Rounding errors and side effects with straight skeleton algorithm

[micycle1]

A user writes...

I have hit an issue that has to do with the skeleton algorithm. The algorithm is being used with path2D (Double) as input and output. In between I use several layers of transformations including your port of the excellent clipper2 library.

I get also various error messages when trying to use triangulations but lets focus on the skeleton algorithm that gives in my particular case the very best, aesthetically, results.

I think I am being hit by rounding errors on double to float conversions because of PShape/PVector design.
This is apparent on almost all cases but it is more pronounced when using holes. There is a partial workarounds by using layering of clipper2 offsets with very small (close to zero)offsets, so usually the calculation allows some refinement of the rounding errors, or at least space can be filled with different "skeleton faces". I have tried some other ways with no results.

I use single and Multiple (totally internal) holes and holes that can touch or intersect main polygon, I create holes by using Area class operations.

PGS 1.3.0 version skeleton faces does not support multi-holes. It gives many artifacts on multi-hole paths and it breaks XOR operations too. Mixed results.
PGS 1.4.0 version is much better, XOR operations work, INTERSECTION IS ALSO OK on multi hole paths (as I use it).

Now about the SUBTRACTION, it generally seems to work BUT it often produces some randomly exposed artifacts, and I am not sure if it is the float/double issue or a bug/inconsistency in skeleton or jts conversion code. Those artifacts are not deterministic. But when I use the clipper offset transfor layer they become deterministic (but still unpredictably random). By deterministic I mean when recalculating the result is the same.

I have also noted that hole polygons that touch the base polygon usually (but not always) get the skeleton right. Only totally inner polygons can create intense artifacts, so a guess is that rounding errors get more pronounced, exaggerated on internal only holes.
Those artifacts are being revealed when iterating thousands of polygons, you might not have the chance to hit this bugs otherwise as it can be 1-10 per 1000 polygons.

I also often see errors like:

java.lang.RuntimeException: Matrix is singular.
at Jama.LUDecomposition.solve(LUDecomposition.java:282)
at Jama.Matrix.solve(Matrix.java:815)
at org.twak.utils.Jama.solve(Jama.java:34)
at org.twak.utils.geom.LinearForm3D.collide(LinearForm3D.java:195)
at org.twak.camp.CoSitedCollision.validateChains(CoSitedCollision.java:180)
at org.twak.camp.HeightCollision.process(HeightCollision.java:105)
at org.twak.camp.Skeleton.skeleton(Skeleton.java:211)
at micycle.pgs.PGS_Contour.straightSkeletonTwak(PGS_Contour.java:301)
at micycle.pgs.PGS_Contour.straightSkeleton(PGS_Contour.java:272)
at micycle.pgs.PGS_Contour.straightSkeleton(PGS_Contour.java:253)

This error is not appearing on every artifact, but it could be related, in fact it mostly appears on very high resolution (very small, near zero length) structures that possibly need better accuracy to be processed and rendered, and can be a side effect of the rounding errors.

I cannot at the moment create a reproduction code, and I am not sure if I can reproduce this outside my workflow.
I am not asking for a solution or course, I m just reporting my experience.
I have also created a feature request in processing4 GitHub but I do not think it will never be touched.
processing/processing4#893

I have though, created a very quick n brutal (only geometry) version of processing-core for doubles, fairly quickly (by replacing of all "float" to "double" words in the codebase, n then trying to fix some errors in various places in order for the codebase be able to compile), but then pgs uses float internally so it breaks with errors. That was just late night code overdose joke, but it could potentially give a valuable result if pgs codebase was also modified accordingly. I didn't try it, I cannot go further, I am not that good.

Assuming that this is a rounding error issue only (not 100% sure on all levels, but it seems to be!), what do you think are the options?
Maybe try to re-create the skeleton algorithm for Path2D i/o?
Or try to avoid the usage of PShape class completely and rely only on jts classes code in a new method in PGS codebase? With the appropriate to/fromJava2D converters. would that be possible?

If you have any ideas or any other/additional experimental skeleton code, please let me know...

[micycle1]

@istinnstudio

Some thoughts...

Or try to avoid the usage of PShape class completely and rely only on jts classes code in a new method in PGS codebase? With the appropriate to/fromJava2D converters. would that be possible?

It's fairly possible and I'd try that first to check whether it is a problem with precision. For instance, the internal straightSkeletonTwak() method takes in JTS Polygon types, whose coordinates are defined with doubles. You could do an initial conversion of Java2D --> JTS, then work entirely with JTS Geometries. Many of PGS methods operate on JTS Geometries under the hood so you could lift the methods from source and change the inputs from PShapes.

