Opened 7 years ago

Closed 5 years ago

#837 closed defect (fixed)

TopologyException in UnaryUnion with collection of valid geometries in input

Reported by: strk Owned by: strk
Priority: major Milestone: 3.8.0
Component: Core Version: 3.5.1
Severity: Unassigned Keywords:
Cc:

Description

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

Attachments (1)

bug837.xml (114.6 KB ) - added by strk 7 years ago.
XML test

Download all attachments as: .zip

Change History (19)

by strk, 7 years ago

Attachment: bug837.xml added

XML test

comment:1 by Sandro Santilli <strk@…>, 7 years ago

Resolution: fixed
Status: assignedclosed

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

comment:2 by strk, 7 years ago

Milestone: 3.6.2
Version: master3.5.1

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.

comment:3 by Sandro Santilli <strk@…>, 7 years ago

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

comment:4 by strk, 7 years ago

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 ?

comment:5 by strk, 7 years ago

Resolution: fixed
Status: closedreopened

Will keep this open until that Travis problem is sorted out

comment:6 by strk, 7 years ago

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..)

comment:7 by strk, 7 years ago

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

Version 0, edited 7 years ago by strk (next)

comment:8 by strk, 7 years ago

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)

comment:9 by strk, 7 years ago

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)

comment:10 by strk, 7 years ago

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

comment:11 by Sandro Santilli <strk@…>, 7 years ago

Resolution: fixed
Status: reopenedclosed

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)

comment:12 by robe, 6 years ago

Resolution: fixed
Status: closedreopened

comment:13 by robe, 6 years ago

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

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

comment:14 by robe, 6 years ago

Milestone: 3.6.23.8.0

comment:15 by mdavis, 5 years ago

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.

comment:16 by mdavis, 5 years ago

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)

comment:17 by mdavis, 5 years ago

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.

comment:18 by pramsey, 5 years ago

Resolution: fixed
Status: reopenedclosed

This is in fact ported and the test case works.

Note: See TracTickets for help on using tickets.