Doc Classic

Class LineStringSnapper

  1 /*
  2  * Copyright (c) 2016 Vivid Solutions.
  3  *
  4  * All rights reserved. This program and the accompanying materials
  5  * are made available under the terms of the Eclipse Public License 2.0
  6  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
  7  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
  8  * and the Eclipse Distribution License is available at
  9  *
 10  * http://www.eclipse.org/org/documents/edl-v10.php.
 11  */
 12  
 13 package org.locationtech.jts.operation.overlay.snap;
 14  
 15 import org.locationtech.jts.geom.Coordinate;
 16 import org.locationtech.jts.geom.CoordinateList;
 17 import org.locationtech.jts.geom.LineSegment;
 18 import org.locationtech.jts.geom.LineString;
 19  
 20 /**
 21  * Snaps the vertices and segments of a {@link LineString} 
 22  * to a set of target snap vertices.
 23  * A snap distance tolerance is used to control where snapping is performed.
 24  * <p>
 25  * The implementation handles empty geometry and empty snap vertex sets.
 26  *
 27  * @author Martin Davis
 28  * @version 1.7
 29  */
 30 public class LineStringSnapper
 31 {
 32   private double snapTolerance = 0.0;
 33  
 34   private Coordinate[] srcPts;
 35   private LineSegment seg = new LineSegment(); // for reuse during snapping
 36   private boolean allowSnappingToSourceVertices = false;
 37   private boolean isClosed = false;
 38  
 39   /**
 40    * Creates a new snapper using the points in the given {@link LineString}
 41    * as source snap points.
 42    * 
 43    * @param srcLine a LineString to snap (may be empty)
 44    * @param snapTolerance the snap tolerance to use
 45    */
 46   public LineStringSnapper(LineString srcLine, double snapTolerance)
 47   {
 48     this(srcLine.getCoordinates(), snapTolerance);
 49   }
 50  
 51   /**
 52    * Creates a new snapper using the given points
 53    * as source points to be snapped.
 54    * 
 55    * @param srcPts the points to snap 
 56    * @param snapTolerance the snap tolerance to use
 57    */
 58   public LineStringSnapper(Coordinate[] srcPts, double snapTolerance)
 59   {
 60     this.srcPts = srcPts;
 61     isClosed = isClosed(srcPts);
 62     this.snapTolerance = snapTolerance;
 63   }
 64  
 65   public void setAllowSnappingToSourceVertices(boolean allowSnappingToSourceVertices)
 66   {
 67     this.allowSnappingToSourceVertices = allowSnappingToSourceVertices;
 68   }
 69   private static boolean isClosed(Coordinate[] pts)
 70   {
 71     if (pts.length <= 1) return false;
 72     return pts[0].equals2D(pts[pts.length - 1]);
 73   }
 74   /**
 75    * Snaps the vertices and segments of the source LineString 
 76    * to the given set of snap vertices.
 77    * 
 78    * @param snapPts the vertices to snap to
 79    * @return a list of the snapped points
 80    */
 81   public Coordinate[] snapTo(Coordinate[] snapPts)
 82   {
 83     CoordinateList coordList = new CoordinateList(srcPts);
 84  
 85     snapVertices(coordList, snapPts);
 86     snapSegments(coordList, snapPts);
 87  
 88     Coordinate[] newPts = coordList.toCoordinateArray();
 89     return newPts;
 90   }
 91  
 92   /**
 93    * Snap source vertices to vertices in the target.
 94    * 
 95    * @param srcCoords the points to snap
 96    * @param snapPts the points to snap to
 97    */
 98   private void snapVertices(CoordinateList srcCoords, Coordinate[] snapPts)
 99   {
100     // try snapping vertices
101     // if src is a ring then don't snap final vertex
102     int end = isClosed ? srcCoords.size() - 1 : srcCoords.size();
103     for (int i = 0; i < end; i++) {
104       Coordinate srcPt = (Coordinate) srcCoords.get(i);
105       Coordinate snapVert = findSnapForVertex(srcPt, snapPts);
106       if (snapVert != null) {
107         // update src with snap pt
108         srcCoords.set(i, new Coordinate(snapVert));
109         // keep final closing point in synch (rings only)
110         if (i == 0 && isClosed)
111           srcCoords.set(srcCoords.size() - 1, new Coordinate(snapVert));
112       }
113     }
114   }
115  
116   private Coordinate findSnapForVertex(Coordinate pt, Coordinate[] snapPts)
117   {
118     for (int i = 0; i < snapPts.length; i++) {
119       // if point is already equal to a src pt, don't snap
120       if (pt.equals2D(snapPts[i]))
121         return null;
122       if (pt.distance(snapPts[i]) < snapTolerance)
123         return snapPts[i];
124     }
125     return null;
126   }
127  
128   /**
129    * Snap segments of the source to nearby snap vertices.
130    * Source segments are "cracked" at a snap vertex.
131    * A single input segment may be snapped several times 
132    * to different snap vertices.
133    * <p>
134    * For each distinct snap vertex, at most one source segment
135    * is snapped to.  This prevents "cracking" multiple segments 
136    * at the same point, which would likely cause 
137    * topology collapse when being used on polygonal linework.
138    * 
139    * @param srcCoords the coordinates of the source linestring to be snapped
140    * @param snapPts the target snap vertices
141    */
142   private void snapSegments(CoordinateList srcCoords, Coordinate[] snapPts)
143   {
144     // guard against empty input
145     if (snapPts.length == 0) return;
146     
147     int distinctPtCount = snapPts.length;
148  
149     // check for duplicate snap pts when they are sourced from a linear ring.  
150     // TODO: Need to do this better - need to check *all* snap points for dups (using a Set?)
151     if (snapPts[0].equals2D(snapPts[snapPts.length - 1]))
152         distinctPtCount = snapPts.length - 1;
153  
154     for (int i = 0; i < distinctPtCount; i++) {
155       Coordinate snapPt = snapPts[i];
156       int index = findSegmentIndexToSnap(snapPt, srcCoords);
157       /**
158        * If a segment to snap to was found, "crack" it at the snap pt.
159        * The new pt is inserted immediately into the src segment list,
160        * so that subsequent snapping will take place on the modified segments.
161        * Duplicate points are not added.
162        */
163       if (index >= 0) {
164         srcCoords.add(index + 1, new Coordinate(snapPt), false);
165       }
166     }
167   }
168  
169  
170   /**
171    * Finds a src segment which snaps to (is close to) the given snap point.
172    * <p>
173    * Only a single segment is selected for snapping.
174    * This prevents multiple segments snapping to the same snap vertex,
175    * which would almost certainly cause invalid geometry
176    * to be created.
177    * (The heuristic approach to snapping used here
178    * is really only appropriate when
179    * snap pts snap to a unique spot on the src geometry.)
180    * <p>
181    * Also, if the snap vertex occurs as a vertex in the src coordinate list,
182    * no snapping is performed.
183    * 
184    * @param snapPt the point to snap to
185    * @param srcCoords the source segment coordinates
186    * @return the index of the snapped segment
187    * or -1 if no segment snaps to the snap point
188    */
189   private int findSegmentIndexToSnap(Coordinate snapPt, CoordinateList srcCoords)
190   {
191     double minDist = Double.MAX_VALUE;
192     int snapIndex = -1;
193     for (int i = 0; i < srcCoords.size() - 1; i++) {
194       seg.p0 = (Coordinate) srcCoords.get(i);
195       seg.p1 = (Coordinate) srcCoords.get(i + 1);
196  
197       /**
198        * Check if the snap pt is equal to one of the segment endpoints.
199        * 
200        * If the snap pt is already in the src list, don't snap at all.
201        */
202       if (seg.p0.equals2D(snapPt) || seg.p1.equals2D(snapPt)) {
203         if (allowSnappingToSourceVertices)
204           continue;
205         else
206           return -1;
207       }
208       
209       double dist = seg.distance(snapPt);
210       if (dist < snapTolerance && dist < minDist) {
211         minDist = dist;
212         snapIndex = i;
213       }
214     }
215     return snapIndex;
216   }
217  
218 }
219