Opened 8 years ago

Last modified 2 years ago

#488 reopened defect

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 8 years ago.
bug488.xml (4.8 KB) - added by strk 8 years ago.
bug488-reduced.xml (4.4 KB) - added by mdavis 8 years ago.
bug488r2.xml (1.3 KB) - added by strk 8 years ago.
further reduction, and format fix
bug488r3.xml (1.2 KB) - added by strk 8 years ago.
further reduction, 5 + 8 vertices in total, with expected result
example1.xml (7.4 KB) - added by sky 8 years ago.
example2.xml (32.0 KB) - added by sky 8 years ago.
example3.xml (4.8 KB) - added by sky 8 years ago.

Download all attachments as: .zip

Change History (59)

Changed 8 years ago by sky

Attachment: debug-shapes.tgz added

comment:1 Changed 8 years ago by strk

Milestone: 3.3.2

comment:2 Changed 8 years ago by strk

Summary: TopologyException with valid geometriesTopologyException unioning valid geometries

comment:3 Changed 8 years ago by strk

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 Changed 8 years ago by strk

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

comment:5 Changed 8 years ago by sky

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

comment:7 in reply to:  6 Changed 8 years ago by 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 ?

comment:8 Changed 8 years ago by 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.

comment:9 Changed 8 years ago by sky

Done for the first test-case.

comment:10 Changed 8 years ago by strk

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 Changed 8 years ago by 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 ?

comment:12 in reply to:  11 Changed 8 years ago by 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).

comment:13 Changed 8 years ago by strk

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

comment:14 Changed 8 years ago by 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 ?

comment:15 Changed 8 years ago by strk

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

comment:16 Changed 8 years ago by strk

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

comment:17 Changed 8 years ago by strk

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

Actually, I'll close...

comment:18 in reply to:  15 Changed 8 years ago by 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 ?

comment:19 Changed 8 years ago by strk

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.

Changed 8 years ago by strk

Attachment: bug488.xml added

comment:20 Changed 8 years ago by 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

comment:21 Changed 8 years ago by sky

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

comment:23 Changed 8 years ago by strk

Milestone: 3.4.0GEOS Future

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

Changed 8 years ago by mdavis

Attachment: bug488-reduced.xml added

comment:24 Changed 8 years ago by 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.

comment:25 Changed 8 years ago by strk

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

comment:26 Changed 8 years ago by 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.

Changed 8 years ago by strk

Attachment: bug488r2.xml added

further reduction, and format fix

comment:27 Changed 8 years ago by strk

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

Changed 8 years ago by strk

Attachment: bug488r3.xml added

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

comment:28 Changed 8 years ago by strk

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 Changed 8 years ago by strk

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 Changed 8 years ago by sky

Good news, thank you :)

comment:31 Changed 8 years ago by strk

Keywords: jtsfail added; jts fails removed

thank you for testing before 3.3.2 is out ! :)

comment:32 Changed 8 years ago by 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 ?

comment:33 Changed 8 years ago by 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"?

comment:34 Changed 8 years ago by 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?

comment:35 Changed 8 years ago by 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.

comment:36 Changed 8 years ago by 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.

comment:37 Changed 8 years ago by 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.

comment:38 Changed 8 years ago by 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 ?

comment:39 Changed 8 years ago by 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)

comment:40 in reply to:  36 ; Changed 8 years ago by 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.

comment:41 in reply to:  40 ; Changed 8 years ago by 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 ?

comment:42 Changed 8 years ago by strk

Resolution: fixed
Status: closedreopened

Changed 8 years ago by sky

Attachment: example1.xml added

Changed 8 years ago by sky

Attachment: example2.xml added

Changed 8 years ago by sky

Attachment: example3.xml added

comment:43 in reply to:  41 Changed 8 years ago by 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.

comment:44 Changed 8 years ago by 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

comment:45 Changed 8 years ago by strk

Milestone: 3.3.2GEOS Future

comment:46 Changed 7 years ago by strk

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

comment:47 Changed 7 years ago by strk

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 Changed 6 years ago by robe

Milestone: GEOS Future3.5.0

comment:49 Changed 4 years ago by robe

Milestone: 3.5.03.6.0

comment:50 Changed 3 years ago by strk

Milestone: 3.6.03.7.0

Ticket retargeted after milestone closed

comment:51 Changed 2 years ago by robe

Milestone: 3.7.03.8.0
Note: See TracTickets for help on using tickets.