TopologyException in UnaryUnion with collection of valid geometries in input

[strk]

I found a case in which unary unioning a collection of valid polygons results in a failure due to CascadedPolygonUnion giving an invalid (self-intersecting) result.

The problem is in CascadedPolygonUnion::unionUsingEnvelopeIntersection wrongly assuming that unionActual will not move any segment, which instead happens due to robustness issues triggering various snapping/precision-reduction heuristics.

The wrong assumption is also in JTS, and was reported here: ​https://github.com/locationtech/jts/issues/104

[strk]

XML test

[Sandro Santilli <strk@…>]

In 0f26249/git:

UnaryUnion: Drop assumption about union not moving vertices

The assumption resulted in invalid geometries being output
by CascadedPolygonUnion intermediary results and then fed
as input by further union calls, which in turn would fail
on first robustness issue.

Fixes #837
Includes automated XML test

[strk]

After fixing JTS's testrunner: ​https://github.com/locationtech/jts/pull/106 I can say that JTS doesn't fail with the given test. This is not a new case, other cases are known of JTS having less robustness issues than GEOS. I'm not sure if it is about some new robustness fix or just numerical differences in Java and C++. Or just the fact that JTS is more tolerant to invalid geometries in input to Geometry::Union (which instead we check upon first robustness exception).

Anway, I'm reopening this ticket to backport the fix to the 3.6 branch too. I don't think it's worth backporting to 3.5 branch.

[Sandro Santilli <strk@…>]

In 8e6d642/git:

UnaryUnion: Drop assumption about union not moving vertices

The assumption resulted in invalid geometries being output
by CascadedPolygonUnion intermediary results and then fed
as input by further union calls, which in turn would fail
on first robustness issue.

Fixes #837 in 3.6 branch
Includes automated XML test

[strk]

It looks like GCC with -m32 and Autotools is getting a different result for the new test, in travis: ​https://travis-ci.org/OSGeo/geos/jobs/253544104 Clang with -m32 or GCC with -m64 or GCC with -m32 and CMake are fine: ​https://travis-ci.org/OSGeo/geos/builds/253544101

Mateusz: can you think of a reason for this ?

[strk]

Will keep this open until that Travis problem is sorted out

[strk]

I can reproduce the problem by passing -mfpmath=387 to the build config, on a 64bit machine. Doing that, only the new test fails (giving a slightly different result, not raising an exception..)

[strk]

Let's see if -mfpmath=387 works fine in all cases: ​https://github.com/OSGeo/geos/pull/86

[strk]

with -mfpmath=387 the autotools test work on Travis. CMake ones I'm pushing -mfpmath support to tell. Anyway I guess the best fix here would be to make the test result checker more tolerant so to be able to still use fast FP math when available (ie: SSE, SSE2)

[strk]

With [f7391062/git] I took another approach: tolerating small differences in result. If it works it may then be an idea o expect what JTS returns, to check if the test still pass in a way that is compatible with JTS (as JTS passes but get a different result)

[strk]

Travis build with tolerance-based Overlay result checker for XML test: ​https://travis-ci.org/OSGeo/geos/builds/253622747 (still in progress)

[Sandro Santilli <strk@…>]

In 3975725/git:

Use overlay specific result checker

The check just supports some snap-distance based tolerance
for exact match (in addition to topology equality which is
needed for some JTS tests to pass)

Closes #837 (backport of tolerant test checker to 3.6 branch)

[robe]

I'm reopening this ticket because it triggered regression #867.

This is a huge commit so not sure where to start tearing it apart.

[mdavis]

As ​suggested on the JTS issue, a possible fix is to check if any of the "disjoint" polygons overlap the envelope of the union result, and if so union them as well. This has to be done iteratively until no more overlaps occur (which should happen with very few iterations, except in highly pathological cases). This is a fair bit more code, though.

[mdavis]

Forgot to mention on the previous comment: the reason for making this fix is to improve the performance of the current fix (which is severe as noted in #867)

[mdavis]

Update: JTS now has a better approach to UnionByEnvelope, with more robust checking for situations which trigger the error in this issue. The improvement seems to be fairly performant, so may address #867 as well.

​https://github.com/locationtech/jts/pull/429

This needs to be ported to GEOS and tested for performance and correctness.

[pramsey]

This is in fact ported and the test case works.