Doc Classic

Class OffsetCurveSetBuilder

  1  
  2  
  3  
  4 /*
  5  * Copyright (c) 2016 Vivid Solutions.
  6  *
  7  * All rights reserved. This program and the accompanying materials
  8  * are made available under the terms of the Eclipse Public License 2.0
  9  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
 10  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
 11  * and the Eclipse Distribution License is available at
 12  *
 13  * http://www.eclipse.org/org/documents/edl-v10.php.
 14  */
 15 package org.locationtech.jts.operation.buffer;
 16  
 17 /**
 18  * @version 1.7
 19  */
 20 import java.util.ArrayList;
 21 import java.util.List;
 22  
 23 import org.locationtech.jts.algorithm.Distance;
 24 import org.locationtech.jts.algorithm.Orientation;
 25 import org.locationtech.jts.geom.Coordinate;
 26 import org.locationtech.jts.geom.CoordinateArrays;
 27 import org.locationtech.jts.geom.Envelope;
 28 import org.locationtech.jts.geom.Geometry;
 29 import org.locationtech.jts.geom.GeometryCollection;
 30 import org.locationtech.jts.geom.LineString;
 31 import org.locationtech.jts.geom.LinearRing;
 32 import org.locationtech.jts.geom.Location;
 33 import org.locationtech.jts.geom.MultiLineString;
 34 import org.locationtech.jts.geom.MultiPoint;
 35 import org.locationtech.jts.geom.MultiPolygon;
 36 import org.locationtech.jts.geom.Point;
 37 import org.locationtech.jts.geom.Polygon;
 38 import org.locationtech.jts.geom.Triangle;
 39 import org.locationtech.jts.geomgraph.Label;
 40 import org.locationtech.jts.geomgraph.Position;
 41 import org.locationtech.jts.noding.NodedSegmentString;
 42 import org.locationtech.jts.noding.SegmentString;
 43  
 44 /**
 45  * Creates all the raw offset curves for a buffer of a {@link Geometry}.
 46  * Raw curves need to be noded together and polygonized to form the final buffer area.
 47  *
 48  * @version 1.7
 49  */
 50 public class OffsetCurveSetBuilder {
 51  
 52  
 53   private Geometry inputGeom;
 54   private double distance;
 55   private OffsetCurveBuilder curveBuilder;
 56  
 57   private List curveList = new ArrayList();
 58  
 59   public OffsetCurveSetBuilder(
 60       Geometry inputGeom,
 61           double distance,
 62           OffsetCurveBuilder curveBuilder)
 63   {
 64     this.inputGeom = inputGeom;
 65     this.distance = distance;
 66     this.curveBuilder = curveBuilder;
 67   }
 68  
 69   /**
 70    * Computes the set of raw offset curves for the buffer.
 71    * Each offset curve has an attached {@link Label} indicating
 72    * its left and right location.
 73    *
 74    * @return a Collection of SegmentStrings representing the raw buffer curves
 75    */
 76   public List getCurves()
 77   {
 78     add(inputGeom);
 79     return curveList;
 80   }
 81  
 82   /**
 83    * Creates a {@link SegmentString} for a coordinate list which is a raw offset curve,
 84    * and adds it to the list of buffer curves.
 85    * The SegmentString is tagged with a Label giving the topology of the curve.
 86    * The curve may be oriented in either direction.
 87    * If the curve is oriented CW, the locations will be:
 88    * <br>Left: Location.EXTERIOR
 89    * <br>Right: Location.INTERIOR
 90    */
 91   private void addCurve(Coordinate[] coord, int leftLoc, int rightLoc)
 92   {
 93     // don't add null or trivial curves
 94     if (coord == null || coord.length < 2) return;
 95     // add the edge for a coordinate list which is a raw offset curve
 96     SegmentString e = new NodedSegmentString(coord,
 97                         new Label(0, Location.BOUNDARY, leftLoc, rightLoc));
 98     curveList.add(e);
 99   }
100  
101  
102   private void add(Geometry g)
103   {
104     if (g.isEmpty()) return;
105  
106     if (g instanceof Polygon)                 addPolygon((Polygon) g);
107                         // LineString also handles LinearRings
108     else if (g instanceof LineString)         addLineString((LineString) g);
109     else if (g instanceof Point)              addPoint((Point) g);
110     else if (g instanceof MultiPoint)         addCollection((MultiPoint) g);
111     else if (g instanceof MultiLineString)    addCollection((MultiLineString) g);
112     else if (g instanceof MultiPolygon)       addCollection((MultiPolygon) g);
113     else if (g instanceof GeometryCollection) addCollection((GeometryCollection) g);
114     else  throw new UnsupportedOperationException(g.getClass().getName());
115   }
116   private void addCollection(GeometryCollection gc)
117   {
118     for (int i = 0; i < gc.getNumGeometries(); i++) {
119       Geometry g = gc.getGeometryN(i);
120       add(g);
121     }
122   }
123   /**
124    * Add a Point to the graph.
125    */
126   private void addPoint(Point p)
127   {
128     // a zero or negative width buffer of a point is empty
129     if (distance <= 0.0) 
130       return;
131     Coordinate[] coord = p.getCoordinates();
132     Coordinate[] curve = curveBuilder.getLineCurve(coord, distance);
133     addCurve(curve, Location.EXTERIOR, Location.INTERIOR);
134   }
135   
136   private void addLineString(LineString line)
137   {
138     if (curveBuilder.isLineOffsetEmpty(distance)) return;
139     
140     Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(line.getCoordinates());
141     
142     /**
143      * Rings (closed lines) are generated with a continuous curve, 
144      * with no end arcs. This produces better quality linework, 
145      * and avoids noding issues with arcs around almost-parallel end segments.
146      * See JTS #523 and #518.
147      * 
148      * Singled-sided buffers currently treat rings as if they are lines.
149      */
150     if (CoordinateArrays.isRing(coord) && ! curveBuilder.getBufferParameters().isSingleSided()) {
151       addRingBothSides(coord, distance);
152     }
153     else {
154       Coordinate[] curve = curveBuilder.getLineCurve(coord, distance);
155       addCurve(curve, Location.EXTERIOR, Location.INTERIOR);
156     }
157     // TESTING
158     //Coordinate[] curveTrim = BufferCurveLoopPruner.prune(curve); 
159     //addCurve(curveTrim, Location.EXTERIOR, Location.INTERIOR);
160   }
161   
162   private void addPolygon(Polygon p)
163   {
164     double offsetDistance = distance;
165     int offsetSide = Position.LEFT;
166     if (distance < 0.0) {
167       offsetDistance = -distance;
168       offsetSide = Position.RIGHT;
169     }
170  
171     LinearRing shell = p.getExteriorRing();
172     Coordinate[] shellCoord = CoordinateArrays.removeRepeatedPoints(shell.getCoordinates());
173     // optimization - don't bother computing buffer
174     // if the polygon would be completely eroded
175     if (distance < 0.0 && isErodedCompletely(shell, distance))
176         return;
177     // don't attempt to buffer a polygon with too few distinct vertices
178     if (distance <= 0.0 && shellCoord.length < 3)
179         return;
180  
181     addRingSide(
182             shellCoord,
183             offsetDistance,
184             offsetSide,
185             Location.EXTERIOR,
186             Location.INTERIOR);
187  
188     for (int i = 0; i < p.getNumInteriorRing(); i++) {
189  
190       LinearRing hole = p.getInteriorRingN(i);
191       Coordinate[] holeCoord = CoordinateArrays.removeRepeatedPoints(hole.getCoordinates());
192  
193       // optimization - don't bother computing buffer for this hole
194       // if the hole would be completely covered
195       if (distance > 0.0 && isErodedCompletely(hole, -distance))
196           continue;
197  
198       // Holes are topologically labelled opposite to the shell, since
199       // the interior of the polygon lies on their opposite side
200       // (on the left, if the hole is oriented CCW)
201       addRingSide(
202             holeCoord,
203             offsetDistance,
204             Position.opposite(offsetSide),
205             Location.INTERIOR,
206             Location.EXTERIOR);
207     }
208   }
209   
210   private void addRingBothSides(Coordinate[] coord, double distance)
211   {
212     addRingSide(coord, distance,
213       Position.LEFT, 
214       Location.EXTERIOR, Location.INTERIOR);
215     /* Add the opposite side of the ring
216     */
217     addRingSide(coord, distance,
218       Position.RIGHT,
219       Location.INTERIOR, Location.EXTERIOR);
220   }
221   
222   /**
223    * Adds an offset curve for one side of a ring.
224    * The side and left and right topological location arguments
225    * are provided as if the ring is oriented CW.
226    * (If the ring is in the opposite orientation,
227    * this is detected and 
228    * the left and right locations are interchanged and the side is flipped.)
229    *
230    * @param coord the coordinates of the ring (must not contain repeated points)
231    * @param offsetDistance the positive distance at which to create the buffer
232    * @param side the side {@link Position} of the ring on which to construct the buffer line
233    * @param cwLeftLoc the location on the L side of the ring (if it is CW)
234    * @param cwRightLoc the location on the R side of the ring (if it is CW)
235    */
236   private void addRingSide(Coordinate[] coord, double offsetDistance, int side, int cwLeftLoc, int cwRightLoc)
237   {
238     // don't bother adding ring if it is "flat" and will disappear in the output
239     if (offsetDistance == 0.0 && coord.length < LinearRing.MINIMUM_VALID_SIZE)
240       return;
241     
242     int leftLoc  = cwLeftLoc;
243     int rightLoc = cwRightLoc;
244     if (coord.length >= LinearRing.MINIMUM_VALID_SIZE 
245         && Orientation.isCCW(coord)) {
246       leftLoc = cwRightLoc;
247       rightLoc = cwLeftLoc;
248       side = Position.opposite(side);
249     }
250     Coordinate[] curve = curveBuilder.getRingCurve(coord, side, offsetDistance);
251     addCurve(curve, leftLoc, rightLoc);
252   }
253  
254   /**
255    * The ringCoord is assumed to contain no repeated points.
256    * It may be degenerate (i.e. contain only 1, 2, or 3 points).
257    * In this case it has no area, and hence has a minimum diameter of 0.
258    *
259    * @param ringCoord
260    * @param offsetDistance
261    * @return
262    */
263   private boolean isErodedCompletely(LinearRing ring, double bufferDistance)
264   {
265     Coordinate[] ringCoord = ring.getCoordinates();
266     // degenerate ring has no area
267     if (ringCoord.length < 4)
268       return bufferDistance < 0;
269  
270     // important test to eliminate inverted triangle bug
271     // also optimizes erosion test for triangles
272     if (ringCoord.length == 4)
273       return isTriangleErodedCompletely(ringCoord, bufferDistance);
274  
275     // if envelope is narrower than twice the buffer distance, ring is eroded
276     Envelope env = ring.getEnvelopeInternal();
277     double envMinDimension = Math.min(env.getHeight(), env.getWidth());
278     if (bufferDistance < 0.0
279         && 2 * Math.abs(bufferDistance) > envMinDimension)
280       return true;
281  
282     return false;
283     /**
284      * The following is a heuristic test to determine whether an
285      * inside buffer will be eroded completely.
286      * It is based on the fact that the minimum diameter of the ring pointset
287      * provides an upper bound on the buffer distance which would erode the
288      * ring.
289      * If the buffer distance is less than the minimum diameter, the ring
290      * may still be eroded, but this will be determined by
291      * a full topological computation.
292      *
293      */
294 //System.out.println(ring);
295 /* MD  7 Feb 2005 - there's an unknown bug in the MD code, so disable this for now
296     MinimumDiameter md = new MinimumDiameter(ring);
297     minDiam = md.getLength();
298     //System.out.println(md.getDiameter());
299     return minDiam < 2 * Math.abs(bufferDistance);
300     */
301   }
302  
303   /**
304    * Tests whether a triangular ring would be eroded completely by the given
305    * buffer distance.
306    * This is a precise test.  It uses the fact that the inner buffer of a
307    * triangle converges on the inCentre of the triangle (the point
308    * equidistant from all sides).  If the buffer distance is greater than the
309    * distance of the inCentre from a side, the triangle will be eroded completely.
310    *
311    * This test is important, since it removes a problematic case where
312    * the buffer distance is slightly larger than the inCentre distance.
313    * In this case the triangle buffer curve "inverts" with incorrect topology,
314    * producing an incorrect hole in the buffer.
315    *
316    * @param triangleCoord
317    * @param bufferDistance
318    * @return
319    */
320   private boolean isTriangleErodedCompletely(
321       Coordinate[] triangleCoord,
322       double bufferDistance)
323   {
324     Triangle tri = new Triangle(triangleCoord[0], triangleCoord[1], triangleCoord[2]);
325     Coordinate inCentre = tri.inCentre();
326     double distToCentre = Distance.pointToSegment(inCentre, tri.p0, tri.p1);
327     return distToCentre < Math.abs(bufferDistance);
328   }
329  
330  
331  
332 }
333