Open bdon opened 10 months ago
@bdon what do you think of this approach: #703 ? When you add --log-jts-exceptions
it prints out WKT-encoded geometries in the logs along with the error message so we have more context on where the failure occurred. That only adds it for the buffer/union/unbuffer stack trace you shared, are there other entrypoints printing issues?
maybe it's safer to use WKB instead of WKT? Wouldn't writing WKT transform floating-point representation into fixed-precision text; if it's parsed back into floating-point later it might be a different number, which might make robustness problems disappear? Will inspect the logs for different classes of errors now.
maybe it's safer to use WKB instead of WKT?
Generally it is the safest to use WKB. However, I've seen lots (well, some) of OverlayNG issues which can be reproduced using WKT. So either way is likely to provide good feedback.
cheers @bdon !
Another class of exception from the same run:
ERR [archive:encode] - Caught error postprocessing features natural {x=562 y=727 z=11}
org.locationtech.jts.geom.TopologyException: found non-noded intersection between LINESTRING ( -0.000000000000000000000000000000007607423280329582 165.08210678118655, -0.000000000000000000000000000000003803711640164791 165.08210678118655 ) and LINESTRING ( 0 165.08210678118655, -0.000000000000000000000000000000007607423280329582 165.08210678118655 ) [ (-7.607423280329582E-33, 165.08210678118655, NaN) ]
at org.locationtech.jts.noding.FastNodingValidator.checkValid(FastNodingValidator.java:139)
at org.locationtech.jts.noding.ValidatingNoder.validate(ValidatingNoder.java:61)
at org.locationtech.jts.noding.ValidatingNoder.computeNodes(ValidatingNoder.java:56)
at org.locationtech.jts.operation.overlayng.EdgeNodingBuilder.node(EdgeNodingBuilder.java:186)
at org.locationtech.jts.operation.overlayng.EdgeNodingBuilder.build(EdgeNodingBuilder.java:165)
at org.locationtech.jts.operation.overlayng.OverlayNG.nodeEdges(OverlayNG.java:541)
at org.locationtech.jts.operation.overlayng.OverlayNG.computeEdgeOverlay(OverlayNG.java:495)
at org.locationtech.jts.operation.overlayng.OverlayNG.getResult(OverlayNG.java:483)
at org.locationtech.jts.operation.overlayng.OverlayNG.overlay(OverlayNG.java:277)
at org.locationtech.jts.operation.overlayng.OverlayNGRobust.overlay(OverlayNGRobust.java:137)
at org.locationtech.jts.operation.union.CascadedPolygonUnion$1.union(CascadedPolygonUnion.java:62)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.unionActual(CascadedPolygonUnion.java:338)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.unionSafe(CascadedPolygonUnion.java:321)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.binaryUnion(CascadedPolygonUnion.java:246)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.binaryUnion(CascadedPolygonUnion.java:227)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.unionTree(CascadedPolygonUnion.java:191)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.reduceToGeometries(CascadedPolygonUnion.java:286)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.unionTree(CascadedPolygonUnion.java:189)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.reduceToGeometries(CascadedPolygonUnion.java:286)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.unionTree(CascadedPolygonUnion.java:189)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.union(CascadedPolygonUnion.java:179)
at org.locationtech.jts.operation.union.CascadedPolygonUnion.union(CascadedPolygonUnion.java:94)
at org.locationtech.jts.operation.union.UnaryUnionOp.union(UnaryUnionOp.java:219)
at org.locationtech.jts.operation.union.UnaryUnionOp.union(UnaryUnionOp.java:107)
at org.locationtech.jts.geom.GeometryOverlay.union(GeometryOverlay.java:165)
at org.locationtech.jts.geom.Geometry.union(Geometry.java:1439)
at com.onthegomap.planetiler.FeatureMerge.union(FeatureMerge.java:438)
at com.onthegomap.planetiler.FeatureMerge.bufferUnionUnbuffer(FeatureMerge.java:431)
at com.onthegomap.planetiler.FeatureMerge.mergeNearbyPolygons(FeatureMerge.java:325)
at com.onthegomap.planetiler.FeatureMerge.mergeNearbyPolygons(FeatureMerge.java:360)
at com.protomaps.basemap.layers.Natural.postProcess(Natural.java:59)
It is only these two classes of exception that happen, numbering about 10-20 per run for the 100GB output tileset.
We want a separate out-of-band check on the output tileset to check for self-intersection JTS silently creates - my preference is to use https://github.com/mapbox/wagyu
In the non-noded intersection
error, the two linestrings in the error message are VERY short:
LINESTRING ( -0.000000000000000000000000000000007607423280329582 165.08210678118655, -0.000000000000000000000000000000003803711640164791 165.08210678118655 )
LINESTRING ( 0 165.08210678118655, -0.000000000000000000000000000000007607423280329582 165.08210678118655 )
It seems like some heuristic code to eliminate very short line segments might avoid these errors. If these are in the input (which seems unlikely) this could be done by some preprocessing. If they are being created during the union process, I'll need some reproducing data to try and identify a fix.
I wonder if there's a better (ie. faster, more robust) solution than FeatureMerge.bufferUnionUnbuffer
? Buffering/unbuffering is quite likely to introduce line segment artifacts which may cause issues down the road. Plus, it's slow.
Perhaps ConcaveHullOfPolygons
might be an option?
Thanks or the feedback @dr-jts! ConcaveHullOfPolygons sounds promising, I tried it out in place of bufferUnionUnbufer and ran into a couple of issues:
Is there a different sequence of operations you think might help here instead?
@bdon it looks like the same spot in planetiler code will catch that exception as well. I'll print out WKT and base64-encoded WKB just to be safe.
Attached are text files with the full WKT and WKB inputs along with stack traces for the 6 exceptions from last night's build:
exception_6.txt exception_5.txt exception_4.txt exception_3.txt exception_2.txt exception_1.txt
It looks like all these errors are due to the "buffer" result being invalid, due to self-intersecting rings. I'm not sure why this is - probably a bug in the buffer algorithm. Here's an example from one of the error cases:
Can you provide the distance used to buffer? That will help in looking into this.
A workaround is to check the buffered value for validity, and then run GeometryFixer
to fix invalid polygons. To reduce overhead, this could be done only when an exception is encountered.
Another possible fix: buffering essentially acts as a union in itself. So possibly in bufferUnionUnbuffer
the input polygons can simply all be buffered together, and then the intermediate union
can be skipped? However, there might be a performance implication here for very large input sets, since 'buffer
can sometimes take a long time on large complex inputs.
Thanks @dr-jts! Looks like the buffer distance is 0.5.
since 'buffer can sometimes take a long time on large complex inputs
Yes that's what I initially saw while implementing this, they performed about the same until it got to merging a lot of tiny densely packed building polygons and would hang for a long time.
I did some more testing on this case (example_6
):
GEOMETRYCOLLECTION (POLYGON ((240.6875 234.25, 241.5625 233.8125, 242.25 233.5, 243 235.0625, 242.875 235, 242.375 235.25, 242.375 235.375, 241.4375 235.875, 240.6875 234.25)), POLYGON ((242.1875 232.9375, 241.9375 232.9375, 243.0625 232.5625, 243.5 233.5, 242.6875 233.875, 242.1875 232.9375)))
JTS 1.19 produces the invalid buffer (with mitre join) for the first element as you are seeing, which causes the error in union
:
However, JTS 1.20 (unreleased - using the current dev code) produces a correct buffer:
This unions successfully:
example_1
shows the same pattern.
There have been several changes in the codebase that might have improved the buffer output, but I'm not exactly sure what has solved this particular issue.
So - you could try building from the source of master
, and see if that fixes the problems.
As for the low utlity of ConcaveHullOfPolygons
on your data, that's too bad, since it's the theoretically correct solution. Clearly, more research required! For now it seems like your buffer
approach is best. I'm always impressed at how many problems buffer
can solve!
Thanks @dr-jts that's great news! @bdon should be able to force his build to use the latest 1.20.0-SNAPSHOT build to test out if this is fixed.
It would be great if we could use ConcaveHullOfPolygons
eventually, I played with it a bit more and it seems faster on average than buffer/union/unbuffer, it just chokes on the jakarta buildings that are all much closer than the distance threshold - maybe some optimization would eventually help that case? A couple other issues I ran into:
concaveHullByLength(geom, 0.5, true, true)
- is there some additional preprocessing you need to do besides buffer(0)
to join the overlapping polygons?concaveHullByLength(geom, 0.5, true, true)
on buildings2.wbk.txt - is that expected? Or a bug in ConcaveHullOfPolygons ?Attached are all 3 exceptions that arose with JTS 1.20.0-SNAPSHOT.
Note: this runs on slightly different data than before (since it's OSM)
There is a new class of exception that did not appear in the 6 before:
org.locationtech.jts.geom.TopologyException: unable to assign free hole to a shell [ (177.09719405932674, 102.53619843452306, NaN) ]
jts_1_20_exception_3.txt jts_1_20_exception_2.txt jts_1_20_exception_1.txt
It looks like these errors are all due to the initial buffer producing invalid output. Specifically, there's a bug that causes the inward buffer of holes to "invert" and be output as a separate (overlapping) polygon.
The workaround is to check buffer output for validity, and if invalid run GeometryFixer
on it. Hopefully this doesn't introduce too much of a performance penalty.
I'll log this as a JTS issue. It's probably gnarly to fix though, so I doubt I'll have a fix soon.
Would it be sufficient to only do the fix if an exception gets thrown?
Would it be sufficient to only do the fix if an exception gets thrown?
Yes, that's a good idea.
OK I added these test cases and the GeometryFixer fix in #713 - it seems to resolve all of the issues. One other thing that I notice is that the output of the unbuffer operation is often invalid (~12k times per planet render) and gets fixed by this code in snapAndFixPolygon
- that seems to resolve the issue but is that a kind of JTS issue that you want examples of to debug? Currently it just increments a counter and dumps the count at the end.
Thanks for the help @dr-jts !
OK I added these test cases and the GeometryFixer fix in #713 - it seems to resolve all of the issues.
Excellent. Good that GeometryFixer
can clean things up.
One other thing that I notice is that the output of the unbuffer operation is often invalid (~12k times per planet render) and gets fixed by this code in
snapAndFixPolygon
- that seems to resolve the issue but is that a kind of JTS issue that you want examples of to debug? Currently it just increments a counter and dumps the count at the end.
Yes, a few examples of unbuffer invalid output would be good. I will then open a JTS issue for this - to be worked on at some future date. It's gnarly...
Here are some geometries that result in invalid output when you do geometry.buffer(-0.1)
: unbuffer-0.1.zip
And here are some geometries that result in invalid output when you do geometry.unbuffer(-0.5)
: unbuffer-0.5.zip
Is your feature request related to a problem? Please describe.
A couple dozen times per run I'll see JTS exceptions that may be related to robustness in OverlayNG polygon boolops.
Example:
It would be ideal to log these so the exception can be reproduced and reported upstream in the JTS issue tracker.
Describe the solution you'd like Add a configuration flag like
--log-jts-exceptions
. When an exception happens, it serializes the input geometries to the JTS operation to GeoJSON on disk so that the exception can be reproduced later. TBD how to name these output files.