Opened 11 years ago

Closed 3 years ago

#488 closed defect (fixed)

TopologyException unioning valid geometries [JTS fails]

Reported by: sky Owned by: strk
Priority: major Milestone: 3.8.0
Component: Default Version: 3.3.1
Severity: Unassigned Keywords: jtsfail
Cc:

Description

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

Attachments (8)

debug-shapes.tgz (97.0 KB ) - added by sky 11 years ago.
bug488.xml (4.8 KB ) - added by strk 11 years ago.
bug488-reduced.xml (4.4 KB ) - added by mdavis 11 years ago.
bug488r2.xml (1.3 KB ) - added by strk 11 years ago.
further reduction, and format fix
bug488r3.xml (1.2 KB ) - added by strk 11 years ago.
further reduction, 5 + 8 vertices in total, with expected result
example1.xml (7.4 KB ) - added by sky 11 years ago.
example2.xml (32.0 KB ) - added by sky 11 years ago.
example3.xml (4.8 KB ) - added by sky 11 years ago.

Download all attachments as: .zip

Change History (60)

by sky, 11 years ago

Attachment: debug-shapes.tgz added

comment:1 by strk, 11 years ago

Milestone: 3.3.2

comment:2 by strk, 11 years ago

Summary: TopologyException with valid geometriesTopologyException unioning valid geometries

comment:3 by strk, 11 years ago

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

comment:4 by strk, 11 years ago

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

comment:5 by sky, 11 years ago

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

in reply to:  6 comment:7 by sky, 11 years ago

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 ?

comment:8 by strk, 11 years ago

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.

comment:9 by sky, 11 years ago

Done for the first test-case.

comment:10 by strk, 11 years ago

Keywords: jtsfail added
Milestone: 3.3.23.4.0
Summary: TopologyException unioning valid geometriesTopologyException unioning valid geometries [JTS FAILS]
Version: 3.3.1svn-trunk

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

comment:11 by strk, 11 years ago

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 ?

in reply to:  11 comment:12 by sky, 11 years ago

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

comment:13 by strk, 11 years ago

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

comment:14 by sky, 11 years ago

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 ?

comment:15 by strk, 11 years ago

A MultiPolygon in which two polygons overlap is not valid.

comment:16 by strk, 11 years ago

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

comment:17 by strk, 11 years ago

Keywords: jtsfail removed
Resolution: invalid
Status: newclosed
Summary: TopologyException unioning valid geometries [JTS FAILS]TopologyException unioning valid geometries

Actually, I'll close...

in reply to:  15 comment:18 by sky, 11 years ago

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 ?

comment:19 by strk, 11 years ago

Keywords: jts fails added
Resolution: invalid
Status: closedreopened
Summary: TopologyException unioning valid geometriesTopologyException unioning valid geometries [JTS fails]

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

by strk, 11 years ago

Attachment: bug488.xml added

comment:20 by strk, 11 years ago

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

comment:21 by sky, 11 years ago

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

comment:23 by strk, 11 years ago

Milestone: 3.4.0GEOS Future

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

by mdavis, 11 years ago

Attachment: bug488-reduced.xml added

comment:24 by mdavis, 11 years ago

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.

comment:25 by strk, 11 years ago

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

comment:26 by strk, 11 years ago

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.

by strk, 11 years ago

Attachment: bug488r2.xml added

further reduction, and format fix

comment:27 by strk, 11 years ago

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

by strk, 11 years ago

Attachment: bug488r3.xml added

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

comment:28 by strk, 11 years ago

Owner: changed from geos-devel@… to strk
Status: reopenednew

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.

comment:29 by strk, 11 years ago

Milestone: GEOS Future3.3.2
Resolution: fixed
Status: newclosed
Version: svn-trunk3.3.1

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

comment:30 by sky, 11 years ago

Good news, thank you :)

comment:31 by strk, 11 years ago

Keywords: jtsfail added; jts fails removed

thank you for testing before 3.3.2 is out ! :)

comment:32 by sky, 11 years ago

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 ?

comment:33 by mdavis, 11 years ago

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"?

comment:34 by mdavis, 11 years ago

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?

comment:35 by mdavis, 11 years ago

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.

comment:36 by strk, 11 years ago

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

comment:37 by mdavis, 11 years ago

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.

comment:38 by strk, 11 years ago

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 ?

comment:39 by strk, 11 years ago

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)

in reply to:  36 ; comment:40 by sky, 11 years ago

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.

in reply to:  40 ; comment:41 by strk, 11 years ago

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 ?

comment:42 by strk, 11 years ago

Resolution: fixed
Status: closedreopened

by sky, 11 years ago

Attachment: example1.xml added

by sky, 11 years ago

Attachment: example2.xml added

by sky, 11 years ago

Attachment: example3.xml added

in reply to:  41 comment:43 by sky, 11 years ago

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.

comment:44 by strk, 11 years ago

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

comment:45 by strk, 11 years ago

Milestone: 3.3.2GEOS Future

comment:46 by strk, 10 years ago

I just realized that the test added for this ticket expects a really bogus result...

comment:47 by strk, 10 years ago

Note that as of r3751 in master as r3750 in 3.3 branch the exception is back (and I've to say it's better than the clearly bogus return we have had so far).

comment:48 by robe, 9 years ago

Milestone: GEOS Future3.5.0

comment:49 by robe, 7 years ago

Milestone: 3.5.03.6.0

comment:50 by strk, 6 years ago

Milestone: 3.6.03.7.0

Ticket retargeted after milestone closed

comment:51 by robe, 5 years ago

Milestone: 3.7.03.8.0

comment:52 by Paul Ramsey <pramsey@…>, 3 years ago

Resolution: fixed
Status: reopenedclosed

In 1f341e5/git:

Fix test case expected value to match up to results generated now.
No longer an exception, and result passes visual inspection.
Finally,
Closes #488

Note: See TracTickets for help on using tickets.