Doc Classic

Class DirectedEdgeStar

  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.io.PrintStream;
 18 import java.util.ArrayList;
 19 import java.util.Iterator;
 20 import java.util.List;
 21  
 22 import org.locationtech.jts.geom.Location;
 23 import org.locationtech.jts.geom.TopologyException;
 24 import org.locationtech.jts.util.Assert;
 25  
 26 /**
 27  * A DirectedEdgeStar is an ordered list of <b>outgoing</b> DirectedEdges around a node.
 28  * It supports labelling the edges as well as linking the edges to form both
 29  * MaximalEdgeRings and MinimalEdgeRings.
 30  *
 31  * @version 1.7
 32  */
 33 public class DirectedEdgeStar
 34   extends EdgeEndStar
 35 {
 36  
 37   /**
 38    * A list of all outgoing edges in the result, in CCW order
 39    */
 40   private List resultAreaEdgeList;
 41   private Label label;
 42  
 43   public DirectedEdgeStar() {
 44   }
 45   /**
 46    * Insert a directed edge in the list
 47    */
 48   public void insert(EdgeEnd ee)
 49   {
 50     DirectedEdge de = (DirectedEdge) ee;
 51     insertEdgeEnd(de, de);
 52   }
 53  
 54   public Label getLabel() { return label; }
 55  
 56   public int getOutgoingDegree()
 57   {
 58     int degree = 0;
 59     for (Iterator it = iterator(); it.hasNext(); ) {
 60       DirectedEdge de = (DirectedEdge) it.next();
 61       if (de.isInResult()) degree++;
 62     }
 63     return degree;
 64   }
 65   public int getOutgoingDegree(EdgeRing er)
 66   {
 67     int degree = 0;
 68     for (Iterator it = iterator(); it.hasNext(); ) {
 69       DirectedEdge de = (DirectedEdge) it.next();
 70       if (de.getEdgeRing() == er) degree++;
 71     }
 72     return degree;
 73   }
 74  
 75   public DirectedEdge getRightmostEdge()
 76   {
 77     List edges = getEdges();
 78     int size = edges.size();
 79     if (size < 1) return null;
 80     DirectedEdge de0 = (DirectedEdge) edges.get(0);
 81     if (size == 1) return de0;
 82     DirectedEdge deLast = (DirectedEdge) edges.get(size - 1);
 83  
 84     int quad0 = de0.getQuadrant();
 85     int quad1 = deLast.getQuadrant();
 86     if (Quadrant.isNorthern(quad0) && Quadrant.isNorthern(quad1))
 87       return de0;
 88     else if (! Quadrant.isNorthern(quad0) && ! Quadrant.isNorthern(quad1))
 89       return deLast;
 90     else {
 91       // edges are in different hemispheres - make sure we return one that is non-horizontal
 92       //Assert.isTrue(de0.getDy() != 0, "should never return horizontal edge!");
 93       DirectedEdge nonHorizontalEdge = null;
 94       if (de0.getDy() != 0)
 95         return de0;
 96       else if (deLast.getDy() != 0)
 97         return deLast;
 98     }
 99     Assert.shouldNeverReachHere("found two horizontal edges incident on node");
100     return null;
101  
102   }
103   /**
104    * Compute the labelling for all dirEdges in this star, as well
105    * as the overall labelling
106    */
107   public void computeLabelling(GeometryGraph[] geom)
108   {
109 //Debug.print(this);
110     super.computeLabelling(geom);
111  
112     // determine the overall labelling for this DirectedEdgeStar
113     // (i.e. for the node it is based at)
114     label = new Label(Location.NONE);
115     for (Iterator it = iterator(); it.hasNext(); ) {
116       EdgeEnd ee = (EdgeEnd) it.next();
117       Edge e = ee.getEdge();
118       Label eLabel = e.getLabel();
119       for (int i = 0; i < 2; i++) {
120         int eLoc = eLabel.getLocation(i);
121         if (eLoc == Location.INTERIOR || eLoc == Location.BOUNDARY)
122           label.setLocation(i, Location.INTERIOR);
123       }
124     }
125 //Debug.print(this);
126   }
127  
128   /**
129    * For each dirEdge in the star,
130    * merge the label from the sym dirEdge into the label
131    */
132   public void mergeSymLabels()
133   {
134     for (Iterator it = iterator(); it.hasNext(); ) {
135       DirectedEdge de = (DirectedEdge) it.next();
136       Label label = de.getLabel();
137       label.merge(de.getSym().getLabel());
138     }
139   }
140  
141   /**
142    * Update incomplete dirEdge labels from the labelling for the node
143    */
144   public void updateLabelling(Label nodeLabel)
145   {
146     for (Iterator it = iterator(); it.hasNext(); ) {
147       DirectedEdge de = (DirectedEdge) it.next();
148       Label label = de.getLabel();
149       label.setAllLocationsIfNull(0, nodeLabel.getLocation(0));
150       label.setAllLocationsIfNull(1, nodeLabel.getLocation(1));
151     }
152   }
153  
154   private List getResultAreaEdges()
155   {
156 //print(System.out);
157     if (resultAreaEdgeList != null) return resultAreaEdgeList;
158     resultAreaEdgeList = new ArrayList();
159     for (Iterator it = iterator(); it.hasNext(); ) {
160       DirectedEdge de = (DirectedEdge) it.next();
161       if (de.isInResult() || de.getSym().isInResult() )
162         resultAreaEdgeList.add(de);
163     }
164     return resultAreaEdgeList;
165   }
166  
167   private final int SCANNING_FOR_INCOMING = 1;
168   private final int LINKING_TO_OUTGOING = 2;
169   /**
170    * Traverse the star of DirectedEdges, linking the included edges together.
171    * To link two dirEdges, the <code>next</code> pointer for an incoming dirEdge
172    * is set to the next outgoing edge.
173    * <p>
174    * DirEdges are only linked if:
175    * <ul>
176    * <li>they belong to an area (i.e. they have sides)
177    * <li>they are marked as being in the result
178    * </ul>
179    * <p>
180    * Edges are linked in CCW order (the order they are stored).
181    * This means that rings have their face on the Right
182    * (in other words,
183    * the topological location of the face is given by the RHS label of the DirectedEdge)
184    * <p>
185    * PRECONDITION: No pair of dirEdges are both marked as being in the result
186    */
187   public void linkResultDirectedEdges()
188   {
189     // make sure edges are copied to resultAreaEdges list
190     getResultAreaEdges();
191     // find first area edge (if any) to start linking at
192     DirectedEdge firstOut = null;
193     DirectedEdge incoming = null;
194     int state = SCANNING_FOR_INCOMING;
195     // link edges in CCW order
196     for (int i = 0; i < resultAreaEdgeList.size(); i++) {
197       DirectedEdge nextOut = (DirectedEdge) resultAreaEdgeList.get(i);
198       DirectedEdge nextIn = nextOut.getSym();
199  
200       // skip de's that we're not interested in
201       if (! nextOut.getLabel().isArea()) continue;
202  
203       // record first outgoing edge, in order to link the last incoming edge
204       if (firstOut == null && nextOut.isInResult()) firstOut = nextOut;
205       // assert: sym.isInResult() == false, since pairs of dirEdges should have been removed already
206  
207       switch (state) {
208       case SCANNING_FOR_INCOMING:
209         if (! nextIn.isInResult()) continue;
210         incoming = nextIn;
211         state = LINKING_TO_OUTGOING;
212         break;
213       case LINKING_TO_OUTGOING:
214         if (! nextOut.isInResult()) continue;
215         incoming.setNext(nextOut);
216         state = SCANNING_FOR_INCOMING;
217         break;
218       }
219     }
220 //Debug.print(this);
221     if (state == LINKING_TO_OUTGOING) {
222 //Debug.print(firstOut == null, this);
223       if (firstOut == null)
224         throw new TopologyException("no outgoing dirEdge found", getCoordinate());
225       //Assert.isTrue(firstOut != null, "no outgoing dirEdge found (at " + getCoordinate() );
226       Assert.isTrue(firstOut.isInResult(), "unable to link last incoming dirEdge");
227       incoming.setNext(firstOut);
228     }
229   }
230   public void linkMinimalDirectedEdges(EdgeRing er)
231   {
232     // find first area edge (if any) to start linking at
233     DirectedEdge firstOut = null;
234     DirectedEdge incoming = null;
235     int state = SCANNING_FOR_INCOMING;
236     // link edges in CW order
237     for (int i = resultAreaEdgeList.size() - 1; i >= 0; i--) {
238       DirectedEdge nextOut = (DirectedEdge) resultAreaEdgeList.get(i);
239       DirectedEdge nextIn = nextOut.getSym();
240  
241       // record first outgoing edge, in order to link the last incoming edge
242       if (firstOut == null && nextOut.getEdgeRing() == er) firstOut = nextOut;
243  
244       switch (state) {
245       case SCANNING_FOR_INCOMING:
246         if (nextIn.getEdgeRing() != er) continue;
247         incoming = nextIn;
248         state = LINKING_TO_OUTGOING;
249         break;
250       case LINKING_TO_OUTGOING:
251         if (nextOut.getEdgeRing() != er) continue;
252         incoming.setNextMin(nextOut);
253         state = SCANNING_FOR_INCOMING;
254         break;
255       }
256     }
257 //print(System.out);
258     if (state == LINKING_TO_OUTGOING) {
259       Assert.isTrue(firstOut != null, "found null for first outgoing dirEdge");
260       Assert.isTrue(firstOut.getEdgeRing() == er, "unable to link last incoming dirEdge");
261       incoming.setNextMin(firstOut);
262     }
263   }
264   public void linkAllDirectedEdges()
265   {
266     getEdges();
267     // find first area edge (if any) to start linking at
268     DirectedEdge prevOut = null;
269     DirectedEdge firstIn = null;
270     // link edges in CW order
271     for (int i = edgeList.size() - 1; i >= 0; i--) {
272       DirectedEdge nextOut = (DirectedEdge) edgeList.get(i);
273       DirectedEdge nextIn = nextOut.getSym();
274       if (firstIn == null) firstIn = nextIn;
275       if (prevOut != null) nextIn.setNext(prevOut);
276       // record outgoing edge, in order to link the last incoming edge
277       prevOut = nextOut;
278     }
279     firstIn.setNext(prevOut);
280 //Debug.print(this);
281   }
282  
283   /**
284    * Traverse the star of edges, maintaining the current location in the result
285    * area at this node (if any).
286    * If any L edges are found in the interior of the result, mark them as covered.
287    */
288   public void findCoveredLineEdges()
289   {
290 //Debug.print("findCoveredLineEdges");
291 //Debug.print(this);
292     // Since edges are stored in CCW order around the node,
293     // as we move around the ring we move from the right to the left side of the edge
294  
295     /**
296      * Find first DirectedEdge of result area (if any).
297      * The interior of the result is on the RHS of the edge,
298      * so the start location will be:
299      * - INTERIOR if the edge is outgoing
300      * - EXTERIOR if the edge is incoming
301      */
302     int startLoc = Location.NONE ;
303     for (Iterator it = iterator(); it.hasNext(); ) {
304       DirectedEdge nextOut  = (DirectedEdge) it.next();
305       DirectedEdge nextIn   = nextOut.getSym();
306       if (! nextOut.isLineEdge()) {
307         if (nextOut.isInResult()) {
308           startLoc = Location.INTERIOR;
309           break;
310         }
311         if (nextIn.isInResult()) {
312           startLoc = Location.EXTERIOR;
313           break;
314         }
315       }
316     }
317     // no A edges found, so can't determine if L edges are covered or not
318     if (startLoc == Location.NONE) return;
319  
320     /**
321      * move around ring, keeping track of the current location
322      * (Interior or Exterior) for the result area.
323      * If L edges are found, mark them as covered if they are in the interior
324      */
325     int currLoc = startLoc;
326     for (Iterator it = iterator(); it.hasNext(); ) {
327       DirectedEdge nextOut  = (DirectedEdge) it.next();
328       DirectedEdge nextIn   = nextOut.getSym();
329       if (nextOut.isLineEdge()) {
330         nextOut.getEdge().setCovered(currLoc == Location.INTERIOR);
331 //Debug.println(nextOut);
332       }
333       else {  // edge is an Area edge
334         if (nextOut.isInResult())
335           currLoc = Location.EXTERIOR;
336         if (nextIn.isInResult())
337           currLoc = Location.INTERIOR;
338       }
339     }
340   }
341  
342   public void computeDepths(DirectedEdge de)
343   {
344     int edgeIndex = findIndex(de);
345     int startDepth = de.getDepth(Position.LEFT);
346     int targetLastDepth = de.getDepth(Position.RIGHT);
347     // compute the depths from this edge up to the end of the edge array
348     int nextDepth = computeDepths(edgeIndex + 1, edgeList.size(), startDepth);
349     // compute the depths for the initial part of the array
350     int lastDepth = computeDepths(0, edgeIndex, nextDepth);
351 //Debug.print(lastDepth != targetLastDepth, this);
352 //Debug.print(lastDepth != targetLastDepth, "mismatch: " + lastDepth + " / " + targetLastDepth);
353     if (lastDepth != targetLastDepth)
354       throw new TopologyException("depth mismatch at " + de.getCoordinate());
355     //Assert.isTrue(lastDepth == targetLastDepth, "depth mismatch at " + de.getCoordinate());
356   }
357  
358   /**
359    * Compute the DirectedEdge depths for a subsequence of the edge array.
360    *
361    * @return the last depth assigned (from the R side of the last edge visited)
362    */
363   private int computeDepths(int startIndex, int endIndex, int startDepth)
364   {
365     int currDepth = startDepth;
366     for (int i = startIndex; i < endIndex ; i++) {
367       DirectedEdge nextDe = (DirectedEdge) edgeList.get(i);
368       nextDe.setEdgeDepths(Position.RIGHT, currDepth);
369       currDepth = nextDe.getDepth(Position.LEFT);
370     }
371     return currDepth;
372   }
373  
374   public void print(PrintStream out)
375   {
376     System.out.println("DirectedEdgeStar: " + getCoordinate());
377     for (Iterator it = iterator(); it.hasNext(); ) {
378       DirectedEdge de = (DirectedEdge) it.next();
379       out.print("out ");
380       de.print(out);
381       out.println();
382       out.print("in ");
383       de.getSym().print(out);
384       out.println();
385     }
386   }
387 }
388