← Back to branch summary

~ubuntu-branches/ubuntu/natty/jts/natty

« back to all changes in this revision

Viewing changes to src/com/vividsolutions/jts/algorithm/MinimumDiameter.java

  • Committer: Bazaar Package Importer
  • Author(s): Wolfgang Baer
  • Date: 2005-08-07 14:12:35 UTC
  • Revision ID: james.westby@ubuntu.com-20050807141235-7hy3ll3xpq79djcb
Tags: upstream-1.6
Import upstream version 1.6

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/com/vividsolutions/jts/algorithm/MinimumDiameter.java
 
1
 
 
2
/*
 
3
 * The JTS Topology Suite is a collection of Java classes that
 
4
 * implement the fundamental operations required to validate a given
 
5
 * geo-spatial data set to a known topological specification.
 
6
 *
 
7
 * Copyright (C) 2001 Vivid Solutions
 
8
 *
 
9
 * This library is free software; you can redistribute it and/or
 
10
 * modify it under the terms of the GNU Lesser General Public
 
11
 * License as published by the Free Software Foundation; either
 
12
 * version 2.1 of the License, or (at your option) any later version.
 
13
 *
 
14
 * This library is distributed in the hope that it will be useful,
 
15
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
17
 * Lesser General Public License for more details.
 
18
 *
 
19
 * You should have received a copy of the GNU Lesser General Public
 
20
 * License along with this library; if not, write to the Free Software
 
21
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
22
 *
 
23
 * For more information, contact:
 
24
 *
 
25
 *     Vivid Solutions
 
26
 *     Suite #1A
 
27
 *     2328 Government Street
 
28
 *     Victoria BC  V8T 5G5
 
29
 *     Canada
 
30
 *
 
31
 *     (250)385-6040
 
32
 *     www.vividsolutions.com
 
33
 */
 
34
package com.vividsolutions.jts.algorithm;
 
35
 
 
36
import com.vividsolutions.jts.geom.*;
 
37
 
 
38
/**
 
39
 * Computes the minimum diameter of a {@link Geometry}.
 
40
 * The minimum diameter is defined to be the
 
41
 * width of the smallest band that
 
42
 * contains the geometry,
 
43
 * where a band is a strip of the plane defined
 
44
 * by two parallel lines.
 
45
 * This can be thought of as the smallest hole that the geometry can be
 
46
 * moved through, with a single rotation.
 
47
 * <p>
 
48
 * The first step in the algorithm is computing the convex hull of the Geometry.
 
49
 * If the input Geometry is known to be convex, a hint can be supplied to
 
50
 * avoid this computation.
 
51
 *
 
52
 * @see ConvexHull
 
53
 *
 
54
 * @version 1.6
 
55
 */
 
56
public class MinimumDiameter
 
