Infinite loop in Polygonizer

[mukoki]

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]

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

[dr-jts]

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.

[mloeks]

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]

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]

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