Union topology exceptions lead to complete loss of floating point precision

[dannytoone]

This is a cross-posted bug from the PostGIS project, which is calling GEOS for the union function. Certain complex geometries can cause topology exceptions, triggering routines to try to simplify the geometries. This process cascades until all decimal precision is lost.

​https://trac.osgeo.org/postgis/ticket/4711

Inside the ticket you'll find a synthetic data generation process (in PostGIS) which produces geometries which will reproduce the error. According to mdavis:

To follow on from what Paul has said, I tried the union using the new Overlay algorithm in JTS, and it works perfectly (and is pretty fast too).

The new Overlay uses a more effective snapping approach to improve robustness. It doesn't require the aggressive precision reduction that PostGIS/GEOS is using now. So we're very hopeful this will solve most or all of these kinds of issues.

As a side note, your synthetic data generation process seems like a great way to produce stress-testing datasets for overlay. This is actually tricky to do with synthetic data, so well done!

I'm crossposting here so this synthetic dataset can be used for testing on the port of the Overlay algorith from JTS.

[mdavis]

Extract of lines from synthetic data which causes a failure during unary union (in JTS)

[mdavis]

A synthetic data extract of lines which causes union to fail

[mdavis]

A synthetic data extract of lines which causes union to fail - #3

[mdavis]

A synthetic data extract of lines which causes union to fail - #4

[dannytoone]

@mdavis

I found your repo where you're developing OverlayNG and I'm currently trying to build it and use it on some of the geometries I've worked with. It is ​https://github.com/dr-jts/jts/tree/overlay-sr, right? And the OverlayNGSnapIfNeeded.union method?

I could help with geometries and stack traces for any exceptions thrown...is there an easy way to serialize the data that throws the exceptions? I'm fairly unfamiliar with JTS and java in general, so any help would be appreciated.

[mdavis]

Yes, that is the repo for OverlayNG.

It would be great if you are able to test this. I'm happy to help with advice on building and running JTS.

You can use WKBWriter to serialize geometry data. (I assume you are creating the data synthetically, since otherwise you would already have an image of the data?).

If you are building from source, you could even add some code at the point the exception is thrown to write out just the geometries which cause the exception (as opposed to the full union() input dataset). The location is given in the stack trace.

[dannytoone]

Just gave it a runthrough on my dataset, and with the exception of a stack overflow error (fixed by increasing the stack size through -Xss), it ran flawlessly. I fully expected to see a bunch of exceptions, but it handled them all really well. Visually I can't find any flaws in the result.

The operation was basically a process to flatten a bunch of geometries using a process similar to this: ​http://blog.cleverelephant.ca/2019/07/postgis-overlays.html

My full dataset is probably too big to post here, but here I'll try to attach a photo of the resulting geometries to get an idea at what I was throwing at it.

Not sure if it would be useful to find a way to get you this dataset for exploring the behavior around topology exceptions that are handled internally. I know for a fact that this same dataset will reproduce the error linked above in the postgis tracker.

[dannytoone]

fully unioned dataset

[mdavis]

Replying to dannytoone:

Just gave it a runthrough on my dataset, and with the exception of a stack overflow error (fixed by increasing the stack size through -Xss), it ran flawlessly. I fully expected to see a bunch of exceptions, but it handled them all really well. Visually I can't find any flaws in the result.

Excellent!

Not sure if it would be useful to find a way to get you this dataset for exploring the behavior around topology exceptions that are handled internally. I know for a fact that this same dataset will reproduce the error linked above in the postgis tracker.

That's ok, we are already using some of the data from your synthetic data generator as part of the OverlayNG robustness tests. Given the success of your testing, I think we can call this good, and you can wait for OverlayNG to land in GEOS.

[pramsey]

Ran all these cases through PostGIS/GEOS 3.9 and they all processed without exceptions. Thanks for the sample data!