001: /*
002: * The JTS Topology Suite is a collection of Java classes that
003: * implement the fundamental operations required to validate a given
004: * geo-spatial data set to a known topological specification.
005: *
006: * Copyright (C) 2001 Vivid Solutions
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: * For more information, contact:
023: *
024: * Vivid Solutions
025: * Suite #1A
026: * 2328 Government Street
027: * Victoria BC V8T 5G5
028: * Canada
029: *
030: * (250)385-6040
031: * www.vividsolutions.com
032: */
033:
034: package com.vividsolutions.jts.operation.polygonize;
035:
036: import java.util.*;
037: import com.vividsolutions.jts.geom.*;
038: import com.vividsolutions.jts.util.Assert;
039: import com.vividsolutions.jts.planargraph.*;
040:
041: /**
042: * Represents a planar graph of edges that can be used to compute a
043: * polygonization, and implements the algorithms to compute the
044: * {@link EdgeRings} formed by the graph.
045: * <p>
046: * The marked flag on {@link DirectedEdge}s is used to indicate that a directed edge
047: * has be logically deleted from the graph.
048: *
049: * @version 1.7
050: */
051: class PolygonizeGraph extends PlanarGraph {
052:
053: private static int getDegreeNonDeleted(Node node) {
054: List edges = node.getOutEdges().getEdges();
055: int degree = 0;
056: for (Iterator i = edges.iterator(); i.hasNext();) {
057: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i
058: .next();
059: if (!de.isMarked())
060: degree++;
061: }
062: return degree;
063: }
064:
065: private static int getDegree(Node node, long label) {
066: List edges = node.getOutEdges().getEdges();
067: int degree = 0;
068: for (Iterator i = edges.iterator(); i.hasNext();) {
069: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i
070: .next();
071: if (de.getLabel() == label)
072: degree++;
073: }
074: return degree;
075: }
076:
077: /**
078: * Deletes all edges at a node
079: */
080: public static void deleteAllEdges(Node node) {
081: List edges = node.getOutEdges().getEdges();
082: for (Iterator i = edges.iterator(); i.hasNext();) {
083: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i
084: .next();
085: de.setMarked(true);
086: PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de
087: .getSym();
088: if (sym != null)
089: sym.setMarked(true);
090: }
091: }
092:
093: private GeometryFactory factory;
094:
095: //private List labelledRings;
096:
097: /**
098: * Create a new polygonization graph.
099: */
100: public PolygonizeGraph(GeometryFactory factory) {
101: this .factory = factory;
102: }
103:
104: /**
105: * Add a {@link LineString} forming an edge of the polygon graph.
106: * @param line the line to add
107: */
108: public void addEdge(LineString line) {
109: if (line.isEmpty()) {
110: return;
111: }
112: Coordinate[] linePts = CoordinateArrays
113: .removeRepeatedPoints(line.getCoordinates());
114: Coordinate startPt = linePts[0];
115: Coordinate endPt = linePts[linePts.length - 1];
116:
117: Node nStart = getNode(startPt);
118: Node nEnd = getNode(endPt);
119:
120: DirectedEdge de0 = new PolygonizeDirectedEdge(nStart, nEnd,
121: linePts[1], true);
122: DirectedEdge de1 = new PolygonizeDirectedEdge(nEnd, nStart,
123: linePts[linePts.length - 2], false);
124: Edge edge = new PolygonizeEdge(line);
125: edge.setDirectedEdges(de0, de1);
126: add(edge);
127: }
128:
129: private Node getNode(Coordinate pt) {
130: Node node = findNode(pt);
131: if (node == null) {
132: node = new Node(pt);
133: // ensure node is only added once to graph
134: add(node);
135: }
136: return node;
137: }
138:
139: private void computeNextCWEdges() {
140: // set the next pointers for the edges around each node
141: for (Iterator iNode = nodeIterator(); iNode.hasNext();) {
142: Node node = (Node) iNode.next();
143: computeNextCWEdges(node);
144: }
145: }
146:
147: /**
148: * Convert the maximal edge rings found by the initial graph traversal
149: * into the minimal edge rings required by JTS polygon topology rules.
150: *
151: * @param ringEdges the list of start edges for the edgeRings to convert.
152: */
153: private void convertMaximalToMinimalEdgeRings(List ringEdges) {
154: for (Iterator i = ringEdges.iterator(); i.hasNext();) {
155: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i
156: .next();
157: long label = de.getLabel();
158: List intNodes = findIntersectionNodes(de, label);
159:
160: if (intNodes == null)
161: continue;
162: // flip the next pointers on the intersection nodes to create minimal edge rings
163: for (Iterator iNode = intNodes.iterator(); iNode.hasNext();) {
164: Node node = (Node) iNode.next();
165: computeNextCCWEdges(node, label);
166: }
167: }
168: }
169:
170: /**
171: * Finds all nodes in a maximal edgering which are self-intersection nodes
172: * @param startDE
173: * @param label
174: * @return the list of intersection nodes found,
175: * or <code>null</code> if no intersection nodes were found
176: */
177: private static List findIntersectionNodes(
178: PolygonizeDirectedEdge startDE, long label) {
179: PolygonizeDirectedEdge de = startDE;
180: List intNodes = null;
181: do {
182: Node node = de.getFromNode();
183: if (getDegree(node, label) > 1) {
184: if (intNodes == null)
185: intNodes = new ArrayList();
186: intNodes.add(node);
187: }
188:
189: de = de.getNext();
190: Assert.isTrue(de != null, "found null DE in ring");
191: Assert.isTrue(de == startDE || !de.isInRing(),
192: "found DE already in ring");
193: } while (de != startDE);
194:
195: return intNodes;
196: }
197:
198: /**
199: * Computes the EdgeRings formed by the edges in this graph.
200: * @return a list of the {@link EdgeRing}s found by the polygonization process.
201: */
202: public List getEdgeRings() {
203: // maybe could optimize this, since most of these pointers should be set correctly already
204: // by deleteCutEdges()
205: computeNextCWEdges();
206: // clear labels of all edges in graph
207: label(dirEdges, -1);
208: List maximalRings = findLabeledEdgeRings(dirEdges);
209: convertMaximalToMinimalEdgeRings(maximalRings);
210:
211: // find all edgerings
212: List edgeRingList = new ArrayList();
213: for (Iterator i = dirEdges.iterator(); i.hasNext();) {
214: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i
215: .next();
216: if (de.isMarked())
217: continue;
218: if (de.isInRing())
219: continue;
220:
221: EdgeRing er = findEdgeRing(de);
222: edgeRingList.add(er);
223: }
224: return edgeRingList;
225: }
226:
227: /**
228: *
229: * @param dirEdges a List of the DirectedEdges in the graph
230: * @return a List of DirectedEdges, one for each edge ring found
231: */
232: private static List findLabeledEdgeRings(Collection dirEdges) {
233: List edgeRingStarts = new ArrayList();
234: // label the edge rings formed
235: long currLabel = 1;
236: for (Iterator i = dirEdges.iterator(); i.hasNext();) {
237: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i
238: .next();
239: if (de.isMarked())
240: continue;
241: if (de.getLabel() >= 0)
242: continue;
243:
244: edgeRingStarts.add(de);
245: List edges = findDirEdgesInRing(de);
246:
247: label(edges, currLabel);
248: currLabel++;
249: }
250: return edgeRingStarts;
251: }
252:
253: /**
254: * Finds and removes all cut edges from the graph.
255: * @return a list of the {@link LineString}s forming the removed cut edges
256: */
257: public List deleteCutEdges() {
258: computeNextCWEdges();
259: // label the current set of edgerings
260: findLabeledEdgeRings(dirEdges);
261:
262: /**
263: * Cut Edges are edges where both dirEdges have the same label.
264: * Delete them, and record them
265: */
266: List cutLines = new ArrayList();
267: for (Iterator i = dirEdges.iterator(); i.hasNext();) {
268: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i
269: .next();
270: if (de.isMarked())
271: continue;
272:
273: PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de
274: .getSym();
275:
276: if (de.getLabel() == sym.getLabel()) {
277: de.setMarked(true);
278: sym.setMarked(true);
279:
280: // save the line as a cut edge
281: PolygonizeEdge e = (PolygonizeEdge) de.getEdge();
282: cutLines.add(e.getLine());
283: }
284: }
285: return cutLines;
286: }
287:
288: private static void label(Collection dirEdges, long label) {
289: for (Iterator i = dirEdges.iterator(); i.hasNext();) {
290: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i
291: .next();
292: de.setLabel(label);
293: }
294: }
295:
296: private static void computeNextCWEdges(Node node) {
297: DirectedEdgeStar deStar = node.getOutEdges();
298: PolygonizeDirectedEdge startDE = null;
299: PolygonizeDirectedEdge prevDE = null;
300:
301: // the edges are stored in CCW order around the star
302: for (Iterator i = deStar.getEdges().iterator(); i.hasNext();) {
303: PolygonizeDirectedEdge outDE = (PolygonizeDirectedEdge) i
304: .next();
305: if (outDE.isMarked())
306: continue;
307:
308: if (startDE == null)
309: startDE = outDE;
310: if (prevDE != null) {
311: PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) prevDE
312: .getSym();
313: sym.setNext(outDE);
314: }
315: prevDE = outDE;
316: }
317: if (prevDE != null) {
318: PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) prevDE
319: .getSym();
320: sym.setNext(startDE);
321: }
322: }
323:
324: /**
325: * Computes the next edge pointers going CCW around the given node, for the
326: * given edgering label.
327: * This algorithm has the effect of converting maximal edgerings into minimal edgerings
328: */
329: private static void computeNextCCWEdges(Node node, long label) {
330: DirectedEdgeStar deStar = node.getOutEdges();
331: //PolyDirectedEdge lastInDE = null;
332: PolygonizeDirectedEdge firstOutDE = null;
333: PolygonizeDirectedEdge prevInDE = null;
334:
335: // the edges are stored in CCW order around the star
336: List edges = deStar.getEdges();
337: //for (Iterator i = deStar.getEdges().iterator(); i.hasNext(); ) {
338: for (int i = edges.size() - 1; i >= 0; i--) {
339: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) edges
340: .get(i);
341: PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de
342: .getSym();
343:
344: PolygonizeDirectedEdge outDE = null;
345: if (de.getLabel() == label)
346: outDE = de;
347: PolygonizeDirectedEdge inDE = null;
348: if (sym.getLabel() == label)
349: inDE = sym;
350:
351: if (outDE == null && inDE == null)
352: continue; // this edge is not in edgering
353:
354: if (inDE != null) {
355: prevInDE = inDE;
356: }
357:
358: if (outDE != null) {
359: if (prevInDE != null) {
360: prevInDE.setNext(outDE);
361: prevInDE = null;
362: }
363: if (firstOutDE == null)
364: firstOutDE = outDE;
365: }
366: }
367: if (prevInDE != null) {
368: Assert.isTrue(firstOutDE != null);
369: prevInDE.setNext(firstOutDE);
370: }
371: }
372:
373: /**
374: * Traverse a ring of DirectedEdges, accumulating them into a list.
375: * This assumes that all dangling directed edges have been removed
376: * from the graph, so that there is always a next dirEdge.
377: *
378: * @param startDE the DirectedEdge to start traversing at
379: * @return a List of DirectedEdges that form a ring
380: */
381: private static List findDirEdgesInRing(
382: PolygonizeDirectedEdge startDE) {
383: PolygonizeDirectedEdge de = startDE;
384: List edges = new ArrayList();
385: do {
386: edges.add(de);
387: de = de.getNext();
388: Assert.isTrue(de != null, "found null DE in ring");
389: Assert.isTrue(de == startDE || !de.isInRing(),
390: "found DE already in ring");
391: } while (de != startDE);
392:
393: return edges;
394: }
395:
396: private EdgeRing findEdgeRing(PolygonizeDirectedEdge startDE) {
397: PolygonizeDirectedEdge de = startDE;
398: EdgeRing er = new EdgeRing(factory);
399: do {
400: er.add(de);
401: de.setRing(er);
402: de = de.getNext();
403: Assert.isTrue(de != null, "found null DE in ring");
404: Assert.isTrue(de == startDE || !de.isInRing(),
405: "found DE already in ring");
406: } while (de != startDE);
407:
408: return er;
409: }
410:
411: /**
412: * Marks all edges from the graph which are "dangles".
413: * Dangles are which are incident on a node with degree 1.
414: * This process is recursive, since removing a dangling edge
415: * may result in another edge becoming a dangle.
416: * In order to handle large recursion depths efficiently,
417: * an explicit recursion stack is used
418: *
419: * @return a List containing the {@link LineStrings} that formed dangles
420: */
421: public Collection deleteDangles() {
422: List nodesToRemove = findNodesOfDegree(1);
423: Set dangleLines = new HashSet();
424:
425: Stack nodeStack = new Stack();
426: for (Iterator i = nodesToRemove.iterator(); i.hasNext();) {
427: nodeStack.push(i.next());
428: }
429:
430: while (!nodeStack.isEmpty()) {
431: Node node = (Node) nodeStack.pop();
432:
433: deleteAllEdges(node);
434: List nodeOutEdges = node.getOutEdges().getEdges();
435: for (Iterator i = nodeOutEdges.iterator(); i.hasNext();) {
436: PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i
437: .next();
438: // delete this edge and its sym
439: de.setMarked(true);
440: PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de
441: .getSym();
442: if (sym != null)
443: sym.setMarked(true);
444:
445: // save the line as a dangle
446: PolygonizeEdge e = (PolygonizeEdge) de.getEdge();
447: dangleLines.add(e.getLine());
448:
449: Node toNode = de.getToNode();
450: // add the toNode to the list to be processed, if it is now a dangle
451: if (getDegreeNonDeleted(toNode) == 1)
452: nodeStack.push(toNode);
453: }
454: }
455: return dangleLines;
456: }
457: }
|