Almost collinear edges prevent adding a copy of existing edge

[strk]

Here is the input:

0102000020BB0B000002000000EC51B89E320F3841333333B3A9C8524114AE47611D0F384114AE47B17DC85241
0102000020BB0B000003000000EC51B89E320F3841333333B3A9C852415649EE1F280F384164E065F493C85241A4703D8A230F38410AD7A37094C85241

Entering the 2-vertices line (first one) before the 3-vertices line in a topology results in a topology with 4 nodes and 2 edges. Adding the 2-vertices line again (copy of one of the 2 edges) fails with:

ERROR: Spatial exception - geometry intersects edge 2

[strk]

topology state after adding first and second line

[strk]

topology state after adding second and first line (order matters)

[strk]

Note that adding the 3-vertices line _before_ the 2-vertices line results in a different topology which does not prevent adding the 2-vertices line again.

State of topology after adding straight line first:

State of topology after adding straight line second:

[strk]

The problem is that on adding the straight line again, it first gets noded to existing edges with a tolerance computed based on minimum representable number in the floating point grid. The snapping ends up "splitting" the straight line where the other line goes away. Later, on adding the new node, existing edges gets snapped to it, and thus the existing straight edge is moved to intersect the other close edge.

The solution would seem to be to not only snap existing edges to new nodes but also to new or modified edges. As usual this can only work consistently if the tolerance value is constant over all operations, and if the input is guaranteed to fall on that given grid.

[strk]

It's to be noted that the center vertex of the L-shaped line is so close to the straight line that ST_Distance returns 0, still ST_Within returns false:

strk=# select ST_Distance(ST_PointN(e11.geom, 2), e10.geom) from bug3280.edge e11, bug3280.edge e10 where e11.edge_id = 11 and e10.edge_id = 10;
 st_distance 
-------------
           0
(1 row)

strk=# select ST_Within(ST_PointN(e11.geom, 2), e10.geom) from bug3280.edge e11, bug3280.edge e10 where e11.edge_id = 11 and e10.edge_id = 10;
 st_within 
-----------
 f
(1 row)

[strk]

I think this case would succeed if we were able to order intersecting edges by their distance, but unfortunately the fully-containing and the not-containing edges are both found to be at distance 0 from the reference point:

strk=# SELECT st_distance('01010000005649EE1F280F384164E065F493C85241'::geometry, geom), edge_id,geom FROM "bug3280".edge_data WHERE ST_DWithin('01010000005649EE1F280F384164E065F493C85241'::geometry, geom, 1.77267e-08) order by st_distance('01010000005649EE1F280F384164E065F493C85241'::geometry, geom);
 st_distance | edge_id |                                                        geom                                                        
-------------+---------+--------------------------------------------------------------------------------------------------------------------
           0 |       1 | 010200000002000000EC51B89E320F3841333333B3A9C8524114AE47611D0F384114AE47B17DC85241
           0 |       2 | 010200000003000000EC51B89E320F3841333333B3A9C852415649EE1F280F384164E065F493C85241A4703D8A230F38410AD7A37094C85241
(2 rows)

So how to force the longer edge (the one containing the point) to be handled first ? @nicklas note that GEOS finds the query point at a distance of ~5e-11 from the point. Not sure how that happens to work, exactly (is ST_Distance using some tolerance?)

[strk]

proposed patch

[strk]

The attached patch 0001-Improve-robustness-of-adding-points-to-topology-3280.patch tries to find an "easier" edge to snap to, in case multiple ones are within distance. It solves this specific case.

[strk]

NOTE: the patch is for 2.2.0dev, not for 2.1 (now the implementation is so different that it is not that easy to backport, C vs. plpgsql)

[strk]

actually, the proposed patch crashes the backend, I'll work some more on it

[strk]

patch for the 2.1 branch

[strk]

The patch for the 2.1 branch is crash-free and confirms the approach works: 0001-Improve-robustness-of-adding-points-to-topology-3280-pg21.patch​

[strk]

r14152 applies the patch to the 2.1 branch (for 2.1.9), including testcase. it'll take some time to fix the port in trunk (2.2.0), due to possibly already existing memory issues

[strk]

so it looks like the segfault was due to something extraneous, but the 2.2 patch still need more tweaks as it's missing an ORDER BY in comparison with the 2.1 implementation, which makes the algorithm (also the present one) not correct.

I'll set target to 2.2.0 and blocker for now, so we don't release before fixing this, which is a regression (even if I don't have a test handy to show the regressing part).

[strk]

Alright, I'm happy with trunk as of r14155 -- beside the fix added to 2.1, trunk also needed to conform by sorting the close-by nodes and edges by distance, which was lost in the port to C.