"geometry crosses edge" with 1e-2 tolerance

[strk]

Testcase:

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

[strk]

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

[strk]

2.0 is also affected

[strk]

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

[strk]

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

[strk]

Adding the cyan line to the existing topology triggers the error. The distance from the new edge endpoint and the existing node is half the tolerance.

[strk]

The final line can be also a single segment:

  SELECT TopoGeo_AddLinestring('shp_error', '                                   
   LINESTRING(                                                                  
  1612830.15823523 4841287.12674008,                                            
  1612881.64990281 4841274.56198261)                                            
  ', 0);   

[strk]

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

[strk]

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

[strk]

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

[strk]

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.

[strk]

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)

[strk]

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.

[strk]

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)

[strk]

Ok the non-simple exception is due to #3388

[strk]

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.

[strk]

(In [14542]) Decimate lines on topology load

Improves snapping robustness

Updates expected results in topogeo_addlinestring for old and new snapping code (GEOS-3.3.8-, GEOS-3.3.9+)

Fixes #3380 and #3402, including automated tests for them.

[strk]

r14542 in 2.2 branch (2.2.1), r14540 in trunk (2.3.0)