Doc Classic

Class MinimumDiameter

  1  
  2 /*
  3  * Copyright (c) 2016 Vivid Solutions.
  4  *
  5  * All rights reserved. This program and the accompanying materials
  6  * are made available under the terms of the Eclipse Public License 2.0
  7  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
  8  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
  9  * and the Eclipse Distribution License is available at
 10  *
 11  * http://www.eclipse.org/org/documents/edl-v10.php.
 12  */
 13 package org.locationtech.jts.algorithm;
 14  
 15 import org.locationtech.jts.geom.Coordinate;
 16 import org.locationtech.jts.geom.Geometry;
 17 import org.locationtech.jts.geom.LineSegment;
 18 import org.locationtech.jts.geom.LineString;
 19 import org.locationtech.jts.geom.LinearRing;
 20 import org.locationtech.jts.geom.Point;
 21 import org.locationtech.jts.geom.Polygon;
 22  
 23 /**
 24  * Computes the minimum diameter of a {@link Geometry}.
 25  * The minimum diameter is defined to be the
 26  * width of the smallest band that
 27  * contains the geometry,
 28  * where a band is a strip of the plane defined
 29  * by two parallel lines.
 30  * This can be thought of as the smallest hole that the geometry can be
 31  * moved through, with a single rotation.
 32  * <p>
 33  * The first step in the algorithm is computing the convex hull of the Geometry.
 34  * If the input Geometry is known to be convex, a hint can be supplied to
 35  * avoid this computation.
 36  * <p>
 37  * This class can also be used to compute a line segment representing 
 38  * the minimum diameter, the supporting line segment of the minimum diameter,
 39  * and a minimum rectangle enclosing the input geometry.
 40  * This rectangle will
 41  * have width equal to the minimum diameter, and have one side
 42  * parallel to the supporting segment.
 43  *
 44  * @see ConvexHull
 45  *
 46  * @version 1.7
 47  */
 48 public class MinimumDiameter
 49 {
 50   /**
 51    * Gets the minimum rectangle enclosing a geometry.
 52    * 
 53    * @param geom the geometry
 54    * @return the minimum rectangle enclosing the geometry
 55    */
 56   public static Geometry getMinimumRectangle(Geometry geom) {
 57     return (new MinimumDiameter(geom)).getMinimumRectangle();
 58   }
 59   
 60   /**
 61    * Gets the length of the minimum diameter enclosing a geometry
 62    * @param geom the geometry
 63    * @return the length of the minimum diameter of the geometry
 64    */
 65   public static Geometry getMinimumDiameter(Geometry geom) {
 66     return (new MinimumDiameter(geom)).getDiameter();
 67   }
 68   
 69   private final Geometry inputGeom;
 70   private final boolean isConvex;
 71  
 72   private Coordinate[] convexHullPts = null;
 73   private LineSegment minBaseSeg = new LineSegment();
 74   private Coordinate minWidthPt = null;
 75   private int minPtIndex;
 76   private double minWidth = 0.0;
 77  
 78   /**
 79    * Compute a minimum diameter for a given {@link Geometry}.
 80    *
 81    * @param inputGeom a Geometry
 82    */
 83   public MinimumDiameter(Geometry inputGeom)
 84   {
 85     this(inputGeom, false);
 86   }
 87  
 88   /**
 89    * Compute a minimum diameter for a giver {@link Geometry},
 90    * with a hint if
 91    * the Geometry is convex
 92    * (e.g. a convex Polygon or LinearRing,
 93    * or a two-point LineString, or a Point).
 94    *
 95    * @param inputGeom a Geometry which is convex
 96    * @param isConvex <code>true</code> if the input geometry is convex
 97    */
 98   public MinimumDiameter(Geometry inputGeom, boolean isConvex)
 99   {
100     this.inputGeom = inputGeom;
101     this.isConvex = isConvex;
102   }
103  
104   /**
105    * Gets the length of the minimum diameter of the input Geometry
106    *
107    * @return the length of the minimum diameter
108    */
109   public double getLength()
110   {
111     computeMinimumDiameter();
112     return minWidth;
113   }
114  
115   /**
116    * Gets the {@link Coordinate} forming one end of the minimum diameter
117    *
118    * @return a coordinate forming one end of the minimum diameter
119    */
120   public Coordinate getWidthCoordinate()
121   {
122     computeMinimumDiameter();
123     return minWidthPt;
124   }
125  
126   /**
127    * Gets the segment forming the base of the minimum diameter
128    *
129    * @return the segment forming the base of the minimum diameter
130    */
131   public LineString getSupportingSegment()
132   {
133     computeMinimumDiameter();
134     return inputGeom.getFactory().createLineString(new Coordinate[] { minBaseSeg.p0, minBaseSeg.p1 } );
135   }
136  
137   /**
138    * Gets a {@link LineString} which is a minimum diameter
139    *
140    * @return a {@link LineString} which is a minimum diameter
141    */
142   public LineString getDiameter()
143   {
144     computeMinimumDiameter();
145  
146     // return empty linestring if no minimum width calculated
147     if (minWidthPt == null)
148       return inputGeom.getFactory().createLineString();
149  
150     Coordinate basePt = minBaseSeg.project(minWidthPt);
151     return inputGeom.getFactory().createLineString(new Coordinate[] { basePt, minWidthPt } );
152   }
153  
154   private void computeMinimumDiameter()
155   {
156     // check if computation is cached
157     if (minWidthPt != null)
158       return;
159  
160     if (isConvex)
161       computeWidthConvex(inputGeom);
162     else {
163       Geometry convexGeom = (new ConvexHull(inputGeom)).getConvexHull();
164       computeWidthConvex(convexGeom);
165     }
166   }
167  
168   private void computeWidthConvex(Geometry convexGeom)
169   {
170 //System.out.println("Input = " + geom);
171     if (convexGeom instanceof Polygon)
172       convexHullPts = ((Polygon) convexGeom).getExteriorRing().getCoordinates();
173     else
174       convexHullPts = convexGeom.getCoordinates();
175  
176     // special cases for lines or points or degenerate rings
177     if (convexHullPts.length == 0) {
178       minWidth = 0.0;
179       minWidthPt = null;
180       minBaseSeg = null;
181     }
182     else if (convexHullPts.length == 1) {
183       minWidth = 0.0;
184       minWidthPt = convexHullPts[0];
185       minBaseSeg.p0 = convexHullPts[0];
186       minBaseSeg.p1 = convexHullPts[0];
187     }
188     else if (convexHullPts.length == 2 || convexHullPts.length == 3) {
189       minWidth = 0.0;
190       minWidthPt = convexHullPts[0];
191       minBaseSeg.p0 = convexHullPts[0];
192       minBaseSeg.p1 = convexHullPts[1];
193     }
194     else
195       computeConvexRingMinDiameter(convexHullPts);
196   }
197  
198   /**
199    * Compute the width information for a ring of {@link Coordinate}s.
200    * Leaves the width information in the instance variables.
201    *
202    * @param pts
203    */
204   private void computeConvexRingMinDiameter(Coordinate[] pts)
205   {
206     // for each segment in the ring
207     minWidth = Double.MAX_VALUE;
208     int currMaxIndex = 1;
209  
210     LineSegment seg = new LineSegment();
211     // compute the max distance for all segments in the ring, and pick the minimum
212     for (int i = 0; i < pts.length - 1; i++) {
213       seg.p0 = pts[i];
214       seg.p1 = pts[i + 1];
215       currMaxIndex = findMaxPerpDistance(pts, seg, currMaxIndex);
216     }
217   }
218  
219   private int findMaxPerpDistance(Coordinate[] pts, LineSegment seg, int startIndex)
220   {
221     double maxPerpDistance = seg.distancePerpendicular(pts[startIndex]);
222     double nextPerpDistance = maxPerpDistance;
223     int maxIndex = startIndex;
224     int nextIndex = maxIndex;
225     while (nextPerpDistance >= maxPerpDistance) {
226       maxPerpDistance = nextPerpDistance;
227       maxIndex = nextIndex;
228  
229       nextIndex = nextIndex(pts, maxIndex);
230       nextPerpDistance = seg.distancePerpendicular(pts[nextIndex]);
231     }
232     // found maximum width for this segment - update global min dist if appropriate
233     if (maxPerpDistance < minWidth) {
234       minPtIndex = maxIndex;
235       minWidth = maxPerpDistance;
236       minWidthPt = pts[minPtIndex];
237       minBaseSeg = new LineSegment(seg);
238 //      System.out.println(minBaseSeg);
239 //      System.out.println(minWidth);
240     }
241     return maxIndex;
242   }
243  
244   private static int nextIndex(Coordinate[] pts, int index)
245   {
246     index++;
247     if (index >= pts.length) index = 0;
248     return index;
249   }
250   
251   /**
252    * Gets the minimum rectangular {@link Polygon} which encloses the input geometry.
253    * The rectangle has width equal to the minimum diameter, 
254    * and a longer length.
255    * If the convex hull of the input is degenerate (a line or point)
256    * a {@link LineString} or {@link Point} is returned.
257    * <p>
258    * The minimum rectangle can be used as an extremely generalized representation
259    * for the given geometry.
260    * 
261    * @return the minimum rectangle enclosing the input (or a line or point if degenerate)
262    */
263   public Geometry getMinimumRectangle()
264   {
265     computeMinimumDiameter();
266   
267     // check if minimum rectangle is degenerate (a point or line segment)
268     if (minWidth == 0.0) {
269       if (minBaseSeg.p0.equals2D(minBaseSeg.p1)) {
270         return inputGeom.getFactory().createPoint(minBaseSeg.p0);
271       }
272       return minBaseSeg.toGeometry(inputGeom.getFactory());
273     }
274     
275     // deltas for the base segment of the minimum diameter
276     double dx = minBaseSeg.p1.x - minBaseSeg.p0.x;
277     double dy = minBaseSeg.p1.y - minBaseSeg.p0.y;
278     
279     /*
280     double c0 = computeC(dx, dy, minBaseSeg.p0);
281     double c1 = computeC(dx, dy, minBaseSeg.p1);
282     */
283     
284     double minPara = Double.MAX_VALUE;
285     double maxPara = -Double.MAX_VALUE;
286     double minPerp = Double.MAX_VALUE;
287     double maxPerp = -Double.MAX_VALUE;
288     
289     // compute maxima and minima of lines parallel and perpendicular to base segment
290     for (int i = 0; i < convexHullPts.length; i++) {
291       
292       double paraC = computeC(dx, dy, convexHullPts[i]);
293       if (paraC > maxPara) maxPara = paraC;
294       if (paraC < minPara) minPara = paraC;
295       
296       double perpC = computeC(-dy, dx, convexHullPts[i]);
297       if (perpC > maxPerp) maxPerp = perpC;
298       if (perpC < minPerp) minPerp = perpC;
299     }
300     
301     // compute lines along edges of minimum rectangle
302     LineSegment maxPerpLine = computeSegmentForLine(-dx, -dy, maxPerp);
303     LineSegment minPerpLine = computeSegmentForLine(-dx, -dy, minPerp);
304     LineSegment maxParaLine = computeSegmentForLine(-dy, dx, maxPara);
305     LineSegment minParaLine = computeSegmentForLine(-dy, dx, minPara);
306     
307     // compute vertices of rectangle (where the para/perp max & min lines intersect)
308     Coordinate p0 = maxParaLine.lineIntersection(maxPerpLine);
309     Coordinate p1 = minParaLine.lineIntersection(maxPerpLine);
310     Coordinate p2 = minParaLine.lineIntersection(minPerpLine);
311     Coordinate p3 = maxParaLine.lineIntersection(minPerpLine);
312     
313     LinearRing shell = inputGeom.getFactory().createLinearRing(
314         new Coordinate[] { p0, p1, p2, p3, p0 });
315     return inputGeom.getFactory().createPolygon(shell);
316  
317   }
318   
319   private static double computeC(double a, double b, Coordinate p)
320   {
321     return a * p.y - b * p.x;
322   }
323   
324   private static LineSegment computeSegmentForLine(double a, double b, double c)
325   {
326     Coordinate p0;
327     Coordinate p1;
328     /*
329     * Line eqn is ax + by = c
330     * Slope is a/b.
331     * If slope is steep, use y values as the inputs
332     */
333     if (Math.abs(b) > Math.abs(a)) {
334       p0 = new Coordinate(0.0, c/b);
335       p1 = new Coordinate(1.0, c/b - a/b);
336     }
337     else {
338       p0 = new Coordinate(c/a, 0.0);
339       p1 = new Coordinate(c/a - b/a, 1.0);
340     }
341     return new LineSegment(p0, p1);
342   }
343 }
344