False topology invalidity returned in presence of dangling edgerings

[strk]

A statement like the following results in ValidateTopology returning invalidities, while starting with a found-valid state:

begin;
select TopoGeo_addLineString('test', ST_Translate(geom, 2, 1))
from (
 select *
 from test.edge
 where edge_id >= 720000
 and edge_id < 730000
 order by edge_id
) foo;
select * from ValidateTopology('test');

The last ValidateTopology call reports 147 face has multiple shells invalidities, all reporting face 0 as having such state.

[strk]

I can reproduce with: where edge_id >= 720000 and edge_id < 722500 order by edge_id The starting topology has 21227 rings, 12441 faces. PostGIS version is 3.3.0dev 3.2.0-614-gefb9ad2bc Errors detected in this cases:

          error           | id1 |   id2   
--------------------------+-----+---------
 face has multiple shells |   0 | -842600
 face has multiple shells |   0 | -842598
 face has multiple shells |   0 | -842595
 face has multiple shells |   0 | -842576
 face has multiple shells |   0 | -842490
 face has multiple shells |   0 | -842325
 face has multiple shells |   0 | -842180
 face has multiple shells |   0 | -842174
 face has multiple shells |   0 | -842151
 face has multiple shells |   0 | -842100
 face has multiple shells |   0 | -842091
 face has multiple shells |   0 | -841862
 face has multiple shells |   0 | -841848
 face has multiple shells |   0 | -841484
 face has multiple shells |   0 | -841363
 face has multiple shells |   0 | -841255
 face has multiple shells |   0 | -841240
 face has multiple shells |   0 | -841194
 face has multiple shells |   0 | -840489
 face has multiple shells |   0 | -840458
 face has multiple shells |   0 | -840456
(21 rows)

[strk]

I can reproduce with where edge_id >= 720000 and edge_id < 722225 order by edge_id resulting in:

          error           | id1 |   id2   
--------------------------+-----+---------
 face has multiple shells |   0 | -846902
 face has multiple shells |   0 | -846757
 face has multiple shells |   0 | -846751
 face has multiple shells |   0 | -846728
 face has multiple shells |   0 | -846677
 face has multiple shells |   0 | -846668
 face has multiple shells |   0 | -846439
 face has multiple shells |   0 | -846425
 face has multiple shells |   0 | -846061
 face has multiple shells |   0 | -845940
 face has multiple shells |   0 | -845832
 face has multiple shells |   0 | -845817
 face has multiple shells |   0 | -845771
 face has multiple shells |   0 | -845066
 face has multiple shells |   0 | -845035
 face has multiple shells |   0 | -845033
(16 rows)

[strk]

I was able to reduce the testcase to addition of a SINGLE linestring, resulting in an invalid topology. Will now work on reduce the starting topology to make it tractable.

[strk]

On a closer look, the "face has multiple shells" seems to be a false invalidity, as the reported "shell" is actually a ring formed only by dangling edges. The Topology validation code is using ST_IsPolygonCCW(ST_MakePolygon($ringedges)) to determine if the ring is a shell, erroneously expecting that a "flat" ring would always return false from ST_IsPolygonCCW but this is evidently not the case.

The manual does not mention any explicit handling of such cases, I'd think a NULL could be returned, or what other options do you see ? ​https://postgis.net/docs/ST_IsPolygonCCW.html

[strk]

Just to give more detail, here's the topology error being reported:

=# select * from test_invalidities ;
          error           | id1 |   id2
--------------------------+-----+---------
 face has multiple shells |   0 | -850133
 face has multiple shells |   0 | -850131
(2 rows)

The two rings, which are reported as being 2 "shells" of the same face (face 0), are formed by these edges:

=# select * FROM GetRingEdges('test', -850133);
 sequence |  edge
----------+---------
        1 | -850133
        2 |  850133
        3 |  850092
        4 |  850096
        5 | -850096
        6 | -850092
(6 rows)
=# select * FROM GetRingEdges('test', -850131);
 sequence |  edge
----------+---------
        1 | -850131
        2 |  850131
(2 rows)

In both cases you can see that the rings are formed by the *same* edges being considered on both sides (3 edges for the first ring, 1 edge for the second ring). These should be considered "holes" for what concerns the ValidateTopology function, but are instead being considered "shells" due to the use of ST_IsPolygonCCW function on the polygon constructed by them.

[strk]

Next thing to do with this ticket: create a testcase to reproduce the error, which implies finding an open LINESTRING that when merged with its own reverse and turned into a Polygon makes ST_IsPolygonCCW return true…

[strk]

I isolated the 2 edgerings reported by ValidateTopology as being duplicated "shells" for face 0, surprisingly the ST_Area function reports a non-zero area for them:

=# select ring_id, ST_IsSimple(g), ST_Area(ST_MakePolygon(g)), ST_IsPolygonCCW(ST_MakePolygon(g)) from test_flatring;
 ring_id | st_issimple |        st_area         | st_ispolygonccw
---------+-------------+------------------------+-----------------
 -850133 | f           |  2.961306592939839e-21 | t
 -850131 | f           | 3.6390156688045347e-20 | f
(2 rows)

This is unexpected, because the list of edges composing the ring (effectively ONE edge for the -850131 case) form a completely FLAT geometry, so should have an area of 0. Maybe I should file a separate ticket for this problem.

[strk]

I filed #5107 for tthe ST_Area issue. As for this case, here's an example flat polygon found to be CCW by ST_IsPolygonCCW:

=# select ST_IsPolygonCCW('
POLYGON((
  29.262792863298348 71.22115103790775,
  29.26598031986849  71.22202978558047,
  29.275379947735576 71.22044935739267,
  29.29461024331857  71.22741507590429,
  29.275379947735576 71.22044935739267,
  29.26598031986849  71.22202978558047,
  29.262792863298348 71.22115103790775
))
');
 st_ispolygonccw 
-----------------
 t
(1 row)

The cause could be the same (winding computed using signed area)

[strk]

Regression test showing the problem described in this ticket was added to merge request ​https://gitlab.com/postgis/postgis/-/merge_requests/70 - a fix is still not available

[strk]

Affected branches are 3.2 and 3.3 (master). Branch 3.1 is not affected

[Sandro Santilli <strk@…>]

In 21ebc0e/git:

Never consider rings composed of only dangling edges as a shell

Works around a robustness issue with ptarray_is_ccw
References #5105 in master branch (3.3.0dev)

[Sandro Santilli <strk@…>]

In efe02efd/git:

Never consider rings composed of only dangling edges as a shell

Works around a robustness issue with ptarray_is_ccw
Closes #5105 in 3.2 branch (3.2.2dev)
Includes NEWS entry