Opened 5 months ago

Closed 5 months ago

#5568 closed defect (fixed)

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

Reported by: Lars Aksel Opsahl Owned by: strk
Priority: medium Milestone: PostGIS 3.0.10
Component: topology Version: 3.0.x
Keywords: Cc:

Description (last modified by 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

Attachments (4)

mixed_topo_error.sql (93.3 KB ) - added by Lars Aksel Opsahl 5 months ago.
Test file with input sql
starting_condition.png (18.2 KB ) - added by strk 5 months ago.
tiny_face_bound_by_160_161.png (6.4 KB ) - added by strk 5 months ago.
simplified_testcase.sql (878 bytes ) - added by strk 5 months ago.

Download all attachments as: .zip

Change History (20)

by Lars Aksel Opsahl, 5 months ago

Attachment: mixed_topo_error.sql added

Test file with input sql

comment:1 by Lars Aksel Opsahl, 5 months ago

Description: modified (diff)

comment:2 by strk, 5 months ago

Confirmed, I can reproduce with:

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

comment:3 by strk, 5 months ago

Milestone: PostGIS 3.4.1PostGIS 3.0.10
Version: 3.4.x3.0.x

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

comment:4 by strk, 5 months ago

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

by strk, 5 months ago

Attachment: starting_condition.png added

by strk, 5 months ago

comment:5 by strk, 5 months ago

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.

comment:6 by strk, 5 months ago

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

in reply to:  6 comment:7 by Lars Aksel Opsahl, 5 months ago

Replying to strk:

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

Nice

by strk, 5 months ago

Attachment: simplified_testcase.sql added

comment:9 by strk, 5 months ago

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.

comment:10 by strk, 5 months ago

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

comment:11 by Sandro Santilli <strk@…>, 5 months ago

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)

comment:12 by Sandro Santilli <strk@…>, 5 months ago

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)

comment:13 by Sandro Santilli <strk@…>, 5 months ago

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)

comment:14 by Sandro Santilli <strk@…>, 5 months ago

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)

comment:15 by Sandro Santilli <strk@…>, 5 months ago

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)

comment:16 by Sandro Santilli <strk@…>, 5 months ago

Resolution: fixed
Status: newclosed

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)

Note: See TracTickets for help on using tickets.