OverlayNG robustness failure

[dr-jts]

The following case produces incorrect results for all overlay operations using OverayNG (in particular, intersection):

A: POLYGON ((66697.40120137333 185279.95469107336, 66698.375 185273.625, 66697.375 185280.125, 66697.40120137333 185279.95469107336))
B: POLYGON ((66710 185280, 66710 185260, 66690 185260, 66690 185280, 66710 185280))

Incorrect result of intersection:

Analysis

A is a very narrow triangle (shown below in Reveal Topology mode):

The cause of the problem is that after noding the long side of the triangle has a vertex introduced, which causes the lower section to shift left enough so that middle vertex ends up on the opposite side of the noded line segment:

Case 2

A: POLYGON ((61607.62679190189 190194.1555478014, 61620.5389918983 190197.4990478009, 61619.64380966499 190197.26724827816, 61607.62679190189 190194.1555478014))
B: POLYGON ((61620.04309999943 190199.41420000046, 61620.41290000081 190197.98570000008, 61620.53899999708 190197.4989, 61607.62680000067 190194.15549999848, 61607.07620000094 190196.27259999886, 61620.04309999943 190199.41420000046))

Case 3

A: POLYGON ((181093.43788657014 172099.78376270586, 181093.375 172099.375, 181093.57688359552 172100.6872433709, 181093.43788657014 172099.78376270586))
B: POLYGON ((181118.78476615425 172110.76716212876, 181097.49019999802 172097.5095999986, 181081.35400000215 172105.30889999866, 181118.78476615425 172110.76716212876))

Notes

• this situation is not detected by the internal noding validation, since the noding is valid in the sense that it does not contain any intersecting segments
• Snapping noding works on this case (so if the incorrect result can be detected, it can be handled by the same logic that handles other robustness failures)

Originally reported as Shapely-1216 and GEOS-1144. This issue presents a simplified geometry.

[dr-jts]

Ideas for ways to detect this invalid topology (and thus throw a TopologyException to trigger using snapping, which does work):

• check the result envelope is consistent with the inputs and the operation (e.g. the envelope of an intersection should be covered by the input envelopes)
• check that the topology of the noded edges is consistent with the inputs (i.e. in this case the input polygon A produces an edge ring which is a hole and no containing shell)
• use the robust IntersectionArea algorithm to verify the result is reasonable, and if not throw so snapping is used