Topology: ST_AddEdgeNewFaces() fail to add an edge

[aperi2007]

Hi, Im having an error try-ing to insert a new edge on a building topology.

I'm use a postgres 9.1.2 on windows with experimental postgis r8404 oon windows. But it came also with older version of postgis.

This is the query sql I run:

select topology.DropTopology('gb_topo');
select topology.CreateTopology('gb_topo',3003);

 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(-0.4 0.4)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(-0.3 0.4)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(-0.2 -0.4)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(-0.2 0.4)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(-0.2 0.7)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(-0.1 0.6)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(-2.77555756156289e-017 0.4)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.1 0.3)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.2 -0.4)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.2 -0.2)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.2 0.2)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.2 0.4)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.2 0.7)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.2 0.8)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.4 0.9)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.5 0.1)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.5 0.2)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.5 0.6)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.6 0.1)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.7 -0.4)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.7 0.2)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(0.9 0.6)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(1 0.6)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(1.1 -0.4)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(1.1 -0.0999999999999999)'));
 select topology.ST_AddIsoNode('gb_topo',0,ST_GeomFromEWKT('SRID=3003;POINT(1.1 0.4)'));


 select topology.ST_AddEdgeNewFaces('gb_topo',20,24,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.7 -0.4,1.1 -0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',3,9,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.2 -0.4,-0.2 -0.5,0.2 -0.5,0.2 -0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',3,9,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.2 -0.4,0.2 -0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',9,20,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 -0.4,0.7 -0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',19,19,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.6 0.1,0.8 0.1,0.8 -0.0999999999999999,0.6 -0.0999999999999999,0.6 0.1)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',24,25,ST_GeomFromEWKT('SRID=3003;LINESTRING(1.1 -0.4,1.1 -0.0999999999999999)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',10,9,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 -0.2,0.2 -0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',14,15,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 0.8,0.3 0.8,0.4 0.9)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',22,23,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.9 0.6,1 0.6)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',13,18,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 0.7,0.3 0.6,0.5 0.6)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',6,13,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.1 0.6,-2.77555756156289e-017 0.7,0.2 0.7)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',18,22,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.5 0.6,0.5 0.8,0.7 0.8,0.8 0.6,0.9 0.6)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',14,13,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 0.8,0.2 0.7)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',5,14,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.2 0.7,-0.2 0.9,0.2 0.9,0.2 0.8)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',15,23,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.4 0.9,1 0.9,1 0.6)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',3,1,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.2 -0.4,-0.4 -0.4,-0.4 0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',25,26,ST_GeomFromEWKT('SRID=3003;LINESTRING(1.1 -0.0999999999999999,1.1 0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',10,21,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 -0.2,0.3 -0.2,0.6 -0.2,0.9 -0.0999999999999999,0.9 0.1,0.7 0.2)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',8,10,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.1 0.3,-0.1 0.2,-0.1 0.1,-0.1 1.38777878078145e-016,0.2 -0.2)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',11,16,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 0.2,0.2 1.38777878078145e-016,0.5 1.38777878078145e-016,0.5 0.1)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',16,17,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.5 0.1,0.5 0.2)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',11,17,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 0.2,0.5 0.2)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',12,17,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 0.4,0.4 0.4,0.5 0.2)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',26,23,ST_GeomFromEWKT('SRID=3003;LINESTRING(1.1 0.4,1.1 0.6,1 0.6)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',21,22,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.7 0.2,0.7 0.3,0.9 0.4,0.9 0.6)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',11,12,ST_GeomFromEWKT('SRID=3003;LINESTRING(0.2 0.2,0.2 0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',7,8,ST_GeomFromEWKT('SRID=3003;LINESTRING(-2.77555756156289e-017 0.4,0.1 0.4,0.1 0.3)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',2,4,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.3 0.4,-0.2 0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',1,2,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.4 0.4,-0.3 0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',4,7,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.2 0.4,-2.77555756156289e-017 0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',7,6,ST_GeomFromEWKT('SRID=3003;LINESTRING(-2.77555756156289e-017 0.4,-0.1 0.5,-0.1 0.6)'));

-- with this last two Adding I have the error.

 select topology.ST_AddEdgeNewFaces('gb_topo',5,4,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.2 0.7,-0.2 0.4)'));
 select topology.ST_AddEdgeNewFaces('gb_topo',2,5,ST_GeomFromEWKT('SRID=3003;LINESTRING(-0.3 0.4,-0.3 0.7,-0.2 0.7)'));

Running this last two I have this errors in psql:

test=> select topology.ST_AddEdgeNewFaces('gb_topo',5,4,ST_GeomFromEWKT('SRID=3 003;LINESTRING(-0.2 0.7,-0.2 0.4)'));

ERROR: Left(7)/right(0) faces mismatch: invalid topology ?

test=> select topology.ST_AddEdgeNewFaces('gb_topo',2,5,ST_GeomFromEWKT('SRID=3 003;LINESTRING(-0.3 0.4,-0.3 0.7,-0.2 0.7)'));

NOTICE: ST_AddEdgeNewFaces: edge 33 splitted face 0

ERROR: Edge 28 has face 0 registered on the side of this face, while edge 30 ha s face 7 on the same side

CONTEXT: SQL statement "SELECT topology.AddFace(atopology, rec.geom, true)" funzione PL/pgSQL "st_addedgenewfaces" linea 594 a istruzione SQL

[strk]

The last edge inserted (edge 30) seems to get face_left and face_right wrong, which would explain the consequent confusion about faces.

[strk]

It's not the last edge, but the one before. It is interesting that removing the edge and adding it again fixes the issue. Must be some memory handling issue.

[strk]

The bug is in AddFace, failing to detect the correct side of the face for the newly added edge (but not consistently!)

[strk]

Adding debugging calls fixes it as well, so _really_ look like memory handling bug. Here's an excerpt of debugging from of a working session:

DEBUG:  p1: POINT(-0.2 0.4)   
DEBUG:  p2: POINT(-2.77555756156289e-17 0.4)
DEBUG:  bounds: LINESTRING(0.1 0.3,-0.1 0.2,-0.1 0.1,-0.1 1.38777878078145e-16,0.2 -0.2,0.2 -0.4,-0.2 -0.4,-0.4 -0.4,-0.4 0.4,-0.3 0.4,-0.2 0.4,-2.77555756156289e-17 0.4,0.1 0.4,0.1 0.3)
DEBUG:  LocatePoint(bounds,p1): 0.865959016295581
DEBUG:  LocatePoint(bounds,p2): 0.93297950814779
DEBUG:  Edge 30 (left:0, right:0) - ring : {0} - right_side : t

When it fails one of the ST_Locate_Point returns 0, swapping right/left side. So could be related to ST_Locate_Point.

[strk]

Here's a failure session:

DEBUG:  p1: POINT(-0.2 0.4)
DEBUG:  p2: POINT(-2.77555756156289e-17 0.4)
DEBUG:  bounds: LINESTRING(-2.77555756156289e-17 0.4,0.1 0.4,0.1 0.3,-0.1 0.2,-0.1 0.1,-0.1 1.38777878078145e-16,0.2 -0.2,0.2 -0.4,-0.2 -0.4,-0.4 -0.4,-0.4 0.4,-0.3 0.4,-0.2 0.4,-2.77555756156289e-17 0.4)
DEBUG:  LocatePoint(bounds,p1): 0.93297950814779
DEBUG:  LocatePoint(bounds,p2): 0
DEBUG:  Edge 30 (left:0, right:0) - ring : {0} - right_side : f

Now it is interesting that the bounds have a different ordering !

[strk]

forceRHR isn't doing what it should:

strk=# with foo as ( select 'LINESTRING(0.1 0.3,-0.1 0.2,-0.1 0.1,-0.1 1.38777878078145e-16,0.2 -0.2,0.2 -0.4,-0.2 -0.4,-0.4 -0.4,-0.4 0.4,-0.3 0.4,-0.2 0.4,-2.77555756156289e-17 0.4,0.1 0.4,0.1 0.3)'::geometry as a, 'LINESTRING(-2.77555756156289e-17 0.4,0.1 0.4,0.1 0.3,-0.1 0.2,-0.1 0.1,-0.1 1.38777878078145e-16,0.2 -0.2,0.2 -0.4,-0.2 -0.4,-0.4 -0.4,-0.4 0.4,-0.3 0.4,-0.2 0.4,-2.77555756156289e-17 0.4)'::geometry as b ) select st_equals(a,b), st_astext(st_forcerhr(st_makepolygon(b))) as b_frhr, st_astext(st_makepolygon(b)) as b_orig, st_astext(st_forcerhr(st_makepolygon(a))) as a_frhr, st_astext(st_makepolygon(a)) as a_orig from foo;
-[ RECORD 1 ]------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
st_equals | t
b_frhr    | POLYGON((-2.77555756156289e-17 0.4,0.1 0.4,0.1 0.3,-0.1 0.2,-0.1 0.1,-0.1 1.38777878078145e-16,0.2 -0.2,0.2 -0.4,-0.2 -0.4,-0.4 -0.4,-0.4 0.4,-0.3 0.4,-0.2 0.4,-2.77555756156289e-17 0.4))
b_orig    | POLYGON((-2.77555756156289e-17 0.4,0.1 0.4,0.1 0.3,-0.1 0.2,-0.1 0.1,-0.1 1.38777878078145e-16,0.2 -0.2,0.2 -0.4,-0.2 -0.4,-0.4 -0.4,-0.4 0.4,-0.3 0.4,-0.2 0.4,-2.77555756156289e-17 0.4))
a_frhr    | POLYGON((0.1 0.3,-0.1 0.2,-0.1 0.1,-0.1 1.38777878078145e-16,0.2 -0.2,0.2 -0.4,-0.2 -0.4,-0.4 -0.4,-0.4 0.4,-0.3 0.4,-0.2 0.4,-2.77555756156289e-17 0.4,0.1 0.4,0.1 0.3))
a_orig    | POLYGON((0.1 0.3,-0.1 0.2,-0.1 0.1,-0.1 1.38777878078145e-16,0.2 -0.2,0.2 -0.4,-0.2 -0.4,-0.4 -0.4,-0.4 0.4,-0.3 0.4,-0.2 0.4,-2.77555756156289e-17 0.4,0.1 0.4,0.1 0.3))

The above is basically showing that two spatially equal lines forming a polygon do not become the _same_ polygon when passed trough ST_ForceRHR, while they should...

[strk]

False alarm, both versions are clockwise, so ForceRHR is fine. One is just shifted. First target here will be making ordering consistent, to help with producing a testcase. Hopefully ordering the edges on edge id would do.

[strk]

Here's the culprit: robustness of ST_DWithin:

DEBUG:  Edge 30 (LINESTRING(-0.2 0.4,-1e-08 0.4)) does not cover ring startpoint (POINT(-1e-08 0.4))

[strk]

More specifically:

strk=# select ST_DWithin('LINESTRING(-0.2 0.4,-1e-08 0.4)', 
                                       'POINT(-1e-08 0.4)', 
                                                          0);
 st_dwithin 
------------
 f
(1 row)

Or, in other words:

=> select ST_DWithin(g, st_endpoint(g), 0) from ( select 'LINESTRING(-0.2 0.4,-1e-08 0.4)'::geometry as g ) f;
 st_dwithin 
------------
 f
(1 row)

A segment endpoint is not within 0 distance from the segment. Note that the test returns TRUE for the firstpoint...

[strk]

Filed ticket #1459 for the ST_Dwithin case.

[strk]

The fix for #1459 fixed this case as well. I'm still trying to produce a testcase for this.

[strk]

Regress tested with r8791

Happy topology building !