TopoGeo_add* silently corrupt topology: edge crosses edge, mixed face labeling in ring

[Lars Aksel Opsahl]

Running the attached file ar50_test_03_topo_2786_test.sql will cause no errors and the topology is valid.

Then we add this line

SELECT ARRAY(SELECT abs(topogeo_addlinestring) FROM topology.TopoGeo_addLinestring('ar50_test_03_topo_2786','0102000020A2100000AD000000CF31743728CA36402EB8101344AD51403AC5066F4BCA3640FF14D9B243AD51408635AF5642CA3640C3EC66E03DAD51406D16E6FCABCA36406D46B5BF3CAD5140E9731143AECA3640E7C249343EAD51401044C5DEBFCA36404FF12D043EAD514094E69998BDCA36400EB88E8F3CAD5140BBB64D34CFCA364076E6725F3CAD514029ABA061C8CA36407CF79F0138AD5140328829FDD9CA36401D6979D137AD5140B62AFEB6D7CA3640A3ECE45C36AD5140DDFAB152E9CA3640445EBE2C36AD51404CEF0480E2CA3640496FEBCE31AD514043127CE4D0CA3640A8FD11FF31AD51405CE1773FC3CA3640EC62614329AD51405304EFA3B1CA36404BF1877329AD5140F599EE5DAFCA36400AB8E8FE27AD5140ECBC65C29DCA3640A289042F28AD51408E52657C9BCA3640280D70BA26AD5140C4B7C20E55CA36408753DF7A27AD5140664DC2C852CA36400ED74A0626AD51407A63642D41CA3640A6A8663626AD514002BA621538CA36406A80F46320AD51402B5C15B9A1CA364014DA42431FAD5140A7B940FFA3CA36408E56D7B720AD514092A39E9AB5CA3640F684BB8720AD514016467354B3CA3640B54B1C131FAD5140E43CA6EFC4CA36401E7A00E31EAD514068DF7AA9C2CA3640DD40616E1DAD5140F0883D834FCB364001C157ED1BAD5140742B123D4DCB3640C087B8781AAD5140422245D85ECB364029B69C481AAD5140A8D1EE915CCB3640E87CFDD318AD514075C8212D6ECB364089EED6A318AD5140DC77CBE66BCB36401072422F17AD5140418A65B048CB364006D2848F17AD5140C52C3A6A46CB3640C698E51A16AD5140CB37C4FDFFCA36407B1575DB16AD514032E76DB7FDCA36403ADCD56615AD5140FFDDA0520FCB3640A20ABA3615AD514007234AC60ACB364021987B4D12AD51403A2C172BF9CA36408026A27D12AD5140BECEEBE4F6CA36403FED020911AD51400FCBE349E5CA3640D7BE1E3911AD5140936DB803E3CA36405E428AC40FAD51403466A8CDBFCA364055A2CC2410AD5140B0C3D313C2CA3640CE1E619911AD5140B6CE5DA77BCA3640F421DB5912AD514014395EED7DCA3640355B7ACE13AD51401A44E88037CA36405B5EF48E14AD514078AEE8C639CA3640D5DA880316AD5140ABB7B52B28CA36403469AF3316AD5140A7038CFD2ECA36402E5882911AAD514054359590E8C936408D9EF1511BAD514014BEBF4AE6C936404D6552DD19AD5140984D163A36C93640E45E48BE1BAD5140D8C4EB7F38C936402498E7321DAD51405F264177E0C83640C47952231EAD514081AAEBBCE2C836403EF6E6971FAD514096C08D21D1C83640D6C702C81FAD5140EA7B617DDCC836405229140F27AD514002EE930F96C836405A3963CF27AD5140EEA995F98CC836405754E6FC21AD5140E6CC0C5E7BC836402869F72C22AD5140FF2EB81879C83640AEEC62B820AD5140207E734644C836401F2B964821AD514039E01E0142C83640DEF1F6D31FAD51404DF6C06530C83640AF06080420AD5140496541202EC836406ECD688F1EAD5140C6E90D7CC4C73640C1D0B9AF1FAD5140DF4BB936C2C7364080971A3B1EAD5140F4615B9BB0C7364050AC2B6B1EAD5140A4AAD925B5C73640D21E6A5421AD5140B9C07B8AA3C73640A2337B8421AD5140836BA5CFA5C73640E36C1AF922AD51409781473494C73640ECC4202923AD5140612C717996C736402CFEBF9D24AD51405BAB780B50C73640DFD7EE5D25AD514092004FC64DC736409E9E4FE923AD5140A716F12A3CC73640A7F6551924AD5140DD6BC7E539C7364066BDB6A422AD5140EAA4E0AE16C736403F2ACE0423AD5140955CDFF318C7364080636D7924AD51408C7F565807C7364089BB73A924AD514001E27EE20BC736400A2EB29227AD5140E64AE40FD7C63640ECF2CF2228AD51409202E354D9C636402D2C6F9729AD514089255AB9C7C63640368475C729AD514034DD58FEC9C6364076BD143C2BAD51402C00D062B8C636407F151B6C2BAD5140836FCDECBCC63640018859552EAD51400622297E76C6364024E872152FAD5140CDA556F471C63640A275342C2CAD5140A6D5A25860C63640ABCD3A5C2CAD51401811CF135EC636406B949BE72AAD51401699FD9ABFC536406476B4972CAD5140A6C75456BDC53640233D15232BAD5140297AB0E776C53640B82319E32BAD514079EEAAB57DC536407ACFF64030AD5140A0BE5E518FC536403834FB1030AD51401090079691C53640796D9A8531AD51405D306FCDB4C536402F7A982531AD5140EBF44212B7C5364070B3379A32AD51405F655EE5EBC53640E4243A0A32AD5140EABFAEB3F2C53640A6D0176836AD51402E838D4F04C636409D78113836AD5140BC47619406C63640DEB1B0AC37AD5140E317153018C636409D16B57C37AD5140FEA0BCB91CC636401E89F3653AAD514043649B552EC636401531ED353AAD5140D0286F9A30C63640566A8CAA3BAD514015EC4D3642C636404D12867A3BAD5140C0A34C7B44C636408E4B25EF3CAD514005672B1756C636404DB029BF3CAD5140775FD02A5FC636405095A69142AD51401ED9B86282C636403EE5993142AD51407221BA1D80C63640FDABFABC40AD5140B6E498B991C63640F453F48C40AD51400B2D9A748FC63640B41A55183FAD51404FF07810A1C63640ABC24EE83EAD5140A1117EFC97C63640A8DDD11539AD5140E6D45C98A9C636409F85CBE538AD5140E3AD60C9A2C63640DDD9ED8734AD5140314EC800C6C63640046DD62734AD5140DC05C745C8C636400C63809C35AD514003D67AE1D9C636403C4E6F6C35AD5140571E7C9CD7C63640FB14D0F733AD51407EEE2F38E9C63640F2BCC9C733AD5140098C07AEE4C63640704A8BDE30AD5140305CBB49F6C6364068F284AE30AD514084A4BC04F4C6364027B9E5392FAD51408D8145A005C736401E61DF092FAD5140E2C9465B03C73640DD2740952DAD51401177839226C7364004BB28352DAD5140DA21ADD728C7364045F4C7A92EAD5140397C26466FC736405AD7A3E92DAD5140957CA31576C7364055C6764732AD5140BC4C57B187C736404C6E701732AD5140A3EAABF689C736408DA70F8C33AD5140F9679CC9BEC73640E425E7FB32AD5140AE419A99C5C73640A6D1C45937AD51408771E6FDB3C7364076E6D58937AD514037BA6488B8C73640F85814733AAD51407C7D4324CAC73640274403433AAD5140631B9869CCC73640687DA2B73BAD514089EB4B05DEC73640986891873BAD5140A24DF7BFDBC73640572FF2123AAD51405B81F12E22C83640DD98B85239AD51405F12717424C836401ED257C73AAD5140ADB2D8AB47C836407EA835673AAD5140A821596645C836403D6F96F238AD5140605553D58BC83640FC1B523238AD51406A77526090C836407D8E901B3BAD5140904706FCA1C83640AD797FEB3AAD5140B3CBB041A4C8364026F613603CAD5140452FF714D9C83640B5B7E0CF3BAD5140FF26A289D4C836403445A2E638AD514026F75525E6C83640643091B638AD51400473ABDFE3C8364023F7F14137AD51402A435F7BF5C836408B25D61137AD514008BFB435F3C8364012A9419D35AD51408DE9E13F4BC93640AA0ACCAC34AD51406B6537FA48C93640318E373833AD5140ED33D4D6D5C93640027B6EB731AD51408B15AA62DAC9364084EDACA034AD514094F232FEEBC93640EC1B917034AD51408D8ADFA1F9C93640E1F9362C3DAD514067BA2B06E8C9364079CB525C3DAD5140238F2C92ECC93640FA3D914540AD5140495FE02DFEC93640636C751540AD5140A7C9E07300CA3640A4A5148A41AD5140125D73AB23CA36407402DD2941AD5140CF31743728CA36402EB8101344AD5140',0) )  ; -
                                      array                                       
