Opened 13 years ago
Closed 5 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)
Change History (60)
by , 13 years ago
Attachment: | debug-shapes.tgz added |
---|
comment:1 by , 12 years ago
Milestone: | → 3.3.2 |
---|
comment:2 by , 12 years ago
Summary: | TopologyException with valid geometries → TopologyException unioning valid geometries |
---|
comment:3 by , 12 years ago
comment:4 by , 12 years ago
source:trunk/tests/xmltester/tests/ticket/bug188.xml is an example of using HEXWKB as input.
comment:5 by , 12 years ago
How could I write the CascadedUnion of a Polygon collection in an XML test ?
follow-up: 7 comment:6 by , 12 years ago
comment:7 by , 12 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 , 12 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:10 by , 12 years ago
Keywords: | jtsfail added |
---|---|
Milestone: | 3.3.2 → 3.4.0 |
Summary: | TopologyException unioning valid geometries → TopologyException unioning valid geometries [JTS FAILS] |
Version: | 3.3.1 → svn-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...
follow-up: 12 comment:11 by , 12 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 ?
comment:12 by , 12 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 , 12 years ago
Could it be your controls were affected by bug #333 ? Could you double check ?
comment:14 by , 12 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 ?
follow-up: 18 comment:15 by , 12 years ago
A MultiPolygon in which two polygons overlap is not valid.
comment:16 by , 12 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 , 12 years ago
Keywords: | jtsfail removed |
---|---|
Resolution: | → invalid |
Status: | new → closed |
Summary: | TopologyException unioning valid geometries [JTS FAILS] → TopologyException unioning valid geometries |
Actually, I'll close...
comment:18 by , 12 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 , 12 years ago
Keywords: | jts fails added |
---|---|
Resolution: | invalid |
Status: | closed → reopened |
Summary: | TopologyException unioning valid geometries → TopologyException 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 , 12 years ago
Attachment: | bug488.xml added |
---|
comment:20 by , 12 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 , 12 years ago
Ok, thank you. Will you open the bug upstream or am I suppose to do it ?
comment:22 by , 12 years ago
comment:23 by , 12 years ago
Milestone: | 3.4.0 → GEOS Future |
---|
Can't really set a milestone until it's fixed upstream
by , 12 years ago
Attachment: | bug488-reduced.xml added |
---|
comment:24 by , 12 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 , 12 years ago
Don't Union operations already perform precision reduction as an heuristic on topology exception ?
comment:26 by , 12 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.
comment:27 by , 12 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 , 12 years ago
Attachment: | bug488r3.xml added |
---|
further reduction, 5 + 8 vertices in total, with expected result
comment:28 by , 12 years ago
Owner: | changed from | to
---|---|
Status: | reopened → new |
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 , 12 years ago
Milestone: | GEOS Future → 3.3.2 |
---|---|
Resolution: | → fixed |
Status: | new → closed |
Version: | svn-trunk → 3.3.1 |
comment:31 by , 12 years ago
Keywords: | jtsfail added; jts fails removed |
---|
thank you for testing before 3.3.2 is out ! :)
comment:32 by , 12 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 , 12 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 , 12 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 , 12 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.
follow-up: 40 comment:36 by , 12 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 , 12 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 , 12 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 , 12 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)
follow-up: 41 comment:40 by , 12 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.
follow-up: 43 comment:41 by , 12 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 , 12 years ago
Resolution: | fixed |
---|---|
Status: | closed → reopened |
by , 12 years ago
Attachment: | example1.xml added |
---|
by , 12 years ago
Attachment: | example2.xml added |
---|
by , 12 years ago
Attachment: | example3.xml added |
---|
comment:43 by , 12 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 , 12 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 , 12 years ago
Milestone: | 3.3.2 → GEOS Future |
---|
comment:46 by , 11 years ago
I just realized that the test added for this ticket expects a really bogus result...
comment:47 by , 11 years ago
comment:48 by , 11 years ago
Milestone: | GEOS Future → 3.5.0 |
---|
comment:49 by , 9 years ago
Milestone: | 3.5.0 → 3.6.0 |
---|
comment:51 by , 7 years ago
Milestone: | 3.7.0 → 3.8.0 |
---|
sky: could you turn your input data into an XML test ? See source:trunk/tests/xmltester/tests/ticket/bug275.xml for an example