`PolygonizeValid` result differs from JTS

[dr-jts]

This set of linework:

MULTILINESTRING ((0 20, 8 20), (8 20, 20 20, 24 10, 11 10), (11 10, 4 10, 0 20), (8 20, 11 10), (11 10, 12 8, -4 10, 0 20))

produces the following result for a Polygonizer operation with extractOnlyPolygonal = true:

MULTIPOLYGON (((11 10, 12 8, -4 10, 0 20, 4 10, 11 10)), ((11 10, 8 20, 20 20, 24 10, 11 10)))

However, in GEOS the same operation

bin/geosop -a 'MULTILINESTRING ((0 20, 8 20), (8 20, 20 20, 24 10, 11 10), (11 10, 4 10, 0 20), (8 20, 11 10), (11 10, 12 8, -4 10, 0 20))' polygonizeValid

produces:

POLYGON ((0 20, 8 20, 11 10, 4 10, 0 20))

[dr-jts]

This is due to different logic in Polygonizer.findDisjointShells between JTS and GEOS.

This logic was changed in this commit: https://github.com/libgeos/geos/commit/c5c826b340045c6e1581afb7587f41acf57237fa

[dbaston]

I can see that they're different but don't understand why one or the other would be preferable.

[dr-jts]

The original logic was intended to include the outermost polygons. This is ambiguous in some cases (such as two adjacent rectangles), but not in this case.

[dbaston]

Isn't it pretty much the same as

MULTILINESTRING ((1 0, 2 0, 2 1, 1 1, 1 0), 
  (2 0, 3 0, 3 1, 2 1), 
  (1 0, 0 0, 0 1, 1 1))

as there are no containment relationships between the polygons?

[dbaston]

Scratch that -- the polygonizer throws errors on it.

[dbaston]

Here is one in which the "middle" polygon is returned:

MULTILINESTRING ((0 1, 0 0, 1 0, 1 1), 
  (0 2, -1 1.5, 0 1), 
  (0 1, 1 1), 
  (0 2, 1 2), 
  (1 2, 1 1), 
  (1 2, 1 3, 0 3, 0 2))

[dbaston]

Or, modifying the example, from the top,

MULTILINESTRING ((0 20, -10 21, 8 20), 
  (8 20, 20 20, 24 10, 11 10), 
  (11 10, 4 10, 0 20), 
  (8 20, 11 10), 
  (11 10, 12 8, -4 10, 0 20))

vs

MULTIPOLYGON (((11 10, 12 8, -4 10, 0 20, 4 10, 11 10)), 
  ((8 20, 20 20, 24 10, 11 10, 8 20)))

Is "outermost" here just referring to "minimum X coordinate?

[dr-jts]

Is "outermost" here just referring to "minimum X coordinate?

That heuristic would make the results deterministic, which is important to have (for testing purposes if nothing else). Not sure if that's the way it's implemented right now.

[dr-jts]

The heuristic actually needs to be "polygon containing minimum segment", where segments are ordered using the standard lexicographic XY ordering of their endpoints.

Actually perhaps it should be "segment with lowest endpoint and smallest/lowest angle at that node".

PolygonizeValid on this case produces:

[dbaston]

Isn't the purpose of this operation to exclude interior polygons from the result? In all of these cases there are no interior polygons so there is no "correct" result. I feel like I'm missing something fundamental about what the bug is here.

[dr-jts]

The goal is to make the output deterministic, so it is repeatable between JTS and GEOS for all cases.

This may require adding a sort to both libs. And then ensure the polygon alternation algorithm behaves the same.