----------------------------------------------------------------------------------
 {1800,1802,1805,1808,1811,1813,1816,1819,1820,1809,1814,1267,1817,652,1806,1803}
(1 row)

and still no errors, but if we validate now we get the topo error silently created from the last call.

select topology.ValidateTopology('ar50_test_03_topo_2786');
NOTICE:  00000: Checking for coincident nodes
LOCATION:  exec_stmt_raise, pl_exec.c:3925
NOTICE:  00000: Checking for edges crossing nodes
LOCATION:  exec_stmt_raise, pl_exec.c:3925
NOTICE:  00000: Checking for invalid or not-simple edges
LOCATION:  exec_stmt_raise, pl_exec.c:3925
NOTICE:  00000: Checking for crossing edges
LOCATION:  exec_stmt_raise, pl_exec.c:3925
NOTICE:  00000: Checking for edges start_node mismatch
LOCATION:  exec_stmt_raise, pl_exec.c:3925
NOTICE:  00000: Checking for edges end_node mismatch
LOCATION:  exec_stmt_raise, pl_exec.c:3925
NOTICE:  00000: Checking for faces without edges
LOCATION:  exec_stmt_raise, pl_exec.c:3925
NOTICE:  00000: Checking edge linking
LOCATION:  exec_stmt_raise, pl_exec.c:3925
NOTICE:  00000: Building edge rings
LOCATION:  exec_stmt_raise, pl_exec.c:3925
NOTICE:  00000: Found 687 rings, 669 valid shells, 17 valid holes
LOCATION:  exec_stmt_raise, pl_exec.c:3925
            validatetopology            
