search

locationtech / jts

The JTS Topology Suite is a Java library for creating and manipulating vector geometry.
Other
1.98k stars 443 forks source link

Infinite loop in Polygonizer #874

Open mukoki opened 2 years ago

mukoki commented 2 years ago

Here attached is an awful geometry (a GPS track) making Polygonizer entering an infinite loop. I could not reduce the geometry to a simpler case. Just found that the infinite loop is the do loop in Polygonizer#findDisjointShells(List shellList)

infinite_loop.zip

mukoki commented 2 years ago

Forgot to say that failure only happens with option "extractOnlyPolygonal=true" and that it has been tested with last snapshot

dr-jts commented 2 years ago

Thanks. I can reproduce. Will take a look.

I notice there is a tiny non-simple occurence (self-intersection). Perhaps this is causing the problem. Strictly speaking the Polygonizer is not guaranteed to work with non-noded input. But of course it's always good to avoid infinite loops.

image

mloeks commented 2 years ago

Hi,

I also discovered this infinite loop recently with the funny geometry attached (it's a bit smaller but equally awful than that from the OP).

I might try to double check if the input gets properly noded beforehand. However, as you already pointed out, the infinite loop should be avoided somehow. Would be fantastic if you found a fix for that. Many thanks!

breaking_linestring_wkt.txt

mukoki commented 1 year ago

I could simplify the problem to a minimum test case (containing a self-intersection) : MULTILINESTRING (( 7 2, 7 4 ), ( 9 3, 7 2 ), ( 1 2, 7 4 ), ( 1 2, 1 4 ), ( 7 4, 9 3 ), ( 1 4, 7 2 ))

I also successfully tried a patch to escape the infinite loop in the findDisjointShells method : if no new ring is tagged (isIncludedSet) during the inner loop iteration, we will never be able to go out the outer loop and we could throw an exception with a message about a probable noding problem). But there maybe a better solution.

I tried to see if the problem can be catch earlier. Invalid rings are identified before entering findDisjointShells and maybe it is possible to clean the graph from problematic edges before the problem arises. There is already some code to identify edges belonging to invalid rings only in isIncludedInvalid but I could not find a way to update the graph in a consistent way (and I'm not sure this approach would make it possible to eliminate the infinite loop).

Let me know what would be your preferred approach.

dr-jts commented 1 year ago

An exception is preferable to an infinite loop, so that can be added until a better fix is found.