An alternative is the skeleton algorithm itself cannot handle the "very small, near zero length" geometries you are attempting to process, even at float-like precision (assuming they are valid geometries). Another alternative is that after subtraction, some polygon's widths get collapsed to zero, so a skeleton is impossible (this could make sense given offsetting seems to help a bit).

Also, you shouldn't need to use clipper2 alongside PGS/JTS. Instead of using clipper2 to offset, you can use geom.buffer() (this is what PGS_Morphology.buffer() uses under the hood).

And if you can create a minimal reproducible example, that would be handy -- I could poke around with things too.

[istinnstudio]

Thanks for the suggestions and the informative reply. It helps a lot.

[istinnstudio]

I have created a rough version of processing4-core that supports double coordinates and an equivalent version of pgs, The issue remains so it looks like is not a float to double rounding error at this level (if my double version is ok). It could rely somewhere in the conversions or skeleton code itself, I cannot go that deep. So for now I am not able to do more or create a reproducible example, I will keep this version and edit artifacts in post-processing. At least the result is more than acceptable!

to sum up, I am posting the 2 most common console errors I get in very high resolution vector artworks, those are not directly related 1-1 messages with the issue, but could be close enough to what it is going on:

using clipper2 offset (on Path2D level before and after skeleton) helps a lot to eliminate them, and redirect the amount and positioning of the faces artifacts

(this one is on the double coords version)
java.lang.IllegalArgumentException: Points of LinearRing do not form a closed linestring
	at org.locationtech.jts.geom.LinearRing.validateConstruction(LinearRing.java:91)
	at org.locationtech.jts.geom.LinearRing.<init>(LinearRing.java:86)
	at org.locationtech.jts.geom.GeometryFactory.createLinearRing(GeometryFactory.java:380)
	at org.locationtech.jts.geom.GeometryFactory.createLinearRing(GeometryFactory.java:367)
	at org.locationtech.jts.awt.ShapeReader.read(ShapeReader.java:98)
	at org.locationtech.jts.awt.ShapeReader.read(ShapeReader.java:59)
	at micycle.pgs.PGS_Conversion.fromJava2D(PGS_Conversion.java:1277)

java.lang.RuntimeException: Matrix is singular.
	at Jama.LUDecomposition.solve(LUDecomposition.java:282)
	at Jama.Matrix.solve(Matrix.java:815)
	at org.twak.utils.Jama.solve(Jama.java:34)
	at org.twak.utils.geom.LinearForm3D.collide(LinearForm3D.java:195)
	at org.twak.camp.CoSitedCollision.validateChains(CoSitedCollision.java:180)
	at org.twak.camp.HeightCollision.process(HeightCollision.java:105)
	at org.twak.camp.Skeleton.skeleton(Skeleton.java:211)
	at micycle.pgs.PGS_Contour.straightSkeletonTwak(PGS_Contour.java:299)
	at micycle.pgs.PGS_Contour.straightSkeleton(PGS_Contour.java:268)
	at micycle.pgs.PGS_Contour.straightSkeleton(PGS_Contour.java:248)

[micycle1]

The first error means your Java2D shapes don't form polygons (they are an unclosed string of vertices).

[istinnstudio]

Yes apparently it does and it is about the skeleton faces and not the source polygon. The only pattern I could recognize is that more complex polygons are more prone to artifacts. Polygons with holes are such a category. In my geometries there are always exactly same polygons that skeletonize right. That's why I initially thought that this is a rounding error.  For my experience there are 2 kind "triggers" of artifacts. One appears on skeletonized polygons without holes and usually can be fixed with small offset values. The other one is most apparent on multi-hole source polygons (so complex that can scramble the skeletonized faces). This one might has to do with the complexity of the source polygon and is not easily fixed, as a result and moves around on offset width change, and one other same initial polygon inherits the artifact!  For what is worth I have created a github repository with the experimental double precision versions of processing4 and pgs. I cannot say if is useful for you:   GitHub - istinnstudio/processing4-double: This is a rough modification of processing4 core in order to support double precision coordinates | | | | | | | | | | | GitHub - istinnstudio/processing4-double: This is a rough modification o... This is a rough modification of processing4 core in order to support double precision coordinates - istinnstudio... | | | Στις Παρασκευή 3 Ιανουαρίου 2025 στις 04:11:20 μ.μ. EET, ο χρήστης Michael Carleton ***@***.***> έγραψε: The first error means your Java2D shapes don't form polygons (they are an unclosed string of vertices). — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: ***@***.***>