TopologyException unioning valid geometries [JTS fails]

[sky]

Hi,

I do the union of several valid geometries using the CascadedUnion? method which throws a TopologyException?. I've several tests cases of failures.

Here the exceptions:

union fail (3023[16]): TopologyException: found non-noded intersection between LINESTRING (2.39922 48.8778, 2.39854 48.8778) and LINESTRING (2.39922 48.8778, 2.39854 48.8778) at 2.39854 48.8778
union fail (7819[64]): TopologyException: found non-noded intersection between LINESTRING (2.32497 48.8733, 2.32497 48.8733) and LINESTRING (2.32497 48.8733, 2.32497 48.8733) at 2.32497 48.8733
union fail (13073[8]): TopologyException: no outgoing dirEdge found at 2.41216 48.8756

I've enclosed an archive containing several useful data (KML and WKB of the collections, images, etc.).

Thank you for your interest.

Regards,
Jonathan Squirawski

[strk]

sky: could you turn your input data into an XML test ? See source:trunk/tests/xmltester/tests/ticket/bug275.xml for an example

[strk]

source:trunk/tests/xmltester/tests/ticket/bug188.xml is an example of using HEXWKB as input.

[sky]

How could I write the CascadedUnion? of a Polygon collection in an XML test ?

[strk]

CascadedUnion? is exercised by UnaryUnion?, see source:trunk/tests/xmltester/tests/general/TestUnaryUnionFloating.xml

[sky]

Replying to strk:

CascadedUnion? is exercised by UnaryUnion?, see source:trunk/tests/xmltester/tests/general/TestUnaryUnionFloating.xml

Ok, but I don't know the expected result, my tests-cases are too complex, what I'm supposed to put inside the <op> tag ?

[strk]

Put POLYGON EMPTY for now, first bug to spot/fix would be the TopologyException?. I'll use the XML test to try JTS against it, and different versions of GEOS. When (and if) I get a valid result I can update the expected part.

[sky]

Done for the first test-case.

[strk]

Alright, thanks. JTS fails as well: Test Threw Exception (A union) com.vividsolutions.jts.geom.TopologyException?: no outgoing dirEdge found [ (2.412163966209875, 48.87555718514279, NaN) ]

And also fails with GEOS-3.3 branch and trunk...

[strk]

But hold on a second: the input geometry is invalid:

$ ./tests/xmltester/XMLTester --test-valid-input ~/Desktop/Download/bug488.xml /home/strk/Desktop/Download/bug488.xml: case0: test0: : invalid geometry (Geometry A): Self-intersection at or near point 2.4182989742693599 48.878099566078362

What told you they were valid ?

[sky]

Replying to strk:

But hold on a second: the input geometry is invalid: $ ./tests/xmltester/XMLTester --test-valid-input ~/Desktop/Download/bug488.xml /home/strk/Desktop/Download/bug488.xml: case0: test0: : invalid geometry (Geometry A): Self-intersection at or near point 2.4182989742693599 48.878099566078362 What told you they were valid ?

huh? The isValid() function of GEOS told me so. I've tested with 3.2, 3.3 and the svn version (of 2 months ago of course).

[strk]

Could it be your controls were affected by bug #333 ? Could you double check ?

[sky]

No not this bug, but, effectively, I've a weird behavior. In my test I check the polygon one by one before the creation of my collection. They are all valid. But when I run isValid() on the created collection it fails… Do you have an idea of how it's possible ?

[strk]

A MultiPolygon? in which two polygons overlap is not valid.

[strk]

sky: please let me know if you have any really valid input for this, or close it as invalid. Thanks!

[strk]

Actually, I'll close...

[sky]

Replying to strk:

A MultiPolygon? in which two polygons overlap is not valid.

I do not understand, how I'm supposed to do a cascadedUnion of overlaping geometries ?

[strk]

Sorry, you're completely right, UnaryUnion? should work for this case. It is only validity of the components that matters.

[strk]

I've replaced the XML test to use GEOMETRYCOLLECTION ratehr than MULTIPOLYGON. That way the validity checker checks for validity of each and every component, and succeeds (the validity checking).

Next step would be filing the bug upstream in JTS

[sky]

Ok, thank you. Will you open the bug upstream or am I suppose to do it ?

[strk]

Done:  http://sourceforge.net/tracker/index.php?func=detail&aid=3459703&group_id=128875&atid=713120

[strk]

Can't really set a milestone until it's fixed upstream

[mdavis]

This issue is caused by the fact that the input geometry has vertices with very high precision, and nearly-coincident line segments. This occurs both internal to and between geometries.

Attached is a reduced test case containing only two polygons and using binary union directly.

This is a common cause of robustness failure in the current JTS/GEOS overlay algorithm. Fixing this will require some deep design changes in JTS and/or better heuristics for handling failures.

A workaround is to reduce the precision of the input geometries. Using 10 decimal places seems to work.

[strk]

Don't Union operations already perform precision reduction as an heuristic on topology exception ?

[strk]

Enabling some debugging code in GEOS here's what I see:

Trying with original input.
Original exception: TopologyException: no outgoing dirEdge found at 2.4121639662098748 48.875557185142789
Trying with Common Bits Remover (CBR)
CBR: TopologyException: no outgoing dirEdge found at 0.41216396620987483 0.8755571851427888
Trying with snapping 
Computed snap tolerance: 7.513087031840282175e-12
Computed common bits: 2 48
SNAP: snapped geom 1 is INVALID: Self-intersection at or near point 0.41216396620987439 0.8755571851427888 (0.41216396620987438837 0.87555718514278879638)
SNAP: TopologyException: side location conflict at 0.41216396620987439 0.8755571851427888
EXCEPTION on case 1 test 1: TopologyException: no outgoing dirEdge found at 2.4121639662098748 48.875557185142789

