Snap operation: wrong snapping

[aperi2007]

Hi I notice, using postgis that the Snap algoritm sometimes will wrong to snap geometries causing the born of invalid polygon or disallowing polygon otherwise perfectly touching each other.

To produce a test-case I use linestrings

Starting with this two linestrings:

The geometry to snap (two only vertex) SELECT ST_GeomFromText('LINESTRING(0 0, 10 0)');

Image:

*--------------------*

And the geometry used as reference (4 vertex) SELECT ST_GeomFromText('LINESTRING(0 0, 9 0, 10 0, 11 0)');

Image:

*-----------------*--*--*

Please notice every vertex has a distance of 1 or more from other vertexs. And notice also the first geometry has its vertexs coords exactly as in the second geometry.

Now I try to snap the first geometry on the second (the reference geometry) with a buffer of 2 meters:

Select ST_AsText(ST_Snap(ST_GeomFromText('LINESTRING(0 0, 10 0)'),ST_GeomFromText('LINESTRING(0 0, 9 0, 10 0, 11 0)'),2));

I see that the result is: LINESTRING(0 0,11 0,10 0,9 0)

Image:

*----------->--->-----*

*-<-*

I guess this is really a bug.

I guess the right result should be always: LINESTRING(0 0, 10 0)

Or also I guess another valid result could be this LINESTRING(0 0,9 0,10 0) Where I admit the snap was for segment.

---

Perhaps an optional fourth parameter could allow choose if snap for "segments" or for "vertex", and default to "segment" because surely it is the more useful.

---

However surely the result the Snap give at now: LINESTRING(0 0,11 0,10 0,9 0) is no the right result.

I don't know how the Snap algorithm work, but I guess It seem to stop at the first vertex inside the buffer interval. I guess it should be search always the nearest vertex . So it will find that there is a vertex on exactly the same coords (10 0) and so it will produce a result like Linestring(0 0, I guess the Snap() method should always search the nearest vertex instead of stop to the first vertex inside the buffer interval.

If it search go to find the nearest vertex it will find that there is a vertex exactly on the same coords (10 0), and so it will give as result

ST_Snap('LINESTRING(0 0, 10 0)', LINESTRING(0 0, 9 0, 10 0, 11 0), 2) = LINESTRING(0 0, 9 0, 10 0) (for segment) ST_Snap('LINESTRING(0 0, 10 0)', LINESTRING(0 0, 9 0, 10 0, 11 0), 2) = LINESTRING(0 0, 10 0) (for vertex)

---

Thx, Andrea.

[strk]

testcase for JTS, also fails there

[strk]

The case also fails with JTS. It's a known limitation of the snapping code, quoting from the documentation:

 * Too much snapping can result in invalid topology
 * being created, so the number and location of snapped vertices
 * is decided using heuristics to determine when it
 * is safe to snap.

[strk]

In any case, here's the ticket filed for JTS:

 https://sourceforge.net/tracker/?func=detail&aid=3458092&group_id=128875&atid=713120

I also belive it could be possible to handle this case better.

[strk]

The issue is with segments snapping, not point snapping. Here's some debugging output:

Snapping segment from: (0 0, 10 0)
Checking for a segment to snap to snapPt 0 0
 Checking segment LINESEGMENT(0 0,10 0) for snapping against point 0 0
 One of segment endpoints equal snap point, returning too_far
 No segment to snap
Checking for a segment to snap to snapPt 9 0
 Checking segment LINESEGMENT(0 0,10 0) for snapping against point 9 0
 dist=0 minDist=3 snapTolerance=2
 Segment/snapPt distance within tolerance and closer then previous match (0) 
 Segment to be snapped found, inserting point
Checking for a segment to snap to snapPt 10 0
 Checking segment LINESEGMENT(0 0,9 0) for snapping against point 10 0
 dist=1 minDist=3 snapTolerance=2
 Segment/snapPt distance within tolerance and closer then previous match (1) 
 Checking segment LINESEGMENT(9 0,10 0) for snapping against point 10 0
 One of segment endpoints equal snap point, returning too_far
 No segment to snap
Checking for a segment to snap to snapPt 11 0
 Checking segment LINESEGMENT(0 0,9 0) for snapping against point 11 0
 dist=2 minDist=3 snapTolerance=2
 Checking segment LINESEGMENT(9 0,10 0) for snapping against point 11 0
 dist=1 minDist=3 snapTolerance=2
 Segment/snapPt distance within tolerance and closer then previous match (1) 
 Segment to be snapped found, inserting point
 After segment snapping, srcCoors are: (0 0, 9 0, 11 0, 10 0)

