Invalid output from Union

[strk]

The attached SQL file contains two valid geometries (a and b) that, when unioned, result in a topology exception.

It is interesting that the CommonBitsRemover heuristic succeeds in obtaining a valid union with bits removed, but results in the output getting invalid again when re-adding the common bits !!

[strk]

It is also interesting that cascaded union succeeds w/out heuristics on the same dataset.

[strk]

Sorry, the summary was wrong, problem is not a topology exception here, but an invalid result. A topology exception might come up later, when iteratively applying the BinaryOp.

The invalidity is a "Too few points in ring" kind. Basically when translated toward origin (common bits removed) the code doesn't find repeated points, but after re-translating up, for some reason, two points become the same point (precision loss, I guess?).

If theoretically confirmed, this might mean applying common bits removal might not be a good idea from within the SnappingOverlay OP

[strk]

pure GEOS testcase

[strk]

The attached bug358.xml file is for use within GEOS environment. You need to build GEOS with GEOS_DEBUG_BINARYOP defined in include/geos/geom/BinaryOp.h to see the problem.

For some reason XMLTester --test-valid-output doesn't catch the invalidity, which should be researched on too...

[strk]

Alright, the reson why XMLTester --test-valid-output doesn't catch the invalidity is because it tests validity of the expected output, not the obtained output.

Anyway, the problem here is the fact that a valid geometry, when passing trough the "common bits adder" procedure becomes invalid.

The invalidity is a collapsed polygon ring (7th inner ring of obtained result).

POLYGON((1659284.6921065 4797450.16609695,

1659297.0472 4797444.3747, 1659284.6921065 4797450.16609695, 1659284.6921065 4797450.16609695))

The same ring was NOT invalid when computed, which was, with removed bits 1659284 4797450:

POLYGON((4500.69210649658 5130.16609695368,

4500.69210649654 5130.16609695368, 4513.04719999991 5124.37470000051, 4500.69210649658 5130.16609695368))

... thus became invalid when summing up bits and discarding the high precision ones.

Sounds like a conceptually possible thing to happen when removing and then re-adding precision bits.

[strk]

So, confirmed as possible and found out JTS is indeed checking for this condition before passing the result back. Taking the same approach in GEOS (BinaryOp) will automatically fallback to next heuristic function (SnapOp) and succeed for this specific case.

I'd commit such change (so we are closer to JTS). Only problem I have is case5 in robustness.xml which would then fail (rather than giving invalid result, that is...). Not a huge deal, but might raise the question of wheter or not invalid results should be accepted to give the user a chance to clean them up later...

[strk]

For the record, there were other 5 tests, beside the one in robustness.xml, returning invalid geometries in output.

Current trunk have these isolated in their own files (robustness-invalid-output.xml and stml-something-invalid-output.xml).

With the fallback patch all the tests in stml*xml still succeed and give valid results, while the one in robustness-invalid-output.xml fails with an exception. See bug 375 for that one.

[strk]

Fixed by r3102