Opened 13 years ago

Closed 13 years ago

#1383 closed defect (fixed)

Topology: ST_AddEdgeNewFaces() fail to add an edge

Reported by: aperi2007 Owned by: strk
Priority: medium Milestone: PostGIS 2.0.0
Component: topology Version: master
Keywords: Cc:

Description

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

Change History (12)

comment:1 by strk, 13 years ago

Status: newassigned

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

comment:2 by strk, 13 years ago

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.

comment:3 by strk, 13 years ago

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

comment:4 by strk, 13 years ago

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.

comment:5 by strk, 13 years ago

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 !

comment:6 by strk, 13 years ago

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…

comment:7 by strk, 13 years ago

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.

comment:8 by strk, 13 years ago

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))

comment:9 by strk, 13 years ago

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…

comment:10 by strk, 13 years ago

Filed ticket #1459 for the ST_Dwithin case.

comment:11 by strk, 13 years ago

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

comment:12 by strk, 13 years ago

Resolution: fixed
Status: assignedclosed

Regress tested with r8791

Happy topology building !

Note: See TracTickets for help on using tickets.