The last run seems bogus, highlighted here:

Checking for a segment to snap to snapPt 11 0
 Checking segment LINESEGMENT(0 0,9 0) for snapping against point 11 0
 dist=2 minDist=3 snapTolerance=2
 Checking segment LINESEGMENT(9 0,10 0) for snapping against point 11 0
 dist=1 minDist=3 snapTolerance=2
 Segment/snapPt distance within tolerance and closer then previous match (1) 
 Segment to be snapped found, inserting point
 After segment snapping, srcCoors are: (0 0, 9 0, 11 0, 10 0)

If it was second point (10, 0) snapped rather than first point (9, 0) there would have been no problem. The code says:

    // insert must happen one-past first point (before next point)

So it is intentional to snap the actual segment rather than the existing vertices. Only maybe it should be avoided when one of the endpoints is the closer part of the segment to the snap point.

[strk]

I've been thinking that vertex snapping could maybe be performed against the _farest_ point within tolerance rather than the closest one. And the fartest from segment startpoint. Doing so should ensure that later segment snapping would not introduce overstrikes.

Surely needs more thinking and presentation of a set of cases

[aperi2007]

Please, I guess this other case is really more understandable :) ( a little difference between the vertex of the lines to help to understand if the vertex choose is from line1 or line2 )

ST_Snap(
        'LINESTRING(0 0, 10 0)', 
         LINESTRING(0.1 0, 9.1 0, 10.01 0, 10.9 0), 
         2
) = LINESTRING(0.1 0, 10.9 0, 10.01 0, 9.1 0) 

Please, can you repeat your debug output with this ?

[strk]

First vertices are snapped:

Checking for a snap for source coordinate 0 0
 misuring distance between snap point 0.1 0 and source point 0 0
 points are within distance (0.1) returning iterator to snap point
 Found snap point 0.1 0
 Source point became 0.1 0

Checking for a snap for source coordinate 10 0
 misuring distance between snap point 0.1 0 and source point 10 0
 misuring distance between snap point 9.1 0 and source point 10 0
 points are within distance (0.9) returning iterator to snap point
 Found snap point 9.1 0
 Source point became 9.1 0

Then segments are snapped:

Snapping segment from: (0.1 0, 9.1 0)
 Checking for a segment to snap to snapPt 0.1 0
  Checking segment LINESEGMENT(0.1 0,9.1 0) for snapping against point 0.1 0
   One of segment endpoints equal snap point, returning too_far
   No segment to snap
 Checking for a segment to snap to snapPt 9.1 0
  Checking segment LINESEGMENT(0.1 0,9.1 0) for snapping against point 9.1 0
   One of segment endpoints equal snap point, returning too_far
   No segment to snap
 Checking for a segment to snap to snapPt 10.01 0
  Checking segment LINESEGMENT(0.1 0,9.1 0) for snapping against point 10.01 0
   dist=0.91 minDist=3 snapTolerance=2
   Segment/snapPt distance within tolerance and closer then previous match (0.91) 
   Segment to be snapped found, inserting point
 Checking for a segment to snap to snapPt 10.9 0
  Checking segment LINESEGMENT(0.1 0,10.01 0) for snapping against point 10.9 0
   dist=0.89 minDist=3 snapTolerance=2
   Segment/snapPt distance within tolerance and closer then previous match (0.89) 
  Checking segment LINESEGMENT(10.01 0,9.1 0) for snapping against point 10.9 0
   dist=0.89 minDist=0.89 snapTolerance=2
   Segment to be snapped found, inserting point
After segment snapping, srcCoors are: (0.1 0, 10.9 0, 10.01 0, 9.1 0)

[strk]

I report a schema of the problem described in the bug.

The input (A-B) and the snap points (S1,S2):

 A            B    S2 
 *------------*    *
             S1

The figure produced by current algorithm (A-S2-B):

 A            B    S2             
 *------------*<-->*              
              S1                  

The above happens because vertex snapping for B gives up when finding S1 being == B and later segment snapping finds S2 first (for some reason) and thus produces the invalid overstrike. Note that inverting the order of S1 and S2 in input fixes the issue:

=# select st_astext(st_snap('LINESTRING(0 0, 10 0)', 'MULTIPOINT(10 0, 11 0)', 2));
         st_astext         
---------------------------
 LINESTRING(0 0,11 0,10 0)


=# select st_astext(st_snap('LINESTRING(0 0, 10 0)', 'MULTIPOINT(11 0, 10 0)', 2));
         st_astext         
---------------------------
 LINESTRING(0 0,10 0,11 0)

[strk]

I shall notice that the bug above would be fixed if we snapped to the _closest_ snap point.