----------------------------------------
 ("edge crosses edge",661,1807)
 ("mixed face labeling in ring",-1809,)
(2 rows)

Running on

POSTGIS="3.6.0dev 3.5.0-191-g09b3419dc" [EXTENSION] PGSQL="160" GEOS="3.13.0-CAPI-1.19.0" PROJ="9.5.1 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org USER_WRITABLE_DIRECTORY=/Users/lop/Library/Application Support/proj DATABASE_PATH=/opt/homebrew/Cellar/proj/9.5.1/share/proj/proj.db" (compiled against PROJ 9.5.1) LIBXML="2.13.0" LIBJSON="0.18" TOPOLOGY

[Lars Aksel Opsahl]

testfile

[strk]

Confirmed with

POSTGIS="3.6.0dev 3.5.0-221-g450d3b770" [EXTENSION] PGSQL="170" GEOS="3.14.0dev-CAPI-1.20.0" PROJ="9.1.1 NETWORK_ENABLED=OFF URL_ENDPOINT=​https://cdn.proj.org USER_WRITABLE_DIRECTORY=/tmp/proj DATABASE_PATH=/usr/share/proj/proj.db" (compiled against PROJ 9.1.1) LIBXML="2.9.14" LIBJSON="0.16" LIBPROTOBUF="1.4.1" WAGYU="0.5.0 (Internal)" (core procs from "3.6.0dev 3.5.0-61-gf8c391052" need upgrade) TOPOLOGY (topology procs from "3.6.0dev 3.5.0-61-gf8c391052" need upgrade)

[strk]

simplified testcase

[strk]

I've attached a simplified testcase. The problem is once again with edge segments being almost concidental but not having an intersection, as shown in figure (note the lack of nodes near the end point of the incoming offending red line):

The incoming line results in a new node and the edge merge code seems to be choking on that, but fails to notice it before it is too late!

[Lars Aksel Opsahl]

The dataset we try to clean up are from raster so there are many close parallel lines.

[strk]

Extreme reduction:

