ERROR: lwt_ChangeEdgeGeom could not construct face X, on the left of edge Y

[strk]

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

[strk]

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 !

 ("face has no rings",1,)

So _lwtAddLineEdge is evidently breaking the topology with adding one of those components.

[strk]

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.

[strk]

starting topology, 2 nodes, 2 edges, 1 tiny face

[strk]

line being added to the topology, 3rd vertex counting from the top falls within the face

[strk]

Image of the starting topology:

With line being added:

[strk]

Detali of the upper zone

[strk]

Detail of the lower zone

[strk]

Detail of the middle zone

[strk]

Upper side, first segment crosses both edges near their start node:

Third line vertex is within the narrow face:

Final line vertex is outside the narrow face:

[strk]

NOTE: specifying a tolerance of 1e-5 on import makes the line successfully added.

[strk]

(the distance between the upper intersection and the upper face vertex is 0.8e5)

[strk]

The line being added crosses the existing edges 4 times:

1. Crosses the upper edge near its starting node going inside the face
2. Crosses the lower edge near its starting node going outside the face
3. Crosses the lower edge going inside the face near its centroid
4. 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.

[strk]

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.

[strk]

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

[strk]

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

[strk]

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

[strk]

(In [14690]) Check for side-location conflicts when adding a new edge

It is possible to trigger such failure adding an edge to a corrupted topology. Test added.

See #3464

[strk]

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.

[strk]

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.

[robe]

Milestone renamed

[strk]

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