001: /*
002: * The JTS Topology Suite is a collection of Java classes that
003: * implement the fundamental operations required to validate a given
004: * geo-spatial data set to a known topological specification.
005: *
006: * Copyright (C) 2001 Vivid Solutions
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: * For more information, contact:
023: *
024: * Vivid Solutions
025: * Suite #1A
026: * 2328 Government Street
027: * Victoria BC V8T 5G5
028: * Canada
029: *
030: * (250)385-6040
031: * www.vividsolutions.com
032: */
033: package com.vividsolutions.jts.operation.distance;
034:
035: import java.util.*;
036: import com.vividsolutions.jts.geom.*;
037: import com.vividsolutions.jts.geom.util.*;
038: import com.vividsolutions.jts.algorithm.*;
039:
040: /**
041: * Find two points on two {@link Geometry}s which lie
042: * within a given distance, or else are the closest points
043: * on the geometries (in which case this also
044: * provides the distance between the geometries).
045: * <p>
046: * The distance computation also finds a pair of points in the input geometries
047: * which have the minimum distance between them.
048: * If a point lies in the interior of a line segment,
049: * the coordinate computed is a close
050: * approximation to the exact point.
051: * <p>
052: * The algorithms used are straightforward O(n^2)
053: * comparisons. This worst-case performance could be improved on
054: * by using Voronoi techniques or spatial indexes.
055: *
056: * @version 1.7
057: */
058: public class DistanceOp {
059: /**
060: * Compute the distance between the closest points of two geometries.
061: * @param g0 a {@link Geometry}
062: * @param g1 another {@link Geometry}
063: * @return the distance between the geometries
064: */
065: public static double distance(Geometry g0, Geometry g1) {
066: DistanceOp distOp = new DistanceOp(g0, g1);
067: return distOp.distance();
068: }
069:
070: /**
071: * Test whether two geometries lie within a given distance of each other.
072: * @param g0 a {@link Geometry}
073: * @param g1 another {@link Geometry}
074: * @param distance the distance to test
075: * @return true if g0.distance(g1) <= distance
076: */
077: public static boolean isWithinDistance(Geometry g0, Geometry g1,
078: double distance) {
079: DistanceOp distOp = new DistanceOp(g0, g1, distance);
080: return distOp.distance() <= distance;
081: }
082:
083: /**
084: * Compute the the closest points of two geometries.
085: * The points are presented in the same order as the input Geometries.
086: *
087: * @param g0 a {@link Geometry}
088: * @param g1 another {@link Geometry}
089: * @return the closest points in the geometries
090: */
091: public static Coordinate[] closestPoints(Geometry g0, Geometry g1) {
092: DistanceOp distOp = new DistanceOp(g0, g1);
093: return distOp.closestPoints();
094: }
095:
096: // input
097: private Geometry[] geom;
098: private double terminateDistance = 0.0;
099: // working
100: private PointLocator ptLocator = new PointLocator();
101: private GeometryLocation[] minDistanceLocation;
102: private double minDistance = Double.MAX_VALUE;
103:
104: /**
105: * Constructs a DistanceOp that computes the distance and closest points between
106: * the two specified geometries.
107: * @param g0 a Geometry
108: * @param g1 a Geometry
109: */
110: public DistanceOp(Geometry g0, Geometry g1) {
111: this (g0, g1, 0.0);
112: }
113:
114: /**
115: * Constructs a DistanceOp that computes the distance and closest points between
116: * the two specified geometries.
117: * @param g0 a Geometry
118: * @param g1 a Geometry
119: * @param terminateDistance the distance on which to terminate the search
120: */
121: public DistanceOp(Geometry g0, Geometry g1, double terminateDistance) {
122: this .geom = new Geometry[2];
123: geom[0] = g0;
124: geom[1] = g1;
125: this .terminateDistance = terminateDistance;
126: }
127:
128: /**
129: * Report the distance between the closest points on the input geometries.
130: *
131: * @return the distance between the geometries
132: */
133: public double distance() {
134: computeMinDistance();
135: return minDistance;
136: }
137:
138: /**
139: * Report the coordinates of the closest points in the input geometries.
140: * The points are presented in the same order as the input Geometries.
141: *
142: * @return a pair of {@link Coordinate}s of the closest points
143: */
144: public Coordinate[] closestPoints() {
145: computeMinDistance();
146: Coordinate[] closestPts = new Coordinate[] {
147: minDistanceLocation[0].getCoordinate(),
148: minDistanceLocation[1].getCoordinate() };
149: return closestPts;
150: }
151:
152: /**
153: * Report the locations of the closest points in the input geometries.
154: * The locations are presented in the same order as the input Geometries.
155: *
156: * @return a pair of {@link GeometryLocation}s for the closest points
157: */
158: public GeometryLocation[] closestLocations() {
159: computeMinDistance();
160: return minDistanceLocation;
161: }
162:
163: private void updateMinDistance(double dist) {
164: if (dist < minDistance)
165: minDistance = dist;
166: }
167:
168: private void updateMinDistance(GeometryLocation[] locGeom,
169: boolean flip) {
170: // if not set then don't update
171: if (locGeom[0] == null)
172: return;
173:
174: if (flip) {
175: minDistanceLocation[0] = locGeom[1];
176: minDistanceLocation[1] = locGeom[0];
177: } else {
178: minDistanceLocation[0] = locGeom[0];
179: minDistanceLocation[1] = locGeom[1];
180: }
181: }
182:
183: private void computeMinDistance() {
184: if (minDistanceLocation != null)
185: return;
186:
187: minDistanceLocation = new GeometryLocation[2];
188: computeContainmentDistance();
189: if (minDistance <= terminateDistance)
190: return;
191: computeLineDistance();
192: }
193:
194: private void computeContainmentDistance() {
195: List polys0 = PolygonExtracter.getPolygons(geom[0]);
196: List polys1 = PolygonExtracter.getPolygons(geom[1]);
197:
198: GeometryLocation[] locPtPoly = new GeometryLocation[2];
199: // test if either geometry is wholely inside the other
200: if (polys1.size() > 0) {
201: List insideLocs0 = ConnectedElementLocationFilter
202: .getLocations(geom[0]);
203: computeInside(insideLocs0, polys1, locPtPoly);
204: if (minDistance <= terminateDistance) {
205: minDistanceLocation[0] = locPtPoly[0];
206: minDistanceLocation[1] = locPtPoly[1];
207: return;
208: }
209: }
210: if (polys0.size() > 0) {
211: List insideLocs1 = ConnectedElementLocationFilter
212: .getLocations(geom[1]);
213: computeInside(insideLocs1, polys0, locPtPoly);
214: if (minDistance <= terminateDistance) {
215: // flip locations, since we are testing geom 1 VS geom 0
216: minDistanceLocation[0] = locPtPoly[1];
217: minDistanceLocation[1] = locPtPoly[0];
218: return;
219: }
220: }
221: }
222:
223: private void computeInside(List locs, List polys,
224: GeometryLocation[] locPtPoly) {
225: for (int i = 0; i < locs.size(); i++) {
226: GeometryLocation loc = (GeometryLocation) locs.get(i);
227: for (int j = 0; j < polys.size(); j++) {
228: Polygon poly = (Polygon) polys.get(j);
229: computeInside(loc, poly, locPtPoly);
230: if (minDistance <= terminateDistance) {
231: return;
232: }
233: }
234: }
235: }
236:
237: private void computeInside(GeometryLocation ptLoc, Polygon poly,
238: GeometryLocation[] locPtPoly) {
239: Coordinate pt = ptLoc.getCoordinate();
240: if (Location.EXTERIOR != ptLocator.locate(pt, poly)) {
241: minDistance = 0.0;
242: locPtPoly[0] = ptLoc;
243: GeometryLocation locPoly = new GeometryLocation(poly, pt);
244: locPtPoly[1] = locPoly;
245: return;
246: }
247: }
248:
249: private void computeLineDistance() {
250: GeometryLocation[] locGeom = new GeometryLocation[2];
251:
252: /**
253: * Geometries are not wholely inside, so compute distance from lines and points
254: * of one to lines and points of the other
255: */
256: List lines0 = LinearComponentExtracter.getLines(geom[0]);
257: List lines1 = LinearComponentExtracter.getLines(geom[1]);
258:
259: List pts0 = PointExtracter.getPoints(geom[0]);
260: List pts1 = PointExtracter.getPoints(geom[1]);
261:
262: // bail whenever minDistance goes to zero, since it can't get any less
263: computeMinDistanceLines(lines0, lines1, locGeom);
264: updateMinDistance(locGeom, false);
265: if (minDistance <= terminateDistance)
266: return;
267:
268: locGeom[0] = null;
269: locGeom[1] = null;
270: computeMinDistanceLinesPoints(lines0, pts1, locGeom);
271: updateMinDistance(locGeom, false);
272: if (minDistance <= terminateDistance)
273: return;
274:
275: locGeom[0] = null;
276: locGeom[1] = null;
277: computeMinDistanceLinesPoints(lines1, pts0, locGeom);
278: updateMinDistance(locGeom, true);
279: if (minDistance <= terminateDistance)
280: return;
281:
282: locGeom[0] = null;
283: locGeom[1] = null;
284: computeMinDistancePoints(pts0, pts1, locGeom);
285: updateMinDistance(locGeom, false);
286: }
287:
288: private void computeMinDistanceLines(List lines0, List lines1,
289: GeometryLocation[] locGeom) {
290: for (int i = 0; i < lines0.size(); i++) {
291: LineString line0 = (LineString) lines0.get(i);
292: for (int j = 0; j < lines1.size(); j++) {
293: LineString line1 = (LineString) lines1.get(j);
294: computeMinDistance(line0, line1, locGeom);
295: if (minDistance <= terminateDistance)
296: return;
297: }
298: }
299: }
300:
301: private void computeMinDistancePoints(List points0, List points1,
302: GeometryLocation[] locGeom) {
303: for (int i = 0; i < points0.size(); i++) {
304: Point pt0 = (Point) points0.get(i);
305: for (int j = 0; j < points1.size(); j++) {
306: Point pt1 = (Point) points1.get(j);
307: double dist = pt0.getCoordinate().distance(
308: pt1.getCoordinate());
309: if (dist < minDistance) {
310: minDistance = dist;
311: // this is wrong - need to determine closest points on both segments!!!
312: locGeom[0] = new GeometryLocation(pt0, 0, pt0
313: .getCoordinate());
314: locGeom[1] = new GeometryLocation(pt1, 0, pt1
315: .getCoordinate());
316: }
317: if (minDistance <= terminateDistance)
318: return;
319: }
320: }
321: }
322:
323: private void computeMinDistanceLinesPoints(List lines, List points,
324: GeometryLocation[] locGeom) {
325: for (int i = 0; i < lines.size(); i++) {
326: LineString line = (LineString) lines.get(i);
327: for (int j = 0; j < points.size(); j++) {
328: Point pt = (Point) points.get(j);
329: computeMinDistance(line, pt, locGeom);
330: if (minDistance <= terminateDistance)
331: return;
332: }
333: }
334: }
335:
336: private void computeMinDistance(LineString line0, LineString line1,
337: GeometryLocation[] locGeom) {
338: if (line0.getEnvelopeInternal().distance(
339: line1.getEnvelopeInternal()) > minDistance)
340: return;
341: Coordinate[] coord0 = line0.getCoordinates();
342: Coordinate[] coord1 = line1.getCoordinates();
343: // brute force approach!
344: for (int i = 0; i < coord0.length - 1; i++) {
345: for (int j = 0; j < coord1.length - 1; j++) {
346: double dist = CGAlgorithms.distanceLineLine(coord0[i],
347: coord0[i + 1], coord1[j], coord1[j + 1]);
348: if (dist < minDistance) {
349: minDistance = dist;
350: LineSegment seg0 = new LineSegment(coord0[i],
351: coord0[i + 1]);
352: LineSegment seg1 = new LineSegment(coord1[j],
353: coord1[j + 1]);
354: Coordinate[] closestPt = seg0.closestPoints(seg1);
355: locGeom[0] = new GeometryLocation(line0, i,
356: closestPt[0]);
357: locGeom[1] = new GeometryLocation(line1, j,
358: closestPt[1]);
359: }
360: if (minDistance <= terminateDistance)
361: return;
362: }
363: }
364: }
365:
366: private void computeMinDistance(LineString line, Point pt,
367: GeometryLocation[] locGeom) {
368: if (line.getEnvelopeInternal().distance(
369: pt.getEnvelopeInternal()) > minDistance)
370: return;
371: Coordinate[] coord0 = line.getCoordinates();
372: Coordinate coord = pt.getCoordinate();
373: // brute force approach!
374: for (int i = 0; i < coord0.length - 1; i++) {
375: double dist = CGAlgorithms.distancePointLine(coord,
376: coord0[i], coord0[i + 1]);
377: if (dist < minDistance) {
378: minDistance = dist;
379: LineSegment seg = new LineSegment(coord0[i],
380: coord0[i + 1]);
381: Coordinate segClosestPoint = seg.closestPoint(coord);
382: locGeom[0] = new GeometryLocation(line, i,
383: segClosestPoint);
384: locGeom[1] = new GeometryLocation(pt, 0, coord);
385: }
386: if (minDistance <= terminateDistance)
387: return;
388:
389: }
390: }
391:
392: }
|