Opened 4 years ago
Closed 4 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)
Change History (17)
Changed 4 years ago by
Attachment: | testbug-error.png added |
---|
Changed 4 years ago by
Attachment: | testbug-noerror.png added |
---|
topology state after adding second and first line (order matters)
comment:1 Changed 4 years ago by
comment:2 Changed 4 years ago by
Keywords: | robustness added |
---|
comment:3 Changed 4 years ago by
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 Changed 4 years ago by
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 Changed 4 years ago by
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 Changed 4 years ago by
Cc: | nicklas added |
---|
Changed 4 years ago by
Attachment: | 0001-Improve-robustness-of-adding-points-to-topology-3280.patch added |
---|
proposed patch
comment:7 Changed 4 years ago by
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 Changed 4 years ago by
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 Changed 4 years ago by
actually, the proposed patch crashes the backend, I'll work some more on it
Changed 4 years ago by
Attachment: | 0001-Improve-robustness-of-adding-points-to-topology-3280-pg21.patch added |
---|
patch for the 2.1 branch
comment:10 Changed 4 years ago by
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 Changed 4 years ago by
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 Changed 4 years ago by
Milestone: | PostGIS 2.1.9 → PostGIS 2.2.0 |
---|---|
Priority: | medium → blocker |
Status: | new → assigned |
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 Changed 4 years ago by
Milestone: | PostGIS 2.2.0 → PostGIS 2.1.9 |
---|---|
Resolution: | → fixed |
Status: | assigned → closed |
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.
topology state after adding first and second line