Opened 6 years ago
Last modified 3 months ago
#3464 new defect
ERROR: lwt_ChangeEdgeGeom could not construct face X, on the left of edge Y
Reported by: | strk | Owned by: | strk |
---|---|---|---|
Priority: | medium | Milestone: | PostGIS Fund Me |
Component: | topology | Version: | master |
Keywords: | robustness | Cc: | esseffe |
Description
This is a followup to #3463
Self-contained test triggering the error in the Summary:
SELECT DropTopology('bug3463'); SELECT CreateTopology('bug3463'); SELECT TopoGeo_AddLinestring('bug3463', g) FROM ( VALUES ('LINESTRING(634451.7803 4829559.1626,634485.78 4829525.1627,634506.460690994 4829496.52791544)'::geometry), ('LINESTRING(634447.034152733 4829589.53826525,634451.7794 4829559.1635,634451.7803 4829559.1626)'), ('LINESTRING(634506.460690994 4829496.52791544,634511.7798 4829489.163,634516.720831369 4829468.57536243)'), ('LINESTRING(634451.7803 4829559.1626,634485.78 4829525.1629,634488.637 4829521.2083,634506.460690994 4829496.52791544)'), ('LINESTRING(634506.460690994 4829496.52791544,634511.7792 4829489.1634,634516.720831369 4829468.57536243)') ) foo (g); SELECT TopoGeo_AddLinestring('bug3463', 'LINESTRING(634452.780338203 4829623.16197433,634446.780374345 4829591.16223176,634451.78032304 4829559.16248522,634485.780040461 4829525.1627442,634488.530017153 4829521.16277512,634511.779820754 4829489.16302201,634523.779707286 4829439.16341655,632187.797669813 4827723.17794488,631718.05142978 4827788.42759019,631718.05144314 4827826.17728887,632759.754208638 4830776.16598454)' ::geometry);
Note that the same test also fails with 2.1 branch but triggers a different error (geometry crosses edge).
Attachments (5)
Change History (22)
comment:1 Changed 6 years ago by
Cc: | esseffe added |
---|
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
Reduced testcase:
SELECT DropTopology('bug3464'); SELECT CreateTopology('bug3464'); SELECT TopoGeo_AddLinestring('bug3464', g) FROM ( VALUES ('LINESTRING(634451.7803 4829559.1626,634485.78 4829525.1627,634506.460690994 4829496.52791544)' ::geometry), ('LINESTRING(634451.7803 4829559.1626,634485.78 4829525.1629,634506.460690994 4829496.52791544)') ) foo (g); SELECT TopoGeo_AddLinestring('bug3464', 'LINESTRING(634446.780374345 4829591.16223176,634451.78032304 4829559.16248522,634485.780040461 4829525.1627442,634488.530017153 4829521.16277512)' ::geometry);
In this case we have a starting topology formed by 2 nodes and 2 edges almost parallel forming a single narrow face. The face has an area of 0.0186 units and a perimeter of 166.81 units. Each edge has 3 vertices so the face has a total of 4 vertices (2 common edge endpoints and 2 differenti interior edge vertices).
The line being added is also almost collinear. It has 4 vertices, one of which falling within the tiny face.
Changed 6 years ago by
Attachment: | start_topo.png added |
---|
starting topology, 2 nodes, 2 edges, 1 tiny face
Changed 6 years ago by
Attachment: | added_edge.png added |
---|
line being added to the topology, 3rd vertex counting from the top falls within the face
comment:5 Changed 6 years ago by
comment:6 Changed 6 years ago by
NOTE: specifying a tolerance of 1e-5 on import makes the line successfully added.
comment:7 Changed 6 years ago by
(the distance between the upper intersection and the upper face vertex is 0.8e5)
comment:8 Changed 6 years ago by
The line being added crosses the existing edges 4 times:
- Crosses the upper edge near its starting node going inside the face
- Crosses the lower edge near its starting node going outside the face
- Crosses the lower edge going inside the face near its centroid
- Crosses the lower edge going outside the face near its centroid
Theoretically this would require splitting the line into 5 parts, but the internal noding step splits the line into 4 parts instead, using a _single_ node in the upper side, rather than 2:
psql:crash_smaller.sql:2: DEBUG: [lwgeom_topo.c:lwt_AddLine:5876] Finally-noded: MULTILINESTRING((634446.780374345 4829591.16223176,634451.780306051 4829559.16259395),(634451.780306051 4829559.16259395,634451.78032304 4829559.16248522,634469.462472354 4829541.48032363),(634469.462472354 4829541.48032363,634485.780040461 4829525.1627442,634485.781473602 4829525.16065963),(634485.781473602 4829525.16065963,634488.530017153 4829521.16277512))
I hadn't checked if this is due to snap-rounding happening on the GEOS side but for sure it must not be easy (if possible at all) to represent such a small line. I cannot use QGIS to measure the distance between the edges near the intersection point as it doesnt' let me zoom in more than 50,000:1, and at that scale I cannot see the edges ever disjoint.
comment:9 Changed 6 years ago by
The responsibiliy of the missing split is ST_Difference. Basically this operation:
SELECT ST_Difference( '010200000004000000E5398D8F9D5C2341520162CA656C52416280868FA75C2341682866CA5D6C52419B76618FEB5C2341A6666A4A556C524185685E0FF15C234156E86A4A546C5241' ::geometry, '0107000000020000000102000000030000004A7B838FA75C2341D50968CA5D6C5241F6285C8FEB5C234143AD694A556C5241A2B0DFEB145D2341D75DC9214E6C52410102000000030000004A7B838FA75C2341D50968CA5D6C5241F6285C8FEB5C23411FF46C4A556C5241A2B0DFEB145D2341D75DC9214E6C5241' ::geometry);
That is the difference between the input line and the collection of existing edges.
comment:10 Changed 6 years ago by
When adding the second component of the 4 components in which the original line is split, the algorithm in trunk (and 2.2) fails to find it crossing an existing edge. In PostGIS-2.2.1 it is actually found crossing (SQL/MM Spatial exception - geometry crosses edge 2).
It occurs to me that the "crossing" could actually be determined by looking at the left/right faces as computed looking at the starting node and at the ending node. I might finally got to understand the concept of "side-location conflict" that's often thrown by GEOS/JTS.
Dr Martin are you listening ? :)
comment:11 Changed 6 years ago by
I confirm the possibility to check the occurrence by looking at start and end node analysis:
psql:bug3464.sql:21: NOTICE: Side-location conflict: left face of new edge should be 1 according to start node edges and 0 according to end node edges
comment:12 Changed 6 years ago by
While I believe we found a great way to catch edge-crossing occurrences by looking at topological info, I'm wondering why the spatial-based edge-crossing check did not catch this occurrence, as the second component does indeed come from the inside (from face 1) and then goes outside the face and back inside (from face 0).
comment:13 Changed 6 years ago by
comment:14 Changed 6 years ago by
So with r14690 I added the "side-location conflict" check, although with different wording:
psql:bug3464.sql:21: ERROR: corrupted topology: new edge starts in face 1 and ends in face 0
The message, as usual, doesn't really contain enough info to know what's going on, but the point is that the topology is found to be corrupted because the edge-adding function first checks for edge/edge crossing and finds none, but then finds that the edge started in a face and ended in another, according to topology metadata.
Now I suspect the edge-crossing check is giving a false negative here, because the topology isn't really invalid, but rather that component line is crossing (almost in parallel) an existing topology edge.
As the edge-crossing check uses Relate, there might be a bug in GEOS Relate, not finding a puntual intersection.
comment:15 Changed 6 years ago by
To summarize this issue, the problem derives from being unable to node that crosses a couple of edges which are almost parallel. The noding procedure (based on ST_Difference) gives us a correctly noded output BUT the correctly noded output makes the initial part of the two edges collapse on each other. When adding the new node to the topology (AddPoint?) we make no effort to handle the edge-collapsing.
What the algorithm does right now, on adding a new point, is just snapping the closest edge to the new node, rather than snapping _all_ edges below threshold and handling the collapses.
comment:17 Changed 3 months ago by
This bug still exists as of POSTGIS="3.2.0dev 3.1.0rc1-335-g392b5832a" with GEOS="3.10.0dev-CAPI-1.15.0"
Reported error is:
=# SELECT TopoGeo_AddLinestring('bug3463', 'LINESTRING(634452.780338203 4829623.16197433,634446.780374345 4829591.16223176,634451.78032304 4829559.16248522,634485.780040461 4829525.1627442,634488.530017153 4829521.16277512,634511.779820754 4829489.16302201,634523.779707286 4829439.16341655,632187.797669813 4827723.17794488,631718.05142978 4827788.42759019,631718.05144314 4827826.17728887,632759.754208638 4830776.16598454)' ::geometry); ERROR: Side-location conflict: new edge starts in face 1 and ends in face 0
The line being inserted gets split in 7 components. The first 3 components are successfully added to the topology via _lwtAddLineEdge, the 4th component triggers the exception.
Hacking the code to stop adding components after the 3rd allows me to take a look at the topology at that stage, and ValidateTopolgy? finds it invalid !
So _lwtAddLineEdge is evidently breaking the topology with adding one of those components.