Opened 8 years ago
Closed 7 years ago
Last modified 7 years ago
#3380 closed defect (fixed)
"geometry crosses edge" with 1e-2 tolerance
|Reported by:||strk||Owned by:||strk|
select DropTopology( 'shp_error' ); select CreateTopology( 'shp_error', 0, 0.01); SELECT TopoGeo_AddLinestring('shp_error', ' LINESTRING(1612923.15898333 4841265.48754979,1612938.15932297 4841257.23732472,1612951.65966041 4841253.73720287,1612933.90893005 4841222.98663562,1612915.65821091 4841195.23613226,1612910.65803504 4841190.23604794,1612893.65770428 4841206.23644001,1612881.65747637 4841218.23673119,1612871.65727827 4841227.23695322,1612855.65694177 4841239.23725902,1612844.65670832 4841247.23746406,1612823.40617483 4841252.48765035,1612825.90631516 4841261.48782605,1612829.90652844 4841274.48807845,1612830.15663807 4841287.23833953,1612883.15799825 4841277.73794915,1612923.15898333 4841265.48754979) ', 0); SELECT TopoGeo_AddLinestring('shp_error', ' LINESTRING(1612790.88055733 4841286.88526585,1612830.15823523 4841287.12674008,1612829.98813172 4841274.56198261,1612826.01679126 4841261.50572401,1612823.53033342 4841252.38787263,1612807.19309221 4841256.37344151,1612788.76059031 4841262.00356428,1612790.88055733 4841286.88526585) ', 0); SELECT TopoGeo_AddLinestring('shp_error', ' LINESTRING(1612830.15823523 4841287.12674008,1612883.09421571 4841277.62169028,1612923.13572292 4841265.39870628,1612938.06588219 4841257.24952328,1612951.63833096 4841253.85588049,1612934.02487406 4841223.09636279,1612915.65151363 4841195.23693069,1612910.65009963 4841190.23760515,1612893.64932937 4841206.23701923,1612881.64990281 4841218.23650212,1612871.64932278 4841227.23779269,1612855.64995596 4841239.23728901,1612844.64993299 4841247.23905436,1612823.53033342 4841252.38787263,1612826.01679126 4841261.50572401,1612829.98813172 4841274.56198261,1612830.15823523 4841287.12674008) ', 0);
Change History (21)
by , 8 years ago
comment:1 by , 8 years ago
comment:2 by , 8 years ago
|Milestone:||PostGIS 2.1.9 → PostGIS 2.0.8|
|Version:||2.1.x → 2.0.x|
2.0 is also affected
comment:3 by , 8 years ago
NOTE: the hypothetical fix is also already mentioned in a TODO item in code: https://trac.osgeo.org/postgis/browser/tags/2.2.0/liblwgeom/lwgeom_topo.c#L5649
comment:4 by , 8 years ago
Further reduction of the case, 3 lines of 3 vertices each:
SELECT DropTopology( 'shp_error' ); SELECT CreateTopology( 'shp_error', 0, 0.01); SELECT TopoGeo_AddLinestring('shp_error', ' LINESTRING( 1612829.90652844007126987 4841274.48807844985276461, 1612830.1566380700096488 4841287.23833953030407429, 1612883.15799825009889901 4841277.73794914968311787) ', 0); SELECT TopoGeo_AddLinestring('shp_error', ' LINESTRING( 1612790.88055733009241521 4841286.88526585046201944, 1612830.15823523001745343 4841287.12674008030444384, 1612829.98813172010704875 4841274.56198261026293039) ', 0); SELECT TopoGeo_AddLinestring('shp_error', ' LINESTRING( 1612830.15823523 4841287.12674008, 1612881.64990281 4841274.56198261, 1612883.09421571 4841223.09636279) ', 0);
The third line has an endpointi incident to node 8 in the figure above
by , 8 years ago
comment:5 by , 8 years ago
comment:6 by , 8 years ago
The final line can be also a single segment:
SELECT TopoGeo_AddLinestring('shp_error', ' LINESTRING( 1612830.15823523 4841287.12674008, 1612881.64990281 4841274.56198261) ', 0);
by , 8 years ago
comment:7 by , 8 years ago
From the logs, it is interesting to see that the input line (cyan above) snapped to the existing edges (all the rest) results in a line which extends to the existing node 4. Not that this should by itself matter at this stage, but it is something to keep in mind:
-- Snapping line to existing edges adds the overlapping segment [lwt_AddLine:5559] Snapped: LINESTRING(1612830.15444847 4841287.1267168,1612830.15823523 4841287.12674008,1612881.64990281 4841274.56198261)
Of further noding, we end up with a multilinestring formed by the two components: new line, overlapping line.
Now next step is snapping again this obtained multilinestring to the existing _NODES_. This time we only have the node to snap against, which is below tolerance. There is no edge vertex anymore to snap against, so the result is that while the overlapping line remains unchanged (one endpoint is already on the node), the other one gets his endpoint moved on the node too, introducing the crossing (with edge 4 in the picture below):
comment:8 by , 8 years ago
I'm not sure why we're snapping to existing _NODES_ again after having snapped to existing _EDGES_, since every existing node would already be part of an existing edge, so we should have snapped there already.
I suppose this was a workaround for some previously found robustness case whereas snapping to edge would move the input far enough that a second snap would snap more (as happens in this case).
comment:9 by , 8 years ago
Oh, this comment in code suggests that we're snapping to nodes because not every node is part of an edge:
/* 2.1. Node with existing nodes within tol * TODO: check if we should be only considering _isolated_ nodes! */ nodes = lwt_be_getNodeWithinBox2D( topo, &qbox, &num, LWT_COL_EDGE_ALL, 0 );
comment:10 by , 8 years ago
So, even if we do NOT snap to the non-isolated node, an error occurs in next step, when we add the correct new line to the topology and end up snapping its endpoint to the existing node even if it is coincident to an existing vertex of an edge (we do not check that occurrence).
In other words, the problem moves from TopoGeo_addLinestring to TopoGeom_addPoint, whereas the latter re-snaps. Maybe TopoGeo_addLinestring should _not_ call TopoGeom_addPoint, or call it with some custom parameters to avoid further re-snapping.
comment:11 by , 8 years ago
I'm thinking that the main problem here is that the "tolerance" is not fully enforced to avoid any two vertices of the topology are closer than such tolerance. In particular, after adding the second line, it is split in a way that leaves two consecutive points under the tolerance.
Once a tolerance is given, I think it should never allow to insert similar lines. I could try to remove the consecutive ones, but it might not be enough (and see #3388 about the consecutive ones)
comment:12 by , 8 years ago
I verified that removing consecutive vertices within tolerance after noding fixes this specific case, but I do know it's a non definitive fix yet. I'd also note that the removal makes the edge angle on the node even narrower, which means more trouble might arise later in the loading drive.
comment:13 by , 7 years ago
Removal of consecutive points within tolerance also triggers failures in the existing testsuite, like the following:
-#1714.2|E*|74 +ERROR: SQL/MM Spatial exception - curve not simple
The idea looks promising, but it'd take going trough each and every failing test to see what's going on (most of them might be different but still acceptable results, except the case above of non-simple curve)
comment:14 by , 7 years ago
Ok the non-simple exception is due to #3388
comment:15 by , 7 years ago
This PR fixes this ticket: https://github.com/postgis/postgis/pull/82 It changes the result of some other loading which needs to be carefully checked.
comment:16 by , 7 years ago
|Milestone:||PostGIS 2.0.8 → PostGIS 2.2.1|
|Priority:||medium → blocker|
comment:17 by , 7 years ago
|Status:||new → closed|
After loading the first two geometries node do exist that are closer than the given tolerance. Nodes 3 and 8 in the following image are 0.5e-2 units apart. Node 8 existed as a vertex of the second geometry added (formed by edges 3,5,12) while node 3 was created during import as the intersection between the second geometry and the first one (formed by edges 2 and 4).
There was no vertex where node 3 was created, so second geometry did not snap there. If we added all intersection points first and then re-snap linework against these new intersections, chances are this case would be fixed (in other words, use computed intersection points as snap references).