search

locationtech / jts

The JTS Topology Suite is a Java library for creating and manipulating vector geometry.
Other
1.99k stars 443 forks source link

SnapIfNeededOverlayOp on 2 Valid Geometries throws "found non-noded intersection" Exception #1086

Open james-willis opened 1 month ago

james-willis commented 1 month ago

A user of Apache Sedona reported an issue where computing the intersection of a valid multipolygon and a valid polygon throws a "found non-noded intersection" Topology Exception. I have reproduced the issue in JTS.

There seems to be a problem in the SnapIfNeededOverlayOp implementation but not OverlayNGRobust. The issue is not symmetric; one ordering of the geometries returns correctly but the other throws the exception.

2 questions: 1) Is there some fix that should be made to SnapIfNeededOverlayOp to avoid failure in this case? Is there a way to detect cases where this failure mode might be encountered? 2) Is there any downside to using OverlayNGRobust? That is the work around that the Sedona users are using for now.

The polygons:

POLYGON ((-5.985979 54.9372974, -5.9857103 54.9374386, -5.9856866 54.9374228, -5.985751 54.9373909, -5.9856392 54.9373165, -5.9855676 54.937352, -5.9856475 54.9374051, -5.9855813 54.9374457, -5.9854978 54.9374129, -5.9854129 54.9374842, -5.9854322 54.9375123, -5.9856833 54.9376109, -5.9857849 54.9375256, -5.9857909 54.9375201, -5.9857555 54.9374875, -5.9859626 54.9373794, -5.9859873 54.9373949, -5.9860307 54.9373721, -5.9860036 54.9373551, -5.9860402 54.9373359, -5.985979 54.9372974), (-5.9856469 54.9374719, -5.9855813 54.9374457, -5.98564744638696 54.93747161301757, -5.9856492 54.9374723, -5.9857264 54.9375026, -5.9856469 54.9374719)) 

MULTIPOLYGON (((-5.9857103 54.9374386, -5.9856866 54.9374228, -5.985751 54.9373909, -5.9856392 54.9373165, -5.9855676 54.937352, -5.9856475 54.9374051, -5.9855813 54.9374457, -5.985647446386958 54.93747161301757, -5.9857103 54.9374386)), ((-5.9857103 54.9374386, -5.985647446386961 54.93747161301757, -5.9856492 54.9374723, -5.9857264 54.9375026, -5.9856469 54.9374719, -5.9855813 54.9374457, -5.9854978 54.9374129, -5.9854129 54.9374842, -5.9854322 54.9375123, -5.9856833 54.9376109, -5.9857849 54.9375256, -5.9857909 54.9375201, -5.9857555 54.9374875, -5.9859626 54.9373794, -5.9859873 54.9373949, -5.9860307 54.9373721, -5.9860036 54.9373551, -5.9860402 54.9373359, -5.985979 54.9372974, -5.9857103 54.9374386)), ((-5.9856469 54.9374719, -5.985647446386961 54.93747161301757, -5.985647446386958 54.93747161301757, -5.9856469 54.9374719)))

Note that last of the polygons in the MultiPolygon is incredibly small.

This runs fine: (new SnapIfNeededOverlayOp(multiPolygon, polygon)).getResultGeometry(OverlayNG.INTERSECTION)

This throws the exception: (new SnapIfNeededOverlayOp(polygon, multiPolygon)).getResultGeometry(OverlayNG.INTERSECTION)

org.locationtech.jts.geom.TopologyException: found non-noded intersection between LINESTRING ( -5.9855813 54.9374457, -5.985647446386959 54.93747161301757 ) and LINESTRING ( -5.98564744638696 54.93747161301757, -5.985647446386958 54.93747161301757 ) [ (-5.985647446386959, 54.93747161301757, NaN) ]

OverlayNGRobust works fine with both orderings:

OverlayNGRobust.overlay(polygon, multiPolygon, OverlayNG.INTERSECTION)
OverlayNGRobust.overlay(multiPolygon, polygon, OverlayNG.INTERSECTION)

I tested some other Overlay implementations as well.

Both orders of OverlayOp fail with the error above:

(new OverlayOp(multiPolygon, polygon)).getResultGeometry(OverlayNG.INTERSECTION)
(new OverlayOp(polygon, multiPolygon)).getResultGeometry(OverlayNG.INTERSECTION)

both orderings of the non-robust NG throw the error above:

(new OverlayNG(polygon, multiPolygon, OverlayNG.INTERSECTION)).getResult()
(new OverlayNG(multiPolygon, polygon, OverlayNG.INTERSECTION)).getResult()

The 'good order' works with SnapOverlay: (new SnapOverlayOp(multiPolygon, polygon)).getResultGeometry(OverlayNG.INTERSECTION)

The 'bad order' throws a new exception: (new SnapOverlayOp(polygon, multiPolygon)).getResultGeometry(OverlayNG.INTERSECTION):

org.locationtech.jts.geom.TopologyException: side location conflict [ (1.2954374999996077E-4, 0.06243860000000012, NaN) ]
dr-jts commented 1 month ago

OverlayNG supersedes the old overlay algorithm. It is significantly more robust, particularly when using OverlayNGRobust. (Unfortunately there are still a few failure cases - see #1000. Hopefully these can be sorted out soonish).

I suggest switching to using the OverlayNGRobust API. This can used for the Geometry overlay methods via the -Djts.overlay=ng flag. In the release it will become the default algorithm, and OverlayOp will be deprecated.