57
{
 
58
  private final Geometry inputGeom;
 
59
  private final boolean isConvex;
 
60
 
 
61
  private LineSegment minBaseSeg = new LineSegment();
 
62
  private Coordinate minWidthPt = null;
 
63
  private int minPtIndex;
 
64
  private double minWidth = 0.0;
 
65
 
 
66
  /**
 
67
   * Compute a minimum diameter for a giver {@link Geometry}.
 
68
   *
 
69
   * @param geom a Geometry
 
70
   */
 
71
  public MinimumDiameter(Geometry inputGeom)
 
72
  {
 
73
    this(inputGeom, false);
 
74
  }
 
75
 
 
76
  /**
 
77
   * Compute a minimum diameter for a giver {@link Geometry},
 
78
   * with a hint if
 
79
   * the Geometry is convex
 
80
   * (e.g. a convex Polygon or LinearRing,
 
81
   * or a two-point LineString, or a Point).
 
82
   *
 
83
   * @param geom a Geometry which is convex
 
84
   * @param isConvex <code>true</code> if the input geometry is convex
 
85
   */
 
86
  public MinimumDiameter(Geometry inputGeom, boolean isConvex)
 
87
  {
 
88
    this.inputGeom = inputGeom;
 
89
    this.isConvex = isConvex;
 
90
  }
 
91
 
 
92
  /**
 
93
   * Gets the length of the minimum diameter of the input Geometry
 
94
   *
 
95
   * @return the length of the minimum diameter
 
96
   */
 
97
  public double getLength()
 
98
  {
 
99
    computeMinimumDiameter();
 
100
    return minWidth;
 
101
  }
 
102
 
 
103
  /**
 
104
   * Gets the {@link Coordinate} forming one end of the minimum diameter
 
105
   *
 
106
   * @return a coordinate forming one end of the minimum diameter
 
107
   */
 
108
  public Coordinate getWidthCoordinate()
 
109
  {
 
110
    computeMinimumDiameter();
 
111
    return minWidthPt;
 
112
  }
 
113
 
 
114
  /**
 
115
   * Gets the segment forming the base of the minimum diameter
 
116
   *
 
117
   * @return the segment forming the base of the minimum diameter
 
118
   */
 
119
  public LineString getSupportingSegment()
 
120
  {
 
121
    computeMinimumDiameter();
 
122
    return inputGeom.getFactory().createLineString(new Coordinate[] { minBaseSeg.p0, minBaseSeg.p1 } );
 
123
  }
 
124
 
 
125
  /**
 
126
   * Gets a {@link LineString} which is a minimum diameter
 
127
   *
 
128
   * @return a {@link LineString} which is a minimum diameter
 
129
   */
 
130
  public LineString getDiameter()
 
131
  {
 
132
    computeMinimumDiameter();
 
133
 
 
134
    // return empty linestring if no minimum width calculated
 
135
    if (minWidthPt == null)
 
136
      return inputGeom.getFactory().createLineString((Coordinate[])null);
 
137
 
 
138
    Coordinate basePt = minBaseSeg.project(minWidthPt);
 
139
    return inputGeom.getFactory().createLineString(new Coordinate[] { basePt, minWidthPt } );
 
140
  }
 
141
 
 
142
  private void computeMinimumDiameter()
 
143
  {
 
144
    // check if computation is cached
 
145
    if (minWidthPt != null)
 
146
      return;
 
147
 
 
148
    if (isConvex)
 
149
      computeWidthConvex(inputGeom);
 
150
    else {
 
151
      Geometry convexGeom = (new ConvexHull(inputGeom)).getConvexHull();
 
152
      computeWidthConvex(convexGeom);
 
153
    }
 
154
  }
 
155
 
 
156
  private void computeWidthConvex(Geometry geom)
 
157
  {
 
158
//System.out.println("Input = " + geom);
 
159
    Coordinate[] pts = null;
 
160
    if (geom instanceof Polygon)
 
161
      pts = ((Polygon) geom).getExteriorRing().getCoordinates();
 
162
    else
 
163
      pts = geom.getCoordinates();
 
164
 
 
165
    // special cases for lines or points or degenerate rings
 
166
    if (pts.length == 0) {
 
167
      minWidth = 0.0;
 
168
      minWidthPt = null;
 
169
      minBaseSeg = null;
 
170
    }
 
171
    else if (pts.length == 1) {
 
172
      minWidth = 0.0;
 
173
      minWidthPt = pts[0];
 
174
      minBaseSeg.p0 = pts[0];
 
175
      minBaseSeg.p1 = pts[0];
 
176
    }
 
177
    else if (pts.length == 2 || pts.length == 3) {
 
178
      minWidth = 0.0;
 
179
      minWidthPt = pts[0];
 
180
      minBaseSeg.p0 = pts[0];
 
181
      minBaseSeg.p1 = pts[1];
 
182
    }
 
183
    else
 
184
      computeConvexRingMinDiameter(pts);
 
185
  }
 
186
 
 
187
  /**
 
188
   * Compute the width information for a ring of {@link Coordinate}s.
 
189
   * Leaves the width information in the instance variables.
 
190
   *
 
191
   * @param pts
 
192
   * @return
 
193
   */
 
194
  private void computeConvexRingMinDiameter(Coordinate[] pts)
 
195
  {
 
196
    //if (
 
197
    // for each segment in the ring
 
198
    minWidth = Double.MAX_VALUE;
 
199
    int currMaxIndex = 1;
 
200
 
 
201
    LineSegment seg = new LineSegment();
 
202
    // compute the max distance for all segments in the ring, and pick the minimum
 
203
    for (int i = 0; i < pts.length - 1; i++) {
 
204
      seg.p0 = pts[i];
 
205
      seg.p1 = pts[i + 1];
 
206
      currMaxIndex = findMaxPerpDistance(pts, seg, currMaxIndex);
 
207
    }
 
208
  }
 
209
 
 
210
  private int findMaxPerpDistance(Coordinate[] pts, LineSegment seg, int startIndex)
 
211
  {
 
212
    double maxPerpDistance = seg.distancePerpendicular(pts[startIndex]);
 
213
    double nextPerpDistance = maxPerpDistance;
 
214
    int maxIndex = startIndex;
 
215
    int nextIndex = maxIndex;
 
216
    while (nextPerpDistance >= maxPerpDistance) {
 
217
      maxPerpDistance = nextPerpDistance;
 
218
      maxIndex = nextIndex;
 
219
 
 
220
      nextIndex = nextIndex(pts, maxIndex);
 
221
      nextPerpDistance = seg.distancePerpendicular(pts[nextIndex]);
 
222
    }
 
223
    // found maximum width for this segment - update global min dist if appropriate
 
224
    if (maxPerpDistance < minWidth) {
 
225
      minPtIndex = maxIndex;
 
226
      minWidth = maxPerpDistance;
 
227
      minWidthPt = pts[minPtIndex];
 
228
      minBaseSeg = new LineSegment(seg);
 
229
//      System.out.println(minBaseSeg);
 
230
//      System.out.println(minWidth);
 
231
    }
 
232
    return maxIndex;
 
233
  }
 
234
 
 
235
  private static int nextIndex(Coordinate[] pts, int index)
 
236
  {
 
237
    index++;
 
238
    if (index >= pts.length) index = 0;
 
239
    return index;
 
240
  }
 
241
}