I think the key is in the 'snapped geom 1 is INVALID' message, which means that geometry snapping is _introducing_ an invalidity. I saw this in other cases as well, don't remember if I also filed a bug for JTS about it. Anyway see also #501.

If I'm not mistaken the problem is always with snapping making a portion of a polygon collapse to become a line, thus making that part invalid.

[strk]

further reduction, and format fix

[strk]

self-unioning an operand becoming invalid after snap fixes this case. Attaching an updated reduced version with expected result (obtained with this heuristic)

[strk]

further reduction, 5 + 8 vertices in total, with expected result

[strk]

None of the tests we have in GEOS fail with the heuristic in place, despite its broadness. Such heuristic, currently, checks snapped geometries for invalidity and if found invalid self-unions them. This only happens for overlay operations failing when attempted with no intervention.

Sounds promising.

[strk]

I've committed the heuristic described above with r3552 in 3.3 branch and r3553 in trunk

[sky]

Good news, thank you :)

[strk]

thank you for testing before 3.3.2 is out ! :)

[sky]

It seems that you have fixed this test-case but now I have some new errors in the same style:

error: union fail (3023[7439]): TopologyException: found non-noded intersection between LINESTRING (2.39509 48.8356, 2.39509 48.8356) and LINESTRING (2.39509 48.8351, 2.39509 48.8356) at 2.3950887011177491 48.835572343516048
error: union fail (7819[13844]): TopologyException: found non-noded intersection between LINESTRING (2.34948 48.8208, 2.35424 48.8208) and LINESTRING (2.35424 48.8208, 2.35424 48.8208) at 2.3542418040293267 48.820755493485379
error: union fail (13073[10878]): TopologyException: found non-noded intersection between LINESTRING (2.35893 48.6401, 2.35893 48.6401) and LINESTRING (2.35893 48.6401, 2.35893 48.6401) at 2.3589298179424012 48.640088217772316

Do you want an XML test for those ?

[mdavis]

Overlays ops don't use precision reduction currently. The reason is that that would affect ALL the vertices of the geometry, not just the ones causing the problem.

The current snapping code is only a heuristic, so yes it can introduce invalidities. Doing it right would involve a much more complicated approach (and theoretically it's not possible to always snap all geometries correctly).

What do you mean by "self-union"?

[mdavis]

Ok, I see what you mean by self-Union. I don't see why this works, though. Union() just uses the regular union code, which should show the same problem.

Any ideas why it works?

[mdavis]

Ok, I see now what's going on. The snapping makes the MultiPolygon? invalid, because it introduces extra vertices which cause the polygons to overlap one another slightly. However, each individual polygon is valid, so it's possible to union them together, which then creates a valid geometry. This is turn is able to be unioned correctly with the other original input.

The fix of self-unioning after failure is pretty specific to this one case. I'm pretty leery of introducing situation-specific hacks, since they impact performance across the board, and they create messy code which will need to be cleaned up when a better approach is found.

[strk]

@sky: by "new errors" you mean you didn't have them with the old code ?

@mbdavis: doesn't snapping always produce the same kind of invalidity ? seems to be always self-intersections to me, which self-unioning (of the result of snapping) should always "fix". Performance impact could be lower by only checking for self-intersection condition, and maybe only when snapping actually occurs. Anyway, I'm looking for failing cases.

[mdavis]

Yes, snapping should always produce self-intersections as invalidity. But that's not saying very much - 99% of invalid polygons are due to self-intersections.

Self-union will fix invalidity due to two valid polygons overlapping. But it won't fix a single polygon which is itself invalid. And this I think is mostly the kind of invalidity that snapping produces.

If snapping produces valid geometry, then self-union won't have any affect (other than impacting performance). So you shouldn't find any cases which currently work to fail with the new code. What's more interesting is whether the new code makes a difference in cases which currently fail.

[strk]

What I had in mind was dropping collapsed portions of self-intersecting single polygons. If self-union doesn't do that, would buffer(0) do it ?

[strk]

As for the multi-polygon snap creating overlap, can you show a minimal example of that ? I'm wondering if snapping to closest point (rather than first point) would fix that. See  https://sourceforge.net/tracker/?func=detail&atid=713120&aid=3458092&group_id=128875 (and #501)

[sky]

Replying to strk:

@sky: by "new errors" you mean you didn't have them with the old code ?

I had them but not with the same points values. But in fact that is not related to your patch but to the SVN version. Your patch change nothing for me, I have exactly the same errors with or without it.

[strk]

Replying to sky:

I had them but not with the same points values. But in fact that is not related to your patch but to the SVN version. Your patch change nothing for me, I have exactly the same errors with or without it.

Can you try at producing other XML versions of the other tests, with as much reduction as you may handle ?

[sky]

Replying to strk:

Replying to sky:

I had them but not with the same points values. But in fact that is not related to your patch but to the SVN version. Your patch change nothing for me, I have exactly the same errors with or without it.

Can you try at producing other XML versions of the other tests, with as much reduction as you may handle ?

I've added three more examples.

[strk]

I confirm all of them (example{1,2,3}.xml) fail with JTS. With GEOS-3.3 example3.xml does get to a result here, and it seems correct to me. Can you confirm sky ? You'll need at least r3552