Postgis Topology "mixed face labeling in ring | -267 | [NULL]"

[Lars Aksel Opsahl]

When running data through ​https://gitlab.com/nibioopensource/resolve-overlap-and-gap and checked the result by using ValidateTopology, we found error "mixed face labeling in ring" error for area that we missed data for in the result dataset.

If you run ValidateTopology after running the attached file mixed_topo_error.sql no errors are found.

SELECT * FROM topology.ValidateTopology('test_topo');
 error | id1 | id2 
-------+-----+-----
(0 rows)

Then we add a new linestring with out any error

SELECT topogeo_addlinestring FROM topology.TopoGeo_addLinestring('test_topo','0102000020A21000000200000084CBFA5C7A7824405CC705259CEE4D407A6873CA73782440DE38B01D9CEE4D40',0); 
 topogeo_addlinestring 
-----------------------
                   269

But if we now run topo validation again we see the error

SELECT * FROM topology.ValidateTopology('test_topo');
NOTICE:  00000: Checking for coincident nodes
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for edges crossing nodes
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for invalid or not-simple edges
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for crossing edges
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for edges start_node mismatch
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for edges end_node mismatch
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking for faces without edges
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Checking edge linking
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Building edge rings
LOCATION:  exec_stmt_raise, pl_exec.c:3862
NOTICE:  00000: Found 115 rings, 108 valid shells, 6 valid holes
LOCATION:  exec_stmt_raise, pl_exec.c:3862
            error            | id1  |  id2   
-----------------------------+------+--------
 mixed face labeling in ring | -267 | [NULL]
(1 row)

Here is last server I tested on

PostgreSQL 12.6 (Ubuntu 12.6-0ubuntu0.20.04.1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0, 64-bit

POSTGIS="3.4.0 0874ea3" [EXTENSION] PGSQL="120" GEOS="3.10.1-CAPI-1.16.0" SFCGAL="1.3.7" PROJ="8.2.0 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org USER_WRITABLE_DIRECTORY=/tmp/proj DATABASE_PATH=/usr/share/proj/proj.db" LIBXML="2.9.10" LIBJSON="0.13.1" LIBPROTOBUF="1.3.3" WAGYU="0.5.0 (Internal)" TOPOLOGY

[Lars Aksel Opsahl]

Test file with input sql

[strk]

Confirmed, I can reproduce with:

POSTGIS="3.5.0dev 3.4.0rc1-610-gdfe511b01" GEOS="3.12.0dev-CAPI-1.18.0"

[strk]

Also affected:

• PostGIS 3.3.3-14-g82421b9c7
• PostGIS 3.2.5-10-gbc35b3901
• PostGIS 3.1.9dev 3.1.8-17-gd1fc0f7ae [ with different validity error message "face within face" ]
• PostGIS 3.0.9dev 3.0.7-21-g28cad0324 [ same error as with 3.1.9dev ]

Sounds like a pretty old bug

[strk]

The bug is also present with GEOS="3.9.4-CAPI-1.14.4"

[strk]

This is the incoming line (semitransparent purple) and the starting topology:

The incoming line forms a new shell (counterclockwise ring) at its top side. The face previously occupying that space was the universal face. The code goes to find all edges (forward and backward) that need be update to reflect the new face.

New face is on the inside of the ring, updating forward edges in new ring

Of 102 edges found to interesect the new face bbox and having the universal face on either side, 9 are found to bind the new face:

• 3 edges are found to have the new face on the left: 161, 160 and 252
• 6 edges are found to have the new face on the right: 22, 28, 282, 110, 109, 217

Now, looking with my eyes what QGIS renders as the topology, it looks to me that edges 160 and 161, found by code as binding the new face, cannot possibly both bind the new face as they instead form a face by themselves, a very very tiny face:

I bet the problem thus lying in the code that given a set of edges tries to figure out if they bind or not the new face, and it's definitely a robustness issue.

The ValidateTopology correctly finds that one of those two edges, part of a *different* ring, is, after the update, advertised to have not face 0 on its left side anymore, but another face, contraddicting other edges in its ring.

[strk]

I've atteched a simplified_testcase to use less edges and nodes while still reproducing the issue.

[Lars Aksel Opsahl]

Replying to strk:

I've atteched a simplified_testcase to use less edges and nodes while still reproducing the issue.

Nice

[strk]

WIP fix PR ​https://gitlab.com/postgis/postgis/-/merge_requests/96

[strk]

Ok the issue is in the way we determine if an edge among the edges intersecting the new face is contained or not in the new face.

The way we do this is as follows:

1. We get an interior point of the edge
2. we check with ptarray_contains_point if the new shell contains that point

In our case I bet the "interior point" on the very-close external edge ends up being internal to the new face, as step 1 is a "constructive" method, and thus is subject to drifts. The current code ( _lwt_GetInteriorEdgePoint ) makes a best effort at finding an existing vertex, to avoid the constructtive method, but in this case it evidently fails in doing so. Indeed the edge 160 in the original testcase is formed by only 2 vertices. Edge 161 is the one that's really inside the new face, but edge 160 is erroneously found to be inside due to this constructive interpolation.

I'm not sure what a good fix would be, but the goal here would be avoiding the interpolation. Maybe using Covers from GEOS against the whole line, when the line has less than 3 distinct vertices could be a solution.

[strk]

I found a better fix that does not even require an internal point, going to backport in all branches up to 3.0

[Sandro Santilli <strk@…>]

In 83fbad6/git:

Fix robustness issue in topology face split handling

Stop using interpolation to find edges to update in _lwt_AddFaceSplit.

Includes regress test.

References #5568 in master branch (3.5.0dev)

[Sandro Santilli <strk@…>]

In bfab1e9/git:

Fix robustness issue in topology face split handling

Stop using interpolation to find edges to update in _lwt_AddFaceSplit.

Includes regress test.

References #5568 in stable-3.4 branch (3.4.1dev)

[Sandro Santilli <strk@…>]

In 623dcd61/git:

Fix robustness issue in topology face split handling

Stop using interpolation to find edges to update in _lwt_AddFaceSplit.

Includes regress test.

References #5568 in stable-3.3 branch (3.3.5dev)

[Sandro Santilli <strk@…>]

In 8a797e2/git:

Fix robustness issue in topology face split handling

Stop using interpolation to find edges to update in _lwt_AddFaceSplit.

Includes regress test.

References #5568 in stable-3.2 branch (3.2.6dev)

[Sandro Santilli <strk@…>]

In dab8a55/git:

Fix robustness issue in topology face split handling

Stop using interpolation to find edges to update in _lwt_AddFaceSplit.

Includes regress test.

References #5568 in stable-3.1 branch (3.1.10dev)

[Sandro Santilli <strk@…>]

In bae93ad/git:

Fix robustness issue in topology face split handling

Stop using interpolation to find edges to update in _lwt_AddFaceSplit.

Includes regress test.

Closes #5568 in stable-3.0 branch (3.0.10dev)