Opened 9 years ago

Closed 9 years ago

#3280 closed defect (fixed)

Almost collinear edges prevent adding a copy of existing edge

Reported by: strk Owned by: strk
Priority: blocker Milestone: PostGIS 2.1.9
Component: topology Version: 2.0.x
Keywords: robustness Cc: nicklas

Description

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

Attachments (4)

testbug-error.png (14.5 KB ) - added by strk 9 years ago.
topology state after adding first and second line
testbug-noerror.png (15.0 KB ) - added by strk 9 years ago.
topology state after adding second and first line (order matters)
0001-Improve-robustness-of-adding-points-to-topology-3280.patch (2.9 KB ) - added by strk 9 years ago.
proposed patch
0001-Improve-robustness-of-adding-points-to-topology-3280-pg21.patch (1.1 KB ) - added by strk 9 years ago.
patch for the 2.1 branch

Download all attachments as: .zip

Change History (17)

by strk, 9 years ago

Attachment: testbug-error.png added

topology state after adding first and second line

by strk, 9 years ago

Attachment: testbug-noerror.png added

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

comment:1 by strk, 9 years ago

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: topology state after adding first and second line

State of topology after adding straight line second: topology state after adding second and first line (order matters)

comment:2 by strk, 9 years ago

Keywords: robustness added

comment:3 by strk, 9 years ago

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.

comment:4 by strk, 9 years ago

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)

comment:5 by strk, 9 years ago

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

comment:6 by strk, 9 years ago

Cc: nicklas added

comment:7 by strk, 9 years ago

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.

comment:8 by strk, 9 years ago

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)

comment:9 by strk, 9 years ago

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

by strk, 9 years ago

patch for the 2.1 branch

comment:10 by strk, 9 years ago

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​

comment:11 by strk, 9 years ago

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

comment:12 by strk, 9 years ago

Milestone: PostGIS 2.1.9PostGIS 2.2.0
Priority: mediumblocker
Status: newassigned

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

comment:13 by strk, 9 years ago

Milestone: PostGIS 2.2.0PostGIS 2.1.9
Resolution: fixed
Status: assignedclosed

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.

Note: See TracTickets for help on using tickets.