001:
002: /*
003: * The JTS Topology Suite is a collection of Java classes that
004: * implement the fundamental operations required to validate a given
005: * geo-spatial data set to a known topological specification.
006: *
007: * Copyright (C) 2001 Vivid Solutions
008: *
009: * This library is free software; you can redistribute it and/or
010: * modify it under the terms of the GNU Lesser General Public
011: * License as published by the Free Software Foundation; either
012: * version 2.1 of the License, or (at your option) any later version.
013: *
014: * This library is distributed in the hope that it will be useful,
015: * but WITHOUT ANY WARRANTY; without even the implied warranty of
016: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
017: * Lesser General Public License for more details.
018: *
019: * You should have received a copy of the GNU Lesser General Public
020: * License along with this library; if not, write to the Free Software
021: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
022: *
023: * For more information, contact:
024: *
025: * Vivid Solutions
026: * Suite #1A
027: * 2328 Government Street
028: * Victoria BC V8T 5G5
029: * Canada
030: *
031: * (250)385-6040
032: * www.vividsolutions.com
033: */
034: package com.vividsolutions.jts.operation.buffer;
035:
036: /**
037: * @version 1.7
038: */
039: import java.util.*;
040: import com.vividsolutions.jts.geom.*;
041: import com.vividsolutions.jts.algorithm.*;
042: import com.vividsolutions.jts.geomgraph.*;
043: import com.vividsolutions.jts.noding.SegmentString;
044:
045: /**
046: * Creates all the raw offset curves for a buffer of a {@link Geometry}.
047: * Raw curves need to be noded together and polygonized to form the final buffer area.
048: *
049: * @version 1.7
050: */
051: public class OffsetCurveSetBuilder {
052:
053: private CGAlgorithms cga = new RobustCGAlgorithms();
054:
055: private Geometry inputGeom;
056: private double distance;
057: private OffsetCurveBuilder curveBuilder;
058:
059: private List curveList = new ArrayList();
060:
061: public OffsetCurveSetBuilder(Geometry inputGeom, double distance,
062: OffsetCurveBuilder curveBuilder) {
063: this .inputGeom = inputGeom;
064: this .distance = distance;
065: this .curveBuilder = curveBuilder;
066: }
067:
068: /**
069: * Computes the set of raw offset curves for the buffer.
070: * Each offset curve has an attached {@link Label} indicating
071: * its left and right location.
072: *
073: * @return a Collection of SegmentStrings representing the raw buffer curves
074: */
075: public List getCurves() {
076: add(inputGeom);
077: return curveList;
078: }
079:
080: private void addCurves(List lineList, int leftLoc, int rightLoc) {
081: for (Iterator i = lineList.iterator(); i.hasNext();) {
082: Coordinate[] coords = (Coordinate[]) i.next();
083: addCurve(coords, leftLoc, rightLoc);
084: }
085: }
086:
087: /**
088: * Creates a {@link SegmentString} for a coordinate list which is a raw offset curve,
089: * and adds it to the list of buffer curves.
090: * The SegmentString is tagged with a Label giving the topology of the curve.
091: * The curve may be oriented in either direction.
092: * If the curve is oriented CW, the locations will be:
093: * <br>Left: Location.EXTERIOR
094: * <br>Right: Location.INTERIOR
095: */
096: private void addCurve(Coordinate[] coord, int leftLoc, int rightLoc) {
097: // don't add null curves!
098: if (coord.length < 2)
099: return;
100: // add the edge for a coordinate list which is a raw offset curve
101: SegmentString e = new SegmentString(coord, new Label(0,
102: Location.BOUNDARY, leftLoc, rightLoc));
103: curveList.add(e);
104: }
105:
106: private void add(Geometry g) {
107: if (g.isEmpty())
108: return;
109:
110: if (g instanceof Polygon)
111: addPolygon((Polygon) g);
112: // LineString also handles LinearRings
113: else if (g instanceof LineString)
114: addLineString((LineString) g);
115: else if (g instanceof Point)
116: addPoint((Point) g);
117: else if (g instanceof MultiPoint)
118: addCollection((MultiPoint) g);
119: else if (g instanceof MultiLineString)
120: addCollection((MultiLineString) g);
121: else if (g instanceof MultiPolygon)
122: addCollection((MultiPolygon) g);
123: else if (g instanceof GeometryCollection)
124: addCollection((GeometryCollection) g);
125: else
126: throw new UnsupportedOperationException(g.getClass()
127: .getName());
128: }
129:
130: private void addCollection(GeometryCollection gc) {
131: for (int i = 0; i < gc.getNumGeometries(); i++) {
132: Geometry g = gc.getGeometryN(i);
133: add(g);
134: }
135: }
136:
137: /**
138: * Add a Point to the graph.
139: */
140: private void addPoint(Point p) {
141: if (distance <= 0.0)
142: return;
143: Coordinate[] coord = p.getCoordinates();
144: List lineList = curveBuilder.getLineCurve(coord, distance);
145: addCurves(lineList, Location.EXTERIOR, Location.INTERIOR);
146: }
147:
148: private void addLineString(LineString line) {
149: if (distance <= 0.0)
150: return;
151: Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(line
152: .getCoordinates());
153: List lineList = curveBuilder.getLineCurve(coord, distance);
154: addCurves(lineList, Location.EXTERIOR, Location.INTERIOR);
155: }
156:
157: private void addPolygon(Polygon p) {
158: double offsetDistance = distance;
159: int offsetSide = Position.LEFT;
160: if (distance < 0.0) {
161: offsetDistance = -distance;
162: offsetSide = Position.RIGHT;
163: }
164:
165: LinearRing shell = (LinearRing) p.getExteriorRing();
166: Coordinate[] shellCoord = CoordinateArrays
167: .removeRepeatedPoints(shell.getCoordinates());
168: // optimization - don't bother computing buffer
169: // if the polygon would be completely eroded
170: if (distance < 0.0 && isErodedCompletely(shell, distance))
171: return;
172:
173: addPolygonRing(shellCoord, offsetDistance, offsetSide,
174: Location.EXTERIOR, Location.INTERIOR);
175:
176: for (int i = 0; i < p.getNumInteriorRing(); i++) {
177:
178: LinearRing hole = (LinearRing) p.getInteriorRingN(i);
179: Coordinate[] holeCoord = CoordinateArrays
180: .removeRepeatedPoints(hole.getCoordinates());
181:
182: // optimization - don't bother computing buffer for this hole
183: // if the hole would be completely covered
184: if (distance > 0.0 && isErodedCompletely(hole, -distance))
185: continue;
186:
187: // Holes are topologically labelled opposite to the shell, since
188: // the interior of the polygon lies on their opposite side
189: // (on the left, if the hole is oriented CCW)
190: addPolygonRing(holeCoord, offsetDistance, Position
191: .opposite(offsetSide), Location.INTERIOR,
192: Location.EXTERIOR);
193: }
194: }
195:
196: /**
197: * Add an offset curve for a ring.
198: * The side and left and right topological location arguments
199: * assume that the ring is oriented CW.
200: * If the ring is in the opposite orientation,
201: * the left and right locations must be interchanged and the side flipped.
202: *
203: * @param coord the coordinates of the ring (must not contain repeated points)
204: * @param offsetDistance the distance at which to create the buffer
205: * @param side the side of the ring on which to construct the buffer line
206: * @param cwLeftLoc the location on the L side of the ring (if it is CW)
207: * @param cwRightLoc the location on the R side of the ring (if it is CW)
208: */
209: private void addPolygonRing(Coordinate[] coord,
210: double offsetDistance, int side, int cwLeftLoc,
211: int cwRightLoc) {
212: //Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(lr.getCoordinates());
213: int leftLoc = cwLeftLoc;
214: int rightLoc = cwRightLoc;
215: if (cga.isCCW(coord)) {
216: leftLoc = cwRightLoc;
217: rightLoc = cwLeftLoc;
218: side = Position.opposite(side);
219: }
220: List lineList = curveBuilder.getRingCurve(coord, side,
221: offsetDistance);
222: addCurves(lineList, leftLoc, rightLoc);
223: }
224:
225: /**
226: * The ringCoord is assumed to contain no repeated points.
227: * It may be degenerate (i.e. contain only 1, 2, or 3 points).
228: * In this case it has no area, and hence has a minimum diameter of 0.
229: *
230: * @param ringCoord
231: * @param offsetDistance
232: * @return
233: */
234: private boolean isErodedCompletely(LinearRing ring,
235: double bufferDistance) {
236: Coordinate[] ringCoord = ring.getCoordinates();
237: double minDiam = 0.0;
238: // degenerate ring has no area
239: if (ringCoord.length < 4)
240: return bufferDistance < 0;
241:
242: // important test to eliminate inverted triangle bug
243: // also optimizes erosion test for triangles
244: if (ringCoord.length == 4)
245: return isTriangleErodedCompletely(ringCoord, bufferDistance);
246:
247: // if envelope is narrower than twice the buffer distance, ring is eroded
248: Envelope env = ring.getEnvelopeInternal();
249: double envMinDimension = Math.min(env.getHeight(), env
250: .getWidth());
251: if (bufferDistance < 0.0
252: && 2 * Math.abs(bufferDistance) > envMinDimension)
253: return true;
254:
255: return false;
256: /**
257: * The following is a heuristic test to determine whether an
258: * inside buffer will be eroded completely.
259: * It is based on the fact that the minimum diameter of the ring pointset
260: * provides an upper bound on the buffer distance which would erode the
261: * ring.
262: * If the buffer distance is less than the minimum diameter, the ring
263: * may still be eroded, but this will be determined by
264: * a full topological computation.
265: *
266: */
267: //System.out.println(ring);
268: /* MD 7 Feb 2005 - there's an unknown bug in the MD code, so disable this for now
269: MinimumDiameter md = new MinimumDiameter(ring);
270: minDiam = md.getLength();
271: //System.out.println(md.getDiameter());
272: return minDiam < 2 * Math.abs(bufferDistance);
273: */
274: }
275:
276: /**
277: * Tests whether a triangular ring would be eroded completely by the given
278: * buffer distance.
279: * This is a precise test. It uses the fact that the inner buffer of a
280: * triangle converges on the inCentre of the triangle (the point
281: * equidistant from all sides). If the buffer distance is greater than the
282: * distance of the inCentre from a side, the triangle will be eroded completely.
283: *
284: * This test is important, since it removes a problematic case where
285: * the buffer distance is slightly larger than the inCentre distance.
286: * In this case the triangle buffer curve "inverts" with incorrect topology,
287: * producing an incorrect hole in the buffer.
288: *
289: * @param triangleCoord
290: * @param bufferDistance
291: * @return
292: */
293: private boolean isTriangleErodedCompletely(
294: Coordinate[] triangleCoord, double bufferDistance) {
295: Triangle tri = new Triangle(triangleCoord[0], triangleCoord[1],
296: triangleCoord[2]);
297: Coordinate inCentre = tri.inCentre();
298: double distToCentre = cga.distancePointLine(inCentre, tri.p0,
299: tri.p1);
300: return distToCentre < Math.abs(bufferDistance);
301: }
302:
303: }
|