Doc Classic

Class DistanceOp

  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 package org.locationtech.jts.operation.distance;
 13  
 14 import java.util.List;
 15  
 16 import org.locationtech.jts.algorithm.Distance;
 17 import org.locationtech.jts.algorithm.PointLocator;
 18 import org.locationtech.jts.geom.Coordinate;
 19 import org.locationtech.jts.geom.Envelope;
 20 import org.locationtech.jts.geom.Geometry;
 21 import org.locationtech.jts.geom.LineSegment;
 22 import org.locationtech.jts.geom.LineString;
 23 import org.locationtech.jts.geom.Location;
 24 import org.locationtech.jts.geom.Point;
 25 import org.locationtech.jts.geom.Polygon;
 26 import org.locationtech.jts.geom.util.LinearComponentExtracter;
 27 import org.locationtech.jts.geom.util.PointExtracter;
 28 import org.locationtech.jts.geom.util.PolygonExtracter;
 29  
 30 /**
 31  * Find two points on two {@link Geometry}s which lie
 32  * within a given distance, or else are the nearest points
 33  * on the geometries (in which case this also
 34  * provides the distance between the geometries).
 35  * <p>
 36  * The distance computation also finds a pair of points in the input geometries
 37  * which have the minimum distance between them.
 38  * If a point lies in the interior of a line segment,
 39  * the coordinate computed is a close
 40  * approximation to the exact point.
 41  * <p>
 42  * Empty geometry collection components are ignored.
 43  * <p>
 44  * The algorithms used are straightforward O(n^2)
 45  * comparisons.  This worst-case performance could be improved on
 46  * by using Voronoi techniques or spatial indexes.
 47  *
 48  * @version 1.7
 49  */
 50 public class DistanceOp
 51 {
 52   /**
 53    * Compute the distance between the nearest points of two geometries.
 54    * @param g0 a {@link Geometry}
 55    * @param g1 another {@link Geometry}
 56    * @return the distance between the geometries
 57    */
 58   public static double distance(Geometry g0, Geometry g1)
 59   {
 60     DistanceOp distOp = new DistanceOp(g0, g1);
 61     return distOp.distance();
 62   }
 63  
 64   /**
 65    * Test whether two geometries lie within a given distance of each other.
 66    * @param g0 a {@link Geometry}
 67    * @param g1 another {@link Geometry}
 68    * @param distance the distance to test
 69    * @return true if g0.distance(g1) <= distance
 70    */
 71   public static boolean isWithinDistance(Geometry g0, Geometry g1, double distance)
 72   {
 73     // check envelope distance for a short-circuit negative result
 74     double envDist = g0.getEnvelopeInternal().distance(g1.getEnvelopeInternal());
 75     if (envDist > distance)
 76       return false;
 77  
 78     // MD - could improve this further with a positive short-circuit based on envelope MinMaxDist
 79     
 80     DistanceOp distOp = new DistanceOp(g0, g1, distance);
 81     return distOp.distance() <= distance;
 82   }
 83  
 84   /**
 85    * Compute the the nearest points of two geometries.
 86    * The points are presented in the same order as the input Geometries.
 87    *
 88    * @param g0 a {@link Geometry}
 89    * @param g1 another {@link Geometry}
 90    * @return the nearest points in the geometries
 91    */
 92   public static Coordinate[] nearestPoints(Geometry g0, Geometry g1)
 93   {
 94     DistanceOp distOp = new DistanceOp(g0, g1);
 95     return distOp.nearestPoints();
 96   }
 97  
 98   /**
 99    * Compute the the closest points of two geometries.
100    * The points are presented in the same order as the input Geometries.
101    *
102    * @param g0 a {@link Geometry}
103    * @param g1 another {@link Geometry}
104    * @return the closest points in the geometries
105    * @deprecated renamed to nearestPoints
106    */
107   public static Coordinate[] closestPoints(Geometry g0, Geometry g1)
108   {
109     DistanceOp distOp = new DistanceOp(g0, g1);
110     return distOp.nearestPoints();
111   }
112  
113   // input
114   private Geometry[] geom;
115   private double terminateDistance = 0.0;
116   // working
117   private PointLocator ptLocator = new PointLocator();
118   private GeometryLocation[] minDistanceLocation;
119   private double minDistance = Double.MAX_VALUE;
120  
121   /**
122    * Constructs a DistanceOp that computes the distance and nearest points between
123    * the two specified geometries.
124    * @param g0 a Geometry
125    * @param g1 a Geometry
126    */
127   public DistanceOp(Geometry g0, Geometry g1)
128   {
129     this(g0, g1, 0.0);
130   }
131  
132   /**
133    * Constructs a DistanceOp that computes the distance and nearest points between
134    * the two specified geometries.
135    * @param g0 a Geometry
136    * @param g1 a Geometry
137    * @param terminateDistance the distance on which to terminate the search
138    */
139   public DistanceOp(Geometry g0, Geometry g1, double terminateDistance)
140   {
141     this.geom = new Geometry[2];
142     geom[0] = g0;
143     geom[1] = g1;
144     this.terminateDistance = terminateDistance;
145   }
146  
147   /**
148    * Report the distance between the nearest points on the input geometries.
149    *
150    * @return the distance between the geometries
151    * or 0 if either input geometry is empty
152    * @throws IllegalArgumentException if either input geometry is null
153    */
154   public double distance()
155   {
156       if (geom[0] == null || geom[1] == null)
157           throw new IllegalArgumentException("null geometries are not supported");
158       if (geom[0].isEmpty() || geom[1].isEmpty()) 
159           return 0.0;
160       
161     computeMinDistance();
162     return minDistance;
163   }
164  
165   /**
166    * Report the coordinates of the nearest points in the input geometries.
167    * The points are presented in the same order as the input Geometries.
168    *
169    * @return a pair of {@link Coordinate}s of the nearest points
170    */
171   public Coordinate[] nearestPoints()
172   {
173     computeMinDistance();
174     Coordinate[] nearestPts
175         = new Coordinate[] {
176           minDistanceLocation[0].getCoordinate(),
177           minDistanceLocation[1].getCoordinate() };
178     return nearestPts;
179   }
180   
181   /**
182    * 
183    * @return a pair of {@link Coordinate}s of the nearest points
184    * @deprecated renamed to nearestPoints
185    */
186   public Coordinate[] closestPoints()
187   {
188     return nearestPoints();
189   }
190  
191   /**
192    * Report the locations of the nearest points in the input geometries.
193    * The locations are presented in the same order as the input Geometries.
194    *
195    * @return a pair of {@link GeometryLocation}s for the nearest points
196    */
197   public GeometryLocation[] nearestLocations()
198   {
199     computeMinDistance();
200     return minDistanceLocation;
201   }
202  
203   /**
204    * 
205    * @return a pair of {@link GeometryLocation}s for the nearest points
206    * @deprecated renamed to nearestLocations
207    */
208   public GeometryLocation[] closestLocations()
209   {
210     return nearestLocations();
211   }
212  
213   private void updateMinDistance(GeometryLocation[] locGeom, boolean flip)
214   {
215     // if not set then don't update
216     if (locGeom[0] == null) return;
217  
218     if (flip) {
219       minDistanceLocation[0] = locGeom[1];
220       minDistanceLocation[1] = locGeom[0];
221     }
222     else {
223       minDistanceLocation[0] = locGeom[0];
224       minDistanceLocation[1] = locGeom[1];
225     }
226   }
227  
228   private void computeMinDistance()
229   {
230     // only compute once!
231     if (minDistanceLocation != null) return;
232  
233     minDistanceLocation = new GeometryLocation[2];
234     computeContainmentDistance();
235     if (minDistance <= terminateDistance) return;
236     computeFacetDistance();
237   }
238  
239   private void computeContainmentDistance()
240   {
241     GeometryLocation[] locPtPoly = new GeometryLocation[2];
242     // test if either geometry has a vertex inside the other
243     computeContainmentDistance(0, locPtPoly);
244     if (minDistance <= terminateDistance) return;
245     computeContainmentDistance(1, locPtPoly);
246   }
247   
248   private void computeContainmentDistance(int polyGeomIndex, GeometryLocation[] locPtPoly)
249   {
250     Geometry polyGeom = geom[polyGeomIndex];
251     // if no polygon then nothing to do
252     if (polyGeom.getDimension() < 2) return;
253     
254       int locationsIndex = 1 - polyGeomIndex;
255     List polys = PolygonExtracter.getPolygons(polyGeom);
256     if (polys.size() > 0) {
257       List insideLocs = ConnectedElementLocationFilter.getLocations(geom[locationsIndex]);
258       computeContainmentDistance(insideLocs, polys, locPtPoly);
259       if (minDistance <= terminateDistance) {
260           // this assigment is determined by the order of the args in the computeInside call above
261         minDistanceLocation[locationsIndex] = locPtPoly[0];
262         minDistanceLocation[polyGeomIndex]     = locPtPoly[1];
263         return;
264       }
265     }    
266   }
267   
268   private void computeContainmentDistance(List locs, List polys, GeometryLocation[] locPtPoly)
269   {
270     for (int i = 0; i < locs.size(); i++) {
271       GeometryLocation loc = (GeometryLocation) locs.get(i);
272       for (int j = 0; j < polys.size(); j++) {
273           computeContainmentDistance(loc, (Polygon) polys.get(j), locPtPoly);
274         if (minDistance <= terminateDistance) return;
275       }
276     }
277   }
278  
279   private void computeContainmentDistance(GeometryLocation ptLoc,
280       Polygon poly,
281       GeometryLocation[] locPtPoly)
282   {
283     Coordinate pt = ptLoc.getCoordinate();
284     // if pt is not in exterior, distance to geom is 0
285     if (Location.EXTERIOR != ptLocator.locate(pt, poly)) {
286       minDistance = 0.0;
287       locPtPoly[0] = ptLoc;
288       locPtPoly[1] = new GeometryLocation(poly, pt);;
289       return;
290     }
291   }
292  
293   /**
294    * Computes distance between facets (lines and points)
295    * of input geometries.
296    *
297    */
298   private void computeFacetDistance()
299   {
300     GeometryLocation[] locGeom = new GeometryLocation[2];
301  
302     /**
303      * Geometries are not wholely inside, so compute distance from lines and points
304      * of one to lines and points of the other
305      */
306     List lines0 = LinearComponentExtracter.getLines(geom[0]);
307     List lines1 = LinearComponentExtracter.getLines(geom[1]);
308  
309     List pts0 = PointExtracter.getPoints(geom[0]);
310     List pts1 = PointExtracter.getPoints(geom[1]);
311  
312     // exit whenever minDistance goes LE than terminateDistance
313     computeMinDistanceLines(lines0, lines1, locGeom);
314     updateMinDistance(locGeom, false);
315     if (minDistance <= terminateDistance) return;
316  
317     locGeom[0] = null;
318     locGeom[1] = null;
319     computeMinDistanceLinesPoints(lines0, pts1, locGeom);
320     updateMinDistance(locGeom, false);
321     if (minDistance <= terminateDistance) return;
322  
323     locGeom[0] = null;
324     locGeom[1] = null;
325     computeMinDistanceLinesPoints(lines1, pts0, locGeom);
326     updateMinDistance(locGeom, true);
327     if (minDistance <= terminateDistance) return;
328  
329     locGeom[0] = null;
330     locGeom[1] = null;
331     computeMinDistancePoints(pts0, pts1, locGeom);
332     updateMinDistance(locGeom, false);
333   }
334  
335   private void computeMinDistanceLines(List lines0, List lines1, GeometryLocation[] locGeom)
336   {
337     for (int i = 0; i < lines0.size(); i++) {
338       LineString line0 = (LineString) lines0.get(i);
339       for (int j = 0; j < lines1.size(); j++) {
340         LineString line1 = (LineString) lines1.get(j);
341         computeMinDistance(line0, line1, locGeom);
342         if (minDistance <= terminateDistance) return;
343       }
344     }
345   }
346  
347   private void computeMinDistancePoints(List points0, List points1, GeometryLocation[] locGeom)
348   {
349     for (int i = 0; i < points0.size(); i++) {
350       Point pt0 = (Point) points0.get(i);
351       for (int j = 0; j < points1.size(); j++) {
352         Point pt1 = (Point) points1.get(j);
353         double dist = pt0.getCoordinate().distance(pt1.getCoordinate());
354         if (dist < minDistance) {
355           minDistance = dist;
356           locGeom[0] = new GeometryLocation(pt0, 0, pt0.getCoordinate());
357           locGeom[1] = new GeometryLocation(pt1, 0, pt1.getCoordinate());
358         }
359         if (minDistance <= terminateDistance) return;
360       }
361     }
362   }
363  
364   private void computeMinDistanceLinesPoints(List lines, List points,
365       GeometryLocation[] locGeom)
366   {
367     for (int i = 0; i < lines.size(); i++) {
368       LineString line = (LineString) lines.get(i);
369       for (int j = 0; j < points.size(); j++) {
370         Point pt = (Point) points.get(j);
371         computeMinDistance(line, pt, locGeom);
372         if (minDistance <= terminateDistance) return;
373       }
374     }
375   }
376  
377   private void computeMinDistance(LineString line0, LineString line1,
378                                   GeometryLocation[] locGeom)
379   {
380     if (line0.getEnvelopeInternal().distance(line1.getEnvelopeInternal())
381         > minDistance)
382           return;
383     Coordinate[] coord0 = line0.getCoordinates();
384     Coordinate[] coord1 = line1.getCoordinates();
385       // brute force approach!
386     for (int i = 0; i < coord0.length - 1; i++) {
387       
388       // short-circuit if line segment is far from line
389       Envelope segEnv0 = new Envelope(coord0[i], coord0[i + 1]);
390       if (segEnv0.distance(line1.getEnvelopeInternal()) > minDistance)
391         continue;
392       
393       for (int j = 0; j < coord1.length - 1; j++) {
394         
395         // short-circuit if line segments are far apart
396         Envelope segEnv1 = new Envelope(coord1[j], coord1[j + 1]);
397         if (segEnv0.distance(segEnv1) > minDistance)
398           continue;
399  
400         double dist = Distance.segmentToSegment(
401                                         coord0[i], coord0[i + 1],
402                                         coord1[j], coord1[j + 1] );
403         if (dist < minDistance) {
404           minDistance = dist;
405           LineSegment seg0 = new LineSegment(coord0[i], coord0[i + 1]);
406           LineSegment seg1 = new LineSegment(coord1[j], coord1[j + 1]);
407           Coordinate[] closestPt = seg0.closestPoints(seg1);
408           locGeom[0] = new GeometryLocation(line0, i, closestPt[0]);
409           locGeom[1] = new GeometryLocation(line1, j, closestPt[1]);
410         }
411         if (minDistance <= terminateDistance) return;
412       }
413     }
414   }
415  
416   private void computeMinDistance(LineString line, Point pt,
417                                   GeometryLocation[] locGeom)
418   {
419     if (line.getEnvelopeInternal().distance(pt.getEnvelopeInternal())
420         > minDistance)
421           return;
422     Coordinate[] coord0 = line.getCoordinates();
423     Coordinate coord = pt.getCoordinate();
424       // brute force approach!
425     for (int i = 0; i < coord0.length - 1; i++) {
426         double dist = Distance.pointToSegment(
427             coord, coord0[i], coord0[i + 1] );
428         if (dist < minDistance) {
429           minDistance = dist;
430           LineSegment seg = new LineSegment(coord0[i], coord0[i + 1]);
431           Coordinate segClosestPoint = seg.closestPoint(coord);
432           locGeom[0] = new GeometryLocation(line, i, segClosestPoint);
433           locGeom[1] = new GeometryLocation(pt, 0, coord);
434         }
435         if (minDistance <= terminateDistance) return;
436  
437     }
438   }
439  
440 }
441  
442