Summary: OverlayNG failures

This is a summary issue fo bug reports about OverlayNG failure cases.

The cases always (?) involve nearly-coincident linework (either in a single input or between inputs). The result of overlay operations is obviously incorrect (i.e. it is drastically different from the expected result).

• https://github.com/shapely/shapely/issues/1871 - the intersection of two non-overlapping polygons with almost coincident linework produces an obviously incorrect result

• https://github.com/JuliaGeo/LibGEOS.jl/issues/166
• https://github.com/libgeos/geos/issues/942
• https://github.com/libgeos/geos/issues/827 - possibly same cause?
• https://github.com/libgeos/geos/issues/741 - possibly same cause?
• https://github.com/libgeos/geos/issues/955 - this is primarily a Voronoi algorithm robustness issue, but the way it manifests as an incorrect shape rather than a TopologyException is due to the noding correctness check failing
• https://github.com/libgeos/geos/issues/965
• https://github.com/libgeos/geos/issues/1170 - caused by union returning nested polygons
• https://github.com/libgeos/geos/issues/1342 - nearly-coincident linework
• https://github.com/libgeos/geos/issues/1343 - nearly-coincident linework causes topology-building failure
• https://github.com/libgeos/geos/issues/1344
• https://github.com/libgeos/geos/issues/1383
• https://github.com/shapely/shapely/issues/1344 - returns point instead of polygon.

Works with snapping

• https://github.com/libgeos/geos/issues/1354

Options for fixing

An Area-Check heuristic was added in #812, but this does not handle all cases. Any fix should be tested to see if it handles the cases resolved by that fix (https://github.com/Toblerity/Shapely/issues/1216, GEOS-1144.

• add an Envelope-Check heuristic sanity check (analogous to the heuristic area check). This will not catch all cases, however.
• use a Area-Only Intersection check, utilizing the IntersectionArea approach. This should be (almost?) fully robust, at the cost of decreased performance
• Add supplementary vertex location checks for linework with topology determined by geometry edge intersection. This should allow detecting invalid topology graphs.

Fixed

• #820

Begin by reviewing the linked failure reports, especially the nearly-coincident linework cases, and compare them with the Area-Check work from #812. No source files or tests are named, so locate the OverlayNG validation and test entry points first. Done means a selected fix handles the reported cases, including the cases previously covered by #812, without introducing incorrect overlay results.