SELECT NULL FROM topology.DropTopology('t5862');
SELECT NULL FROM topology.CreateTopology('t5862');
SELECT NULL FROM topology.TopoGeo_addLinestring('t5862',
'LINESTRING(
22.780107846871616 70.70515928614921,
22.779899976871615 70.7046262461492
)');
SELECT NULL FROM topology.TopoGeo_addLinestring('t5862',
'LINESTRING(
22.79217056687162 70.70247684614921,
22.779969266871618 70.70480392614921,
22.780038556871617 70.7049816061492,
22.796764346871615 70.7044482361492
)');

SELECT * FROM validatetopology('t5862');

BEGIN;
SELECT array_agg(x) as last_line_edges FROM
topology.TopoGeo_addLinestring('t5862',
'LINESTRING(
22.780038556871617 70.7049816061492,
22.789676156871618 70.7072799361492
)')
x;
SELECT * FROM validatetopology('t5862');

How it looks:

The purple edge enters the topology first, the green edge second, and does not result in a node being created when they are very close each other. The yellow line is the one added last which results in silent topology corruption

[Sandro Santilli <strk@…>]

In 50a5f3c/git:

Add more precision to debug output

References #5862

[Lars Aksel Opsahl]

Just as a comment here I had a input dataset which resulted in 33200 faces and that was split in 133 working content based grid cell and in 10 of those there was a topology error, some of the errors had an effect more than one cell so distinct errors was

'("face without edges",80171,)'
 '("face without edges",74918,)','("face has wrong mbr",72996,)'
 '("face without edges",78662,)','("face has wrong mbr",74635,)'
 '("face has wrong mbr",77591,)'
 '("face without edges",78662,)'
 '("face without edges",74918,)'

Then I did a new call with the exact same area and code but I change one parameter at this to merge sliver areas that collapses if I buffer in with one meter. This resulted in 33170 faces zero topology errors.

[strk]

In this further simplification we only add a single point to corrupt topology.

SELECT NULL FROM topology.DropTopology('t5862');                                                                               
SELECT NULL FROM topology.CreateTopology('t5862');                                                                             
SELECT NULL FROM topology.TopoGeo_addLinestring('t5862',                                                                       
'LINESTRING(                                                                                                                   
22.780107846871616 70.70515928614921,                                                                                          
22.779899976871615 70.7046262461492                                                                                            
)');                                                                                                                           
SELECT NULL FROM topology.TopoGeo_addLinestring('t5862',                                                                       
'LINESTRING(                                                                                                                   
22.79217056687162 70.70247684614921,                                                                                           
22.779969266871618 70.70480392614921,                                                                                          
22.780038556871617 70.7049816061492,                                                                                           
22.796764346871615 70.7044482361492                                                                                            
)');                                                                                                                           
                                                                                                                               
SELECT * FROM validatetopology('t5862');                                                                                       
                                                                                                                               
BEGIN;                                                                                                                         
SELECT topology.TopoGeo_addPoint('t5862',                                                                                      
'POINT(                                                                                                                        
22.780038556871617 70.7049816061492                                                                                            
)');                                                                                                                           
SELECT * FROM validatetopology('t5862');

[strk]

The code seems to be miscomputing which edge is encountered going clockwise and counter-clockwise around the new node when splitting edge 1.

Node 12 is the new split node (pink in figure).

Edge 2 is the first part of original Edge 2, incoming to node 12 (from below).

Edge 16 is the second part original Edge 2, outgoing from node 12 (going to the right).

Edge 1 is the first part of original Edge 1, incoming to node 12 (from above).

Edge 17 is the second part of original Edge 1, outgoing from node 12 (going down).

The almost coincident edges portions are are 17 and 2, but 2 is supposed to be on the right of 17 or topology validation would have found an edge intersection, which wasn't found.

From the logs we see that the EdgeStar ordering places 17 before 2, when going clockwise:

Star around node 12 has 4 edgeEnds
 EdgeEnd 2 is incoming edge  1, azimuth=0.371830671185702
 EdgeEnd 0 is outgoing edge 16, azimuth=1.60267460060034
 EdgeEnd 3 is outgoing edge 17, azimuth=3.51342332479771
 EdgeEnd 1 is incoming edge  2, azimuth=3.51342332480257

