Doc Classic

Class GeometryGraph

  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.geomgraph;
 16  
 17 import java.util.Collection;
 18 import java.util.HashMap;
 19 import java.util.Iterator;
 20 import java.util.List;
 21 import java.util.Map;
 22  
 23 import org.locationtech.jts.algorithm.BoundaryNodeRule;
 24 import org.locationtech.jts.algorithm.LineIntersector;
 25 import org.locationtech.jts.algorithm.Orientation;
 26 import org.locationtech.jts.algorithm.PointLocator;
 27 import org.locationtech.jts.algorithm.locate.IndexedPointInAreaLocator;
 28 import org.locationtech.jts.algorithm.locate.PointOnGeometryLocator;
 29 import org.locationtech.jts.geom.Coordinate;
 30 import org.locationtech.jts.geom.CoordinateArrays;
 31 import org.locationtech.jts.geom.Geometry;
 32 import org.locationtech.jts.geom.GeometryCollection;
 33 import org.locationtech.jts.geom.LineString;
 34 import org.locationtech.jts.geom.LinearRing;
 35 import org.locationtech.jts.geom.Location;
 36 import org.locationtech.jts.geom.MultiLineString;
 37 import org.locationtech.jts.geom.MultiPoint;
 38 import org.locationtech.jts.geom.MultiPolygon;
 39 import org.locationtech.jts.geom.Point;
 40 import org.locationtech.jts.geom.Polygon;
 41 import org.locationtech.jts.geom.Polygonal;
 42 import org.locationtech.jts.geomgraph.index.EdgeSetIntersector;
 43 import org.locationtech.jts.geomgraph.index.SegmentIntersector;
 44 import org.locationtech.jts.geomgraph.index.SimpleMCSweepLineIntersector;
 45 import org.locationtech.jts.util.Assert;
 46  
 47 /**
 48  * A GeometryGraph is a graph that models a given Geometry
 49  * @version 1.7
 50  */
 51 public class GeometryGraph
 52   extends PlanarGraph
 53 {
 54 /**
 55  * This method implements the Boundary Determination Rule
 56  * for determining whether
 57  * a component (node or edge) that appears multiple times in elements
 58  * of a MultiGeometry is in the boundary or the interior of the Geometry
 59  * <br>
 60  * The SFS uses the "Mod-2 Rule", which this function implements
 61  * <br>
 62  * An alternative (and possibly more intuitive) rule would be
 63  * the "At Most One Rule":
 64  *    isInBoundary = (componentCount == 1)
 65  */
 66 /*
 67   public static boolean isInBoundary(int boundaryCount)
 68   {
 69     // the "Mod-2 Rule"
 70     return boundaryCount % 2 == 1;
 71   }
 72   public static int determineBoundary(int boundaryCount)
 73   {
 74     return isInBoundary(boundaryCount) ? Location.BOUNDARY : Location.INTERIOR;
 75   }
 76 */
 77  
 78   public static int determineBoundary(BoundaryNodeRule boundaryNodeRule, int boundaryCount)
 79   {
 80     return boundaryNodeRule.isInBoundary(boundaryCount)
 81         ? Location.BOUNDARY : Location.INTERIOR;
 82   }
 83  
 84   private Geometry parentGeom;
 85  
 86   /**
 87    * The lineEdgeMap is a map of the linestring components of the
 88    * parentGeometry to the edges which are derived from them.
 89    * This is used to efficiently perform findEdge queries
 90    */
 91   private Map lineEdgeMap = new HashMap();
 92  
 93   private BoundaryNodeRule boundaryNodeRule = null;
 94  
 95   /**
 96    * If this flag is true, the Boundary Determination Rule will used when deciding
 97    * whether nodes are in the boundary or not
 98    */
 99   private boolean useBoundaryDeterminationRule = true;
100   private int argIndex;  // the index of this geometry as an argument to a spatial function (used for labelling)
101   private Collection boundaryNodes;
102   private boolean hasTooFewPoints = false;
103   private Coordinate invalidPoint = null;
104  
105   private PointOnGeometryLocator areaPtLocator = null;
106   // for use if geometry is not Polygonal
107   private final PointLocator ptLocator = new PointLocator();
108   
109   private EdgeSetIntersector createEdgeSetIntersector()
110   {
111   // various options for computing intersections, from slowest to fastest
112  
113   //private EdgeSetIntersector esi = new SimpleEdgeSetIntersector();
114   //private EdgeSetIntersector esi = new MonotoneChainIntersector();
115   //private EdgeSetIntersector esi = new NonReversingChainIntersector();
116   //private EdgeSetIntersector esi = new SimpleSweepLineIntersector();
117   //private EdgeSetIntersector esi = new MCSweepLineIntersector();
118  
119     //return new SimpleEdgeSetIntersector();
120     return new SimpleMCSweepLineIntersector();
121   }
122  
123   public GeometryGraph(int argIndex, Geometry parentGeom)
124   {
125     this(argIndex, parentGeom,
126          BoundaryNodeRule.OGC_SFS_BOUNDARY_RULE
127          );
128   }
129  
130   public GeometryGraph(int argIndex, Geometry parentGeom, BoundaryNodeRule boundaryNodeRule) {
131     this.argIndex = argIndex;
132     this.parentGeom = parentGeom;
133     this.boundaryNodeRule = boundaryNodeRule;
134     if (parentGeom != null) {
135 //      precisionModel = parentGeom.getPrecisionModel();
136 //      SRID = parentGeom.getSRID();
137       add(parentGeom);
138     }
139   }
140  
141   /**
142    * This constructor is used by clients that wish to add Edges explicitly,
143    * rather than adding a Geometry.  (An example is BufferOp).
144    */
145   // no longer used
146 //  public GeometryGraph(int argIndex, PrecisionModel precisionModel, int SRID) {
147 //    this(argIndex, null);
148 //    this.precisionModel = precisionModel;
149 //    this.SRID = SRID;
150 //  }
151 //  public PrecisionModel getPrecisionModel()
152 //  {
153 //    return precisionModel;
154 //  }
155 //  public int getSRID() { return SRID; }
156  
157   public boolean hasTooFewPoints() { return hasTooFewPoints; }
158  
159   public Coordinate getInvalidPoint() { return invalidPoint; }
160  
161   public Geometry getGeometry() { return parentGeom; }
162  
163   public BoundaryNodeRule getBoundaryNodeRule() { return boundaryNodeRule; }
164  
165   public Collection getBoundaryNodes()
166   {
167     if (boundaryNodes == null)
168       boundaryNodes = nodes.getBoundaryNodes(argIndex);
169     return boundaryNodes;
170   }
171  
172   public Coordinate[] getBoundaryPoints()
173   {
174     Collection coll = getBoundaryNodes();
175     Coordinate[] pts = new Coordinate[coll.size()];
176     int i = 0;
177     for (Iterator it = coll.iterator(); it.hasNext(); ) {
178       Node node = (Node) it.next();
179       pts[i++] = node.getCoordinate().copy();
180     }
181     return pts;
182   }
183  
184   public Edge findEdge(LineString line)
185   {
186     return (Edge) lineEdgeMap.get(line);
187   }
188  
189   public void computeSplitEdges(List edgelist)
190   {
191     for (Iterator i = edges.iterator(); i.hasNext(); ) {
192       Edge e = (Edge) i.next();
193       e.eiList.addSplitEdges(edgelist);
194     }
195   }
196   private void add(Geometry g)
197   {
198     if (g.isEmpty()) return;
199  
200     // check if this Geometry should obey the Boundary Determination Rule
201     // all collections except MultiPolygons obey the rule
202     if (g instanceof MultiPolygon)
203       useBoundaryDeterminationRule = false;
204  
205     if (g instanceof Polygon)                 addPolygon((Polygon) g);
206                         // LineString also handles LinearRings
207     else if (g instanceof LineString)         addLineString((LineString) g);
208     else if (g instanceof Point)              addPoint((Point) g);
209     else if (g instanceof MultiPoint)         addCollection((MultiPoint) g);
210     else if (g instanceof MultiLineString)    addCollection((MultiLineString) g);
211     else if (g instanceof MultiPolygon)       addCollection((MultiPolygon) g);
212     else if (g instanceof GeometryCollection) addCollection((GeometryCollection) g);
213     else  throw new UnsupportedOperationException(g.getClass().getName());
214   }
215  
216   private void addCollection(GeometryCollection gc)
217   {
218     for (int i = 0; i < gc.getNumGeometries(); i++) {
219       Geometry g = gc.getGeometryN(i);
220       add(g);
221     }
222   }
223   /**
224    * Add a Point to the graph.
225    */
226   private void addPoint(Point p)
227   {
228     Coordinate coord = p.getCoordinate();
229     insertPoint(argIndex, coord, Location.INTERIOR);
230   }
231   
232   /**
233    * Adds a polygon ring to the graph.
234    * Empty rings are ignored.
235    * 
236    * The left and right topological location arguments assume that the ring is oriented CW.
237    * If the ring is in the opposite orientation,
238    * the left and right locations must be interchanged.
239    */
240   private void addPolygonRing(LinearRing lr, int cwLeft, int cwRight)
241   {
242       // don't bother adding empty holes
243       if (lr.isEmpty()) return;
244       
245     Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(lr.getCoordinates());
246  
247     if (coord.length < 4) {
248       hasTooFewPoints = true;
249       invalidPoint = coord[0];
250       return;
251     }
252  
253     int left  = cwLeft;
254     int right = cwRight;
255     if (Orientation.isCCW(coord)) {
256       left = cwRight;
257       right = cwLeft;
258     }
259     Edge e = new Edge(coord,
260                         new Label(argIndex, Location.BOUNDARY, left, right));
261     lineEdgeMap.put(lr, e);
262  
263     insertEdge(e);
264     // insert the endpoint as a node, to mark that it is on the boundary
265     insertPoint(argIndex, coord[0], Location.BOUNDARY);
266   }
267  
268   private void addPolygon(Polygon p)
269   {
270     addPolygonRing(
271             p.getExteriorRing(),
272             Location.EXTERIOR,
273             Location.INTERIOR);
274  
275     for (int i = 0; i < p.getNumInteriorRing(); i++) {
276         LinearRing hole = p.getInteriorRingN(i);
277         
278       // Holes are topologically labelled opposite to the shell, since
279       // the interior of the polygon lies on their opposite side
280       // (on the left, if the hole is oriented CW)
281       addPolygonRing(
282               hole,
283           Location.INTERIOR,
284           Location.EXTERIOR);
285     }
286   }
287  
288   private void addLineString(LineString line)
289   {
290     Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(line.getCoordinates());
291  
292     if (coord.length < 2) {
293       hasTooFewPoints = true;
294       invalidPoint = coord[0];
295       return;
296     }
297  
298     // add the edge for the LineString
299     // line edges do not have locations for their left and right sides
300     Edge e = new Edge(coord, new Label(argIndex, Location.INTERIOR));
301     lineEdgeMap.put(line, e);
302     insertEdge(e);
303     /**
304      * Add the boundary points of the LineString, if any.
305      * Even if the LineString is closed, add both points as if they were endpoints.
306      * This allows for the case that the node already exists and is a boundary point.
307      */
308     Assert.isTrue(coord.length >= 2, "found LineString with single point");
309     insertBoundaryPoint(argIndex, coord[0]);
310     insertBoundaryPoint(argIndex, coord[coord.length - 1]);
311  
312   }
313  
314   /**
315    * Add an Edge computed externally.  The label on the Edge is assumed
316    * to be correct.
317    */
318   public void addEdge(Edge e)
319   {
320     insertEdge(e);
321     Coordinate[] coord = e.getCoordinates();
322     // insert the endpoint as a node, to mark that it is on the boundary
323     insertPoint(argIndex, coord[0], Location.BOUNDARY);
324     insertPoint(argIndex, coord[coord.length - 1], Location.BOUNDARY);
325   }
326  
327   /**
328    * Add a point computed externally.  The point is assumed to be a
329    * Point Geometry part, which has a location of INTERIOR.
330    */
331   public void addPoint(Coordinate pt)
332   {
333     insertPoint(argIndex, pt, Location.INTERIOR);
334   }
335  
336   /**
337    * Compute self-nodes, taking advantage of the Geometry type to
338    * minimize the number of intersection tests.  (E.g. rings are
339    * not tested for self-intersection, since they are assumed to be valid).
340    * 
341    * @param li the LineIntersector to use
342    * @param computeRingSelfNodes if <code>false</code>, intersection checks are optimized to not test rings for self-intersection
343    * @return the computed SegmentIntersector containing information about the intersections found
344    */
345   public SegmentIntersector computeSelfNodes(LineIntersector li, boolean computeRingSelfNodes)
346   {
347       return computeSelfNodes(li, computeRingSelfNodes, false);
348   }
349   
350   /**
351    * Compute self-nodes, taking advantage of the Geometry type to
352    * minimize the number of intersection tests.  (E.g. rings are
353    * not tested for self-intersection, since they are assumed to be valid).
354    * 
355    * @param li the LineIntersector to use
356    * @param computeRingSelfNodes if <code>false</code>, intersection checks are optimized to not test rings for self-intersection
357    * @param isDoneIfProperInt short-circuit the intersection computation if a proper intersection is found
358    * @return the computed SegmentIntersector containing information about the intersections found
359    */
360   public SegmentIntersector computeSelfNodes(LineIntersector li, boolean computeRingSelfNodes, boolean isDoneIfProperInt)
361   {
362     SegmentIntersector si = new SegmentIntersector(li, true, false);
363     si.setIsDoneIfProperInt(isDoneIfProperInt);
364     EdgeSetIntersector esi = createEdgeSetIntersector();
365     // optimize intersection search for valid Polygons and LinearRings
366     boolean isRings = parentGeom instanceof LinearRing
367             || parentGeom instanceof Polygon
368             || parentGeom instanceof MultiPolygon;
369     boolean computeAllSegments = computeRingSelfNodes || ! isRings;
370     esi.computeIntersections(edges, si, computeAllSegments);
371     
372     //System.out.println("SegmentIntersector # tests = " + si.numTests);
373     addSelfIntersectionNodes(argIndex);
374     return si;
375   }
376  
377   public SegmentIntersector computeEdgeIntersections(
378     GeometryGraph g,
379     LineIntersector li,
380     boolean includeProper)
381   {
382     SegmentIntersector si = new SegmentIntersector(li, includeProper, true);
383     si.setBoundaryNodes(this.getBoundaryNodes(), g.getBoundaryNodes());
384  
385     EdgeSetIntersector esi = createEdgeSetIntersector();
386     esi.computeIntersections(edges, g.edges, si);
387 /*
388 for (Iterator i = g.edges.iterator(); i.hasNext();) {
389 Edge e = (Edge) i.next();
390 Debug.print(e.getEdgeIntersectionList());
391 }
392 */
393     return si;
394   }
395  
396   private void insertPoint(int argIndex, Coordinate coord, int onLocation)
397   {
398     Node n = nodes.addNode(coord);
399     Label lbl = n.getLabel();
400     if (lbl == null) {
401       n.label = new Label(argIndex, onLocation);
402     }
403     else
404       lbl.setLocation(argIndex, onLocation);
405   }
406  
407   /**
408    * Adds candidate boundary points using the current {@link BoundaryNodeRule}.
409    * This is used to add the boundary
410    * points of dim-1 geometries (Curves/MultiCurves).
411    */
412   private void insertBoundaryPoint(int argIndex, Coordinate coord)
413   {
414     Node n = nodes.addNode(coord);
415     // nodes always have labels
416     Label lbl = n.getLabel();
417     // the new point to insert is on a boundary
418     int boundaryCount = 1;
419     // determine the current location for the point (if any)
420     int loc = Location.NONE;
421     loc = lbl.getLocation(argIndex, Position.ON);
422     if (loc == Location.BOUNDARY) boundaryCount++;
423  
424     // determine the boundary status of the point according to the Boundary Determination Rule
425     int newLoc = determineBoundary(boundaryNodeRule, boundaryCount);
426     lbl.setLocation(argIndex, newLoc);
427   }
428  
429   private void addSelfIntersectionNodes(int argIndex)
430   {
431     for (Iterator i = edges.iterator(); i.hasNext(); ) {
432       Edge e = (Edge) i.next();
433       int eLoc = e.getLabel().getLocation(argIndex);
434       for (Iterator eiIt = e.eiList.iterator(); eiIt.hasNext(); ) {
435         EdgeIntersection ei = (EdgeIntersection) eiIt.next();
436         addSelfIntersectionNode(argIndex, ei.coord, eLoc);
437       }
438     }
439   }
440   /**
441    * Add a node for a self-intersection.
442    * If the node is a potential boundary node (e.g. came from an edge which
443    * is a boundary) then insert it as a potential boundary node.
444    * Otherwise, just add it as a regular node.
445    */
446   private void addSelfIntersectionNode(int argIndex, Coordinate coord, int loc)
447   {
448     // if this node is already a boundary node, don't change it
449     if (isBoundaryNode(argIndex, coord)) return;
450     if (loc == Location.BOUNDARY && useBoundaryDeterminationRule)
451         insertBoundaryPoint(argIndex, coord);
452     else
453       insertPoint(argIndex, coord, loc);
454   }
455  
456   // MD - experimental for now
457   /**
458    * Determines the {@link Location} of the given {@link Coordinate}
459    * in this geometry.
460    * 
461    * @param pt the point to test
462    * @return the location of the point in the geometry
463    */
464   public int locate(Coordinate pt)
465   {
466       if (parentGeom instanceof Polygonal && parentGeom.getNumGeometries() > 50) {
467           // lazily init point locator
468           if (areaPtLocator == null) {
469               areaPtLocator = new IndexedPointInAreaLocator(parentGeom);
470           }
471           return areaPtLocator.locate(pt);
472       }
473       return ptLocator.locate(pt, parentGeom);
474   }
475 }
476