Union with snapping heuristic is very slow

[dr-jts]

Original source: GEOS 997.

Union of two large geometries runs the snapping heuristic due to a noding robustness error. Because of the size of the geometries snapping is extremely slow.

A fix is not currently obvious. Some options are:

• Instead of the snapping heuristic use the buffer(0) hack (which in this case also invokes some rounding to handle the noding issue, so does round all output vertices somewhat)
• It might be possible to a priori decide if snapping will take "too long" and only then use buffer(0)
• The new overlay code in the works does not use snapping. However, it does requires rounding to a defined precision model (which is generally a Good Thing, but is a small change in semantics)

[dr-jts]

Test case reproducing the slowness.

geos997-slow-union.xml.zip

[dr-jts]

Interestingly, the polygons causing the issue are a result of buffering polygons from a polygonal coverage. The failure point is a point on the buffer outline which is computed slightly differently in each polygon. This is likely due to imprecision when computing the round buffer fillets where one segment of the base convex angle is the same, and the other different.

This kind of effect could be avoided by computing the buffers using a defined precision model. (In fact, the original problem was worked around by snapping the buffer results to a grid with grid size 0.001)

[dr-jts]

OverlayNG using the SnappingNoder fixes this issue.