This case seems to be similar to that observed in #5786 - whereas we don't know which computation to trust (was ValidateTopology failing to report validity upfront ? is it reporting a false invalidity after ?).

See ​https://trac.osgeo.org/postgis/ticket/5786#comment:18

[strk]

For the record, the distances of those two internal vertices of Edge2 from Edge1 are:

=# select n, ST_Distance(e1.geom, ST_PointN(e2.geom, n)) 
   from t5862.edge e1, t5862.edge e2, generate_series(2,3) n
   where e1.edge_id = 1 and e2.edge_id = 2;
 n |      st_distance       
---+------------------------
 2 |  4.855711461806118e-16
 3 | 2.8243441995579915e-15
(2 rows)

[strk]

I'm experimenting with using the GEOS 3.9 Precision overlay operations.

Looks promising in that it would (at least in this case) avoid ending up with the initial state of having those internal vertices of edge2 so close to edge1 segment.

Current master branch of PostGIS still only requires 3.8 so we'd have a mix of behaviors if we rely on that, but the advantages might out weight the disadvantages.

WIP PR for that: ​https://git.osgeo.org/gitea/postgis/postgis/pulls/243

Still we should probably run some checks to avoid creating invalid topologies as the biggest priority.

[Lars Aksel Opsahl]

Replying to strk:

I'm experimenting with using the GEOS 3.9 Precision overlay operations.

Nice to test that.

Looks promising in that it would (at least in this case) avoid ending up with the initial state of having those internal vertices of edge2 so close to edge1 segment.

Nice

Current master branch of PostGIS still only requires 3.8 so we'd have a mix of behaviors if we rely on that, but the advantages might out weight the disadvantages.

WIP PR for that: ​https://git.osgeo.org/gitea/postgis/postgis/pulls/243

Still we should probably run some checks to avoid creating invalid topologies as the biggest priority.

Totally agree that main focus should be to avoid topology errors.

[Lars Aksel Opsahl]

Replying to strk:

For the record, the distances of those two internal vertices of Edge2 from Edge1 are:

=# select n, ST_Distance(e1.geom, ST_PointN(e2.geom, n)) 
   from t5862.edge e1, t5862.edge e2, generate_series(2,3) n
   where e1.edge_id = 1 and e2.edge_id = 2;
 n |      st_distance       
---+------------------------
 2 |  4.855711461806118e-16
 3 | 2.8243441995579915e-15
(2 rows)

Can this info be used to throw an topology exception ?

Since we are not able to handle so close points it's better to get a topology error when trying add that line instead of a topology error in the database, I think.

Then it's up the caller to decide what to with this line.

[strk]

Can this info be used to throw an topology exception ?

I've been thinking for a long time about exposing a function capable of SPOTTING those occurrences. It's not very easy to do at the moment with the PostGIS functions we have because what we are looking for is the existance of distinct vertices that are closer than the topology tolerance (easier) but also vertices that are closer than the topology tolerance from SEGMENTS while not being *endpoints* of the segment.

The way such computation could be done NOW, with the functions we have, would be to project each vertex against each segment within tolerance and report if that projected point is NOT a vertex.

I guess I could work on such internal function but I wonder if any such information would ALSO be useful to have exposed at the SQL level as a standalone function. What would that be called, if we want to expose it ?

[strk]

Maybe a function like ST_SnappableItems(geom_to_test, snap_target_points, snap_tolerance) could return locations from geom_to_test so they could be also printed on a map to help users deal with the problem

[strk]

WIP PR to handle this: ​https://git.osgeo.org/gitea/postgis/postgis/pulls/245

[strk]

Backport to 3.4 (also affected) isn't clean, so I'll only backport the fix to 3.5

[Sandro Santilli <strk@…>]

In 4389e29/git:

Check motion range for edge-snapping with no collapses too

Avoid silent topology corruptions.
Includes tests.
References #5862 in master branch

[Sandro Santilli <strk@…>]

In 507c7d2/git:

Check motion range for edge-snapping with no collapses too

Avoid silent topology corruptions.
Includes tests.
Closes #5862 in stable-3.5 branch (3.5.3dev)

[strk]

Replying to strk:

Maybe a function like ST_SnappableItems(geom_to_test, snap_target_points, snap_tolerance) could return locations from geom_to_test so they could be also printed on a map to help users deal with the problem

See #5890