Doc Classic

Class PolygonizeGraph

  1  
  2 /*
  3  * Copyright (c) 2016 Vivid Solutions.
  4  *
  5  * All rights reserved. This program and the accompanying materials
  6  * are made available under the terms of the Eclipse Public License 2.0
  7  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
  8  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
  9  * and the Eclipse Distribution License is available at
 10  *
 11  * http://www.eclipse.org/org/documents/edl-v10.php.
 12  */
 13  
 14  
 15 package org.locationtech.jts.operation.polygonize;
 16  
 17 import java.util.ArrayList;
 18 import java.util.Collection;
 19 import java.util.HashSet;
 20 import java.util.Iterator;
 21 import java.util.List;
 22 import java.util.Set;
 23 import java.util.Stack;
 24  
 25 import org.locationtech.jts.geom.Coordinate;
 26 import org.locationtech.jts.geom.CoordinateArrays;
 27 import org.locationtech.jts.geom.GeometryFactory;
 28 import org.locationtech.jts.geom.LineString;
 29 import org.locationtech.jts.planargraph.DirectedEdge;
 30 import org.locationtech.jts.planargraph.DirectedEdgeStar;
 31 import org.locationtech.jts.planargraph.Edge;
 32 import org.locationtech.jts.planargraph.Node;
 33 import org.locationtech.jts.planargraph.PlanarGraph;
 34 import org.locationtech.jts.util.Assert;
 35  
 36 /**
 37  * Represents a planar graph of edges that can be used to compute a
 38  * polygonization, and implements the algorithms to compute the
 39  * {@link EdgeRings} formed by the graph.
 40  * <p>
 41  * The marked flag on {@link DirectedEdge}s is used to indicate that a directed edge
 42  * has be logically deleted from the graph.
 43  *
 44  * @version 1.7
 45  */
 46 class PolygonizeGraph
 47     extends PlanarGraph
 48 {
 49  
 50   private static int getDegreeNonDeleted(Node node)
 51   {
 52     List edges = node.getOutEdges().getEdges();
 53     int degree = 0;
 54     for (Iterator i = edges.iterator(); i.hasNext(); ) {
 55       PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
 56       if (! de.isMarked()) degree++;
 57     }
 58     return degree;
 59   }
 60  
 61   private static int getDegree(Node node, long label)
 62   {
 63     List edges = node.getOutEdges().getEdges();
 64     int degree = 0;
 65     for (Iterator i = edges.iterator(); i.hasNext(); ) {
 66       PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
 67       if (de.getLabel() == label) degree++;
 68     }
 69     return degree;
 70   }
 71  
 72   /**
 73    * Deletes all edges at a node
 74    */
 75   public static void deleteAllEdges(Node node)
 76   {
 77     List edges = node.getOutEdges().getEdges();
 78     for (Iterator i = edges.iterator(); i.hasNext(); ) {
 79       PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
 80       de.setMarked(true);
 81       PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de.getSym();
 82       if (sym != null)
 83         sym.setMarked(true);
 84     }
 85   }
 86  
 87   private GeometryFactory factory;
 88  
 89   //private List labelledRings;
 90  
 91   /**
 92    * Create a new polygonization graph.
 93    */
 94   public PolygonizeGraph(GeometryFactory factory)
 95   {
 96     this.factory = factory;
 97   }
 98  
 99   /**
100    * Add a {@link LineString} forming an edge of the polygon graph.
101    * @param line the line to add
102    */
103   public void addEdge(LineString line)
104   {
105     if (line.isEmpty()) { return; }
106     Coordinate[] linePts = CoordinateArrays.removeRepeatedPoints(line.getCoordinates());
107     
108     if (linePts.length < 2) { return; }
109     
110     Coordinate startPt = linePts[0];
111     Coordinate endPt = linePts[linePts.length - 1];
112  
113     Node nStart = getNode(startPt);
114     Node nEnd = getNode(endPt);
115  
116     DirectedEdge de0 = new PolygonizeDirectedEdge(nStart, nEnd, linePts[1], true);
117     DirectedEdge de1 = new PolygonizeDirectedEdge(nEnd, nStart, linePts[linePts.length - 2], false);
118     Edge edge = new PolygonizeEdge(line);
119     edge.setDirectedEdges(de0, de1);
120     add(edge);
121   }
122  
123   private Node getNode(Coordinate pt)
124   {
125     Node node = findNode(pt);
126     if (node == null) {
127       node = new Node(pt);
128       // ensure node is only added once to graph
129       add(node);
130     }
131     return node;
132   }
133  
134   private void computeNextCWEdges()
135   {
136     // set the next pointers for the edges around each node
137     for (Iterator iNode = nodeIterator(); iNode.hasNext(); ) {
138       Node node = (Node) iNode.next();
139       computeNextCWEdges(node);
140     }
141   }
142  
143   /**
144    * Convert the maximal edge rings found by the initial graph traversal
145    * into the minimal edge rings required by JTS polygon topology rules.
146    *
147    * @param ringEdges the list of start edges for the edgeRings to convert.
148    */
149   private void convertMaximalToMinimalEdgeRings(List ringEdges)
150   {
151     for (Iterator i = ringEdges.iterator(); i.hasNext(); ) {
152       PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
153       long label = de.getLabel();
154       List intNodes = findIntersectionNodes(de, label);
155  
156       if (intNodes == null) continue;
157       // flip the next pointers on the intersection nodes to create minimal edge rings
158       for (Iterator iNode = intNodes.iterator(); iNode.hasNext(); ) {
159         Node node = (Node) iNode.next();
160         computeNextCCWEdges(node, label);
161       }
162     }
163   }
164  
165   /**
166    * Finds all nodes in a maximal edgering which are self-intersection nodes
167    * @param startDE
168    * @param label
169    * @return the list of intersection nodes found,
170    * or <code>null</code> if no intersection nodes were found
171    */
172   private static List findIntersectionNodes(PolygonizeDirectedEdge startDE, long label)
173   {
174     PolygonizeDirectedEdge de = startDE;
175     List intNodes = null;
176     do {
177       Node node = de.getFromNode();
178       if (getDegree(node, label) > 1) {
179         if (intNodes == null)
180           intNodes = new ArrayList();
181         intNodes.add(node);
182       }
183  
184       de = de.getNext();
185       Assert.isTrue(de != null, "found null DE in ring");
186       Assert.isTrue(de == startDE || ! de.isInRing(), "found DE already in ring");
187     } while (de != startDE);
188  
189     return intNodes;
190   }
191  
192   /**
193    * Computes the minimal EdgeRings formed by the edges in this graph.
194    * @return a list of the {@link EdgeRing}s found by the polygonization process.
195    */
196   public List getEdgeRings()
197   {
198     // maybe could optimize this, since most of these pointers should be set correctly already
199     // by deleteCutEdges()
200     computeNextCWEdges();
201     // clear labels of all edges in graph
202     label(dirEdges, -1);
203     List maximalRings = findLabeledEdgeRings(dirEdges);
204     convertMaximalToMinimalEdgeRings(maximalRings);
205  
206     // find all edgerings (which will now be minimal ones, as required)
207     List edgeRingList = new ArrayList();
208     for (Iterator i = dirEdges.iterator(); i.hasNext(); ) {
209       PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
210       if (de.isMarked()) continue;
211       if (de.isInRing()) continue;
212  
213       EdgeRing er = findEdgeRing(de);
214       edgeRingList.add(er);
215     }
216     return edgeRingList;
217   }
218  
219   /**
220    * Finds and labels all edgerings in the graph.
221    * The edge rings are labeling with unique integers.
222    * The labeling allows detecting cut edges.
223    * 
224    * @param dirEdges a List of the DirectedEdges in the graph
225    * @return a List of DirectedEdges, one for each edge ring found
226    */
227   private static List findLabeledEdgeRings(Collection dirEdges)
228   {
229     List edgeRingStarts = new ArrayList();
230     // label the edge rings formed
231     long currLabel = 1;
232     for (Iterator i = dirEdges.iterator(); i.hasNext(); ) {
233       PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
234       if (de.isMarked()) continue;
235       if (de.getLabel() >= 0) continue;
236  
237       edgeRingStarts.add(de);
238       List edges = EdgeRing.findDirEdgesInRing(de);
239  
240       label(edges, currLabel);
241       currLabel++;
242     }
243     return edgeRingStarts;
244   }
245  
246   /**
247    * Finds and removes all cut edges from the graph.
248    * @return a list of the {@link LineString}s forming the removed cut edges
249    */
250   public List deleteCutEdges()
251   {
252     computeNextCWEdges();
253     // label the current set of edgerings
254     findLabeledEdgeRings(dirEdges);
255  
256     /**
257      * Cut Edges are edges where both dirEdges have the same label.
258      * Delete them, and record them
259      */
260     List cutLines = new ArrayList();
261     for (Iterator i = dirEdges.iterator(); i.hasNext(); ) {
262       PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
263       if (de.isMarked()) continue;
264  
265       PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de.getSym();
266  
267       if (de.getLabel() == sym.getLabel()) {
268         de.setMarked(true);
269         sym.setMarked(true);
270  
271         // save the line as a cut edge
272         PolygonizeEdge e = (PolygonizeEdge) de.getEdge();
273         cutLines.add(e.getLine());
274       }
275     }
276     return cutLines;
277   }
278  
279   private static void label(Collection dirEdges, long label)
280   {
281     for (Iterator i = dirEdges.iterator(); i.hasNext(); ) {
282       PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
283       de.setLabel(label);
284     }
285   }
286   private static void computeNextCWEdges(Node node)
287   {
288     DirectedEdgeStar deStar = node.getOutEdges();
289     PolygonizeDirectedEdge startDE = null;
290     PolygonizeDirectedEdge prevDE = null;
291  
292     // the edges are stored in CCW order around the star
293     for (Iterator i = deStar.getEdges().iterator(); i.hasNext(); ) {
294       PolygonizeDirectedEdge outDE = (PolygonizeDirectedEdge) i.next();
295       if (outDE.isMarked()) continue;
296  
297       if (startDE == null)
298         startDE = outDE;
299       if (prevDE != null) {
300         PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) prevDE.getSym();
301         sym.setNext(outDE);
302       }
303       prevDE = outDE;
304     }
305     if (prevDE != null) {
306       PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) prevDE.getSym();
307       sym.setNext(startDE);
308     }
309   }
310   /**
311    * Computes the next edge pointers going CCW around the given node, for the
312    * given edgering label.
313    * This algorithm has the effect of converting maximal edgerings into minimal edgerings
314    */
315   private static void computeNextCCWEdges(Node node, long label)
316   {
317     DirectedEdgeStar deStar = node.getOutEdges();
318     //PolyDirectedEdge lastInDE = null;
319     PolygonizeDirectedEdge firstOutDE = null;
320     PolygonizeDirectedEdge prevInDE = null;
321  
322     // the edges are stored in CCW order around the star
323     List edges = deStar.getEdges();
324     //for (Iterator i = deStar.getEdges().iterator(); i.hasNext(); ) {
325     for (int i = edges.size() - 1; i >= 0; i--) {
326       PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) edges.get(i);
327       PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de.getSym();
328  
329       PolygonizeDirectedEdge outDE = null;
330       if (  de.getLabel() == label) outDE = de;
331       PolygonizeDirectedEdge inDE = null;
332       if (  sym.getLabel() == label) inDE =  sym;
333  
334       if (outDE == null && inDE == null) continue;  // this edge is not in edgering
335  
336       if (inDE != null) {
337         prevInDE = inDE;
338       }
339  
340       if (outDE != null) {
341         if (prevInDE != null) {
342           prevInDE.setNext(outDE);
343           prevInDE = null;
344         }
345         if (firstOutDE == null)
346           firstOutDE = outDE;
347       }
348     }
349     if (prevInDE != null) {
350       Assert.isTrue(firstOutDE != null);
351       prevInDE.setNext(firstOutDE);
352     }
353   }
354  
355   private EdgeRing findEdgeRing(PolygonizeDirectedEdge startDE)
356   {
357     EdgeRing er = new EdgeRing(factory);
358     er.build(startDE);
359     return er;
360   }
361  
362   /**
363    * Marks all edges from the graph which are "dangles".
364    * Dangles are which are incident on a node with degree 1.
365    * This process is recursive, since removing a dangling edge
366    * may result in another edge becoming a dangle.
367    * In order to handle large recursion depths efficiently,
368    * an explicit recursion stack is used
369    *
370    * @return a List containing the {@link LineString}s that formed dangles
371    */
372   public Collection deleteDangles()
373   {
374     List nodesToRemove = findNodesOfDegree(1);
375     Set dangleLines = new HashSet();
376  
377     Stack nodeStack = new Stack();
378     for (Iterator i = nodesToRemove.iterator(); i.hasNext(); ) {
379       nodeStack.push(i.next());
380     }
381  
382     while (! nodeStack.isEmpty()) {
383       Node node = (Node) nodeStack.pop();
384  
385       deleteAllEdges(node);
386       List nodeOutEdges = node.getOutEdges().getEdges();
387       for (Iterator i = nodeOutEdges.iterator(); i.hasNext(); ) {
388         PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
389         // delete this edge and its sym
390         de.setMarked(true);
391         PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de.getSym();
392         if (sym != null)
393           sym.setMarked(true);
394  
395         // save the line as a dangle
396         PolygonizeEdge e = (PolygonizeEdge) de.getEdge();
397         dangleLines.add(e.getLine());
398  
399         Node toNode = de.getToNode();
400         // add the toNode to the list to be processed, if it is now a dangle
401         if (getDegreeNonDeleted(toNode) == 1)
402           nodeStack.push(toNode);
403       }
404     }
405     return dangleLines;
406   }
407   
408   /**
409    * Traverses the polygonized edge rings in the graph
410    * and computes the depth parity (odd or even)
411    * relative to the exterior of the graph.
412    * If the client has requested that the output
413    * be polygonally valid, only odd polygons will be constructed. 
414    *
415    */
416   public void computeDepthParity()
417   {
418     while (true) {
419       PolygonizeDirectedEdge de = null; //findLowestDirEdge();
420       if (de == null)
421         return;
422       computeDepthParity(de);
423     }
424   }
425   
426   /**
427    * Traverses all connected edges, computing the depth parity
428    * of the associated polygons.
429    * 
430    * @param de
431    */
432   private void computeDepthParity(PolygonizeDirectedEdge de)
433   {
434     
435   }
436   
437 }
438