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.geomgraph;
035:
036: import java.util.*;
037: import com.vividsolutions.jts.algorithm.*;
038: import com.vividsolutions.jts.geom.*;
039: import com.vividsolutions.jts.geomgraph.index.*;
040: import com.vividsolutions.jts.util.*;
041:
042: /**
043: * A GeometryGraph is a graph that models a given Geometry
044: * @version 1.7
045: */
046: public class GeometryGraph extends PlanarGraph {
047: /**
048: * This method implements the Boundary Determination Rule
049: * for determining whether
050: * a component (node or edge) that appears multiple times in elements
051: * of a MultiGeometry is in the boundary or the interior of the Geometry
052: * <br>
053: * The SFS uses the "Mod-2 Rule", which this function implements
054: * <br>
055: * An alternative (and possibly more intuitive) rule would be
056: * the "At Most One Rule":
057: * isInBoundary = (componentCount == 1)
058: */
059: /*
060: public static boolean isInBoundary(int boundaryCount)
061: {
062: // the "Mod-2 Rule"
063: return boundaryCount % 2 == 1;
064: }
065: public static int determineBoundary(int boundaryCount)
066: {
067: return isInBoundary(boundaryCount) ? Location.BOUNDARY : Location.INTERIOR;
068: }
069: */
070:
071: public static int determineBoundary(
072: BoundaryNodeRule boundaryNodeRule, int boundaryCount) {
073: return boundaryNodeRule.isInBoundary(boundaryCount) ? Location.BOUNDARY
074: : Location.INTERIOR;
075: }
076:
077: private Geometry parentGeom;
078:
079: /**
080: * The lineEdgeMap is a map of the linestring components of the
081: * parentGeometry to the edges which are derived from them.
082: * This is used to efficiently perform findEdge queries
083: */
084: private Map lineEdgeMap = new HashMap();
085:
086: private BoundaryNodeRule boundaryNodeRule = null;
087:
088: /**
089: * If this flag is true, the Boundary Determination Rule will used when deciding
090: * whether nodes are in the boundary or not
091: */
092: private boolean useBoundaryDeterminationRule = true;
093: private int argIndex; // the index of this geometry as an argument to a spatial function (used for labelling)
094: private Collection boundaryNodes;
095: private boolean hasTooFewPoints = false;
096: private Coordinate invalidPoint = null;
097:
098: private EdgeSetIntersector createEdgeSetIntersector() {
099: // various options for computing intersections, from slowest to fastest
100:
101: //private EdgeSetIntersector esi = new SimpleEdgeSetIntersector();
102: //private EdgeSetIntersector esi = new MonotoneChainIntersector();
103: //private EdgeSetIntersector esi = new NonReversingChainIntersector();
104: //private EdgeSetIntersector esi = new SimpleSweepLineIntersector();
105: //private EdgeSetIntersector esi = new MCSweepLineIntersector();
106:
107: //return new SimpleEdgeSetIntersector();
108: return new SimpleMCSweepLineIntersector();
109: }
110:
111: public GeometryGraph(int argIndex, Geometry parentGeom) {
112: this (argIndex, parentGeom,
113: BoundaryNodeRule.OGC_SFS_BOUNDARY_RULE);
114: }
115:
116: public GeometryGraph(int argIndex, Geometry parentGeom,
117: BoundaryNodeRule boundaryNodeRule) {
118: this .argIndex = argIndex;
119: this .parentGeom = parentGeom;
120: this .boundaryNodeRule = boundaryNodeRule;
121: if (parentGeom != null) {
122: // precisionModel = parentGeom.getPrecisionModel();
123: // SRID = parentGeom.getSRID();
124: add(parentGeom);
125: }
126: }
127:
128: /**
129: * This constructor is used by clients that wish to add Edges explicitly,
130: * rather than adding a Geometry. (An example is BufferOp).
131: */
132: // no longer used
133: // public GeometryGraph(int argIndex, PrecisionModel precisionModel, int SRID) {
134: // this(argIndex, null);
135: // this.precisionModel = precisionModel;
136: // this.SRID = SRID;
137: // }
138: // public PrecisionModel getPrecisionModel()
139: // {
140: // return precisionModel;
141: // }
142: // public int getSRID() { return SRID; }
143: public boolean hasTooFewPoints() {
144: return hasTooFewPoints;
145: }
146:
147: public Coordinate getInvalidPoint() {
148: return invalidPoint;
149: }
150:
151: public Geometry getGeometry() {
152: return parentGeom;
153: }
154:
155: public BoundaryNodeRule getBoundaryNodeRule() {
156: return boundaryNodeRule;
157: }
158:
159: public Collection getBoundaryNodes() {
160: if (boundaryNodes == null)
161: boundaryNodes = nodes.getBoundaryNodes(argIndex);
162: return boundaryNodes;
163: }
164:
165: public Coordinate[] getBoundaryPoints() {
166: Collection coll = getBoundaryNodes();
167: Coordinate[] pts = new Coordinate[coll.size()];
168: int i = 0;
169: for (Iterator it = coll.iterator(); it.hasNext();) {
170: Node node = (Node) it.next();
171: pts[i++] = (Coordinate) node.getCoordinate().clone();
172: }
173: return pts;
174: }
175:
176: public Edge findEdge(LineString line) {
177: return (Edge) lineEdgeMap.get(line);
178: }
179:
180: public void computeSplitEdges(List edgelist) {
181: for (Iterator i = edges.iterator(); i.hasNext();) {
182: Edge e = (Edge) i.next();
183: e.eiList.addSplitEdges(edgelist);
184: }
185: }
186:
187: private void add(Geometry g) {
188: if (g.isEmpty())
189: return;
190:
191: // check if this Geometry should obey the Boundary Determination Rule
192: // all collections except MultiPolygons obey the rule
193: if (g instanceof MultiPolygon)
194: useBoundaryDeterminationRule = false;
195:
196: if (g instanceof Polygon)
197: addPolygon((Polygon) g);
198: // LineString also handles LinearRings
199: else if (g instanceof LineString)
200: addLineString((LineString) g);
201: else if (g instanceof Point)
202: addPoint((Point) g);
203: else if (g instanceof MultiPoint)
204: addCollection((MultiPoint) g);
205: else if (g instanceof MultiLineString)
206: addCollection((MultiLineString) g);
207: else if (g instanceof MultiPolygon)
208: addCollection((MultiPolygon) g);
209: else if (g instanceof GeometryCollection)
210: addCollection((GeometryCollection) g);
211: else
212: throw new UnsupportedOperationException(g.getClass()
213: .getName());
214: }
215:
216: private void addCollection(GeometryCollection gc) {
217: for (int i = 0; i < gc.getNumGeometries(); i++) {
218: Geometry g = gc.getGeometryN(i);
219: add(g);
220: }
221: }
222:
223: /**
224: * Add a Point to the graph.
225: */
226: private void addPoint(Point p) {
227: Coordinate coord = p.getCoordinate();
228: insertPoint(argIndex, coord, Location.INTERIOR);
229: }
230:
231: /**
232: * The left and right topological location arguments assume that the ring is oriented CW.
233: * If the ring is in the opposite orientation,
234: * the left and right locations must be interchanged.
235: */
236: private void addPolygonRing(LinearRing lr, int cwLeft, int cwRight) {
237: Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(lr
238: .getCoordinates());
239:
240: if (coord.length < 4) {
241: hasTooFewPoints = true;
242: invalidPoint = coord[0];
243: return;
244: }
245:
246: int left = cwLeft;
247: int right = cwRight;
248: if (cga.isCCW(coord)) {
249: left = cwRight;
250: right = cwLeft;
251: }
252: Edge e = new Edge(coord, new Label(argIndex, Location.BOUNDARY,
253: left, right));
254: lineEdgeMap.put(lr, e);
255:
256: insertEdge(e);
257: // insert the endpoint as a node, to mark that it is on the boundary
258: insertPoint(argIndex, coord[0], Location.BOUNDARY);
259: }
260:
261: private void addPolygon(Polygon p) {
262: addPolygonRing((LinearRing) p.getExteriorRing(),
263: Location.EXTERIOR, Location.INTERIOR);
264:
265: for (int i = 0; i < p.getNumInteriorRing(); i++) {
266: // Holes are topologically labelled opposite to the shell, since
267: // the interior of the polygon lies on their opposite side
268: // (on the left, if the hole is oriented CW)
269: addPolygonRing((LinearRing) p.getInteriorRingN(i),
270: Location.INTERIOR, Location.EXTERIOR);
271: }
272: }
273:
274: private void addLineString(LineString line) {
275: Coordinate[] coord = CoordinateArrays.removeRepeatedPoints(line
276: .getCoordinates());
277:
278: if (coord.length < 2) {
279: hasTooFewPoints = true;
280: invalidPoint = coord[0];
281: return;
282: }
283:
284: // add the edge for the LineString
285: // line edges do not have locations for their left and right sides
286: Edge e = new Edge(coord, new Label(argIndex, Location.INTERIOR));
287: lineEdgeMap.put(line, e);
288: insertEdge(e);
289: /**
290: * Add the boundary points of the LineString, if any.
291: * Even if the LineString is closed, add both points as if they were endpoints.
292: * This allows for the case that the node already exists and is a boundary point.
293: */
294: Assert.isTrue(coord.length >= 2,
295: "found LineString with single point");
296: insertBoundaryPoint(argIndex, coord[0]);
297: insertBoundaryPoint(argIndex, coord[coord.length - 1]);
298:
299: }
300:
301: /**
302: * Add an Edge computed externally. The label on the Edge is assumed
303: * to be correct.
304: */
305: public void addEdge(Edge e) {
306: insertEdge(e);
307: Coordinate[] coord = e.getCoordinates();
308: // insert the endpoint as a node, to mark that it is on the boundary
309: insertPoint(argIndex, coord[0], Location.BOUNDARY);
310: insertPoint(argIndex, coord[coord.length - 1],
311: Location.BOUNDARY);
312: }
313:
314: /**
315: * Add a point computed externally. The point is assumed to be a
316: * Point Geometry part, which has a location of INTERIOR.
317: */
318: public void addPoint(Coordinate pt) {
319: insertPoint(argIndex, pt, Location.INTERIOR);
320: }
321:
322: /**
323: * Compute self-nodes, taking advantage of the Geometry type to
324: * minimize the number of intersection tests. (E.g. rings are
325: * not tested for self-intersection, since they are assumed to be valid).
326: * @param li the LineIntersector to use
327: * @param computeRingSelfNodes if <false>, intersection checks are optimized to not test rings for self-intersection
328: * @return the SegmentIntersector used, containing information about the intersections found
329: */
330: public SegmentIntersector computeSelfNodes(LineIntersector li,
331: boolean computeRingSelfNodes) {
332: SegmentIntersector si = new SegmentIntersector(li, true, false);
333: EdgeSetIntersector esi = createEdgeSetIntersector();
334: // optimized test for Polygons and Rings
335: if (!computeRingSelfNodes
336: && (parentGeom instanceof LinearRing
337: || parentGeom instanceof Polygon || parentGeom instanceof MultiPolygon)) {
338: esi.computeIntersections(edges, si, false);
339: } else {
340: esi.computeIntersections(edges, si, true);
341: }
342: //System.out.println("SegmentIntersector # tests = " + si.numTests);
343: addSelfIntersectionNodes(argIndex);
344: return si;
345: }
346:
347: /* NOT USED
348: public SegmentIntersector computeSelfNodes(LineIntersector li)
349: {
350: return computeSelfNodes(li, false);
351: }
352: */
353: public SegmentIntersector computeEdgeIntersections(GeometryGraph g,
354: LineIntersector li, boolean includeProper) {
355: SegmentIntersector si = new SegmentIntersector(li,
356: includeProper, true);
357: si.setBoundaryNodes(this .getBoundaryNodes(), g
358: .getBoundaryNodes());
359:
360: EdgeSetIntersector esi = createEdgeSetIntersector();
361: esi.computeIntersections(edges, g.edges, si);
362: /*
363: for (Iterator i = g.edges.iterator(); i.hasNext();) {
364: Edge e = (Edge) i.next();
365: Debug.print(e.getEdgeIntersectionList());
366: }
367: */
368: return si;
369: }
370:
371: private void insertPoint(int argIndex, Coordinate coord,
372: int onLocation) {
373: Node n = nodes.addNode(coord);
374: Label lbl = n.getLabel();
375: if (lbl == null) {
376: n.label = new Label(argIndex, onLocation);
377: } else
378: lbl.setLocation(argIndex, onLocation);
379: }
380:
381: /**
382: * Adds candidate boundary points using the current {@link BoundaryNodeRule}.
383: * This is used to add the boundary
384: * points of dim-1 geometries (Curves/MultiCurves).
385: */
386: private void insertBoundaryPoint(int argIndex, Coordinate coord) {
387: Node n = nodes.addNode(coord);
388: Label lbl = n.getLabel();
389: // the new point to insert is on a boundary
390: int boundaryCount = 1;
391: // determine the current location for the point (if any)
392: int loc = Location.NONE;
393: if (lbl != null)
394: loc = lbl.getLocation(argIndex, Position.ON);
395: if (loc == Location.BOUNDARY)
396: boundaryCount++;
397:
398: // determine the boundary status of the point according to the Boundary Determination Rule
399: int newLoc = determineBoundary(boundaryNodeRule, boundaryCount);
400: lbl.setLocation(argIndex, newLoc);
401: }
402:
403: private void addSelfIntersectionNodes(int argIndex) {
404: for (Iterator i = edges.iterator(); i.hasNext();) {
405: Edge e = (Edge) i.next();
406: int eLoc = e.getLabel().getLocation(argIndex);
407: for (Iterator eiIt = e.eiList.iterator(); eiIt.hasNext();) {
408: EdgeIntersection ei = (EdgeIntersection) eiIt.next();
409: addSelfIntersectionNode(argIndex, ei.coord, eLoc);
410: }
411: }
412: }
413:
414: /**
415: * Add a node for a self-intersection.
416: * If the node is a potential boundary node (e.g. came from an edge which
417: * is a boundary) then insert it as a potential boundary node.
418: * Otherwise, just add it as a regular node.
419: */
420: private void addSelfIntersectionNode(int argIndex,
421: Coordinate coord, int loc) {
422: // if this node is already a boundary node, don't change it
423: if (isBoundaryNode(argIndex, coord))
424: return;
425: if (loc == Location.BOUNDARY && useBoundaryDeterminationRule)
426: insertBoundaryPoint(argIndex, coord);
427: else
428: insertPoint(argIndex, coord, loc);
429: }
430:
431: }
|