Doc Classic

Class EdgeEndStar

  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 import java.util.Map;
 22 import java.util.TreeMap;
 23  
 24 import org.locationtech.jts.algorithm.BoundaryNodeRule;
 25 import org.locationtech.jts.algorithm.locate.SimplePointInAreaLocator;
 26 import org.locationtech.jts.geom.Coordinate;
 27 import org.locationtech.jts.geom.Location;
 28 import org.locationtech.jts.geom.TopologyException;
 29 import org.locationtech.jts.util.Assert;
 30  
 31 /**
 32  * A EdgeEndStar is an ordered list of EdgeEnds around a node.
 33  * They are maintained in CCW order (starting with the positive x-axis) around the node
 34  * for efficient lookup and topology building.
 35  *
 36  * @version 1.7
 37  */
 38 abstract public class EdgeEndStar
 39 {
 40  
 41   /**
 42    * A map which maintains the edges in sorted order around the node
 43    */
 44   protected Map edgeMap = new TreeMap();
 45   /**
 46    * A list of all outgoing edges in the result, in CCW order
 47    */
 48   protected List edgeList;
 49   /**
 50    * The location of the point for this star in Geometry i Areas
 51    */
 52   private int[] ptInAreaLocation = { Location.NONE, Location.NONE };
 53  
 54   public EdgeEndStar()
 55   {
 56  
 57   }
 58  
 59   /**
 60    * Insert a EdgeEnd into this EdgeEndStar
 61    */
 62   abstract public void insert(EdgeEnd e);
 63  
 64   /**
 65    * Insert an EdgeEnd into the map, and clear the edgeList cache,
 66    * since the list of edges has now changed
 67    */
 68   protected void insertEdgeEnd(EdgeEnd e, Object obj)
 69   {
 70     edgeMap.put(e, obj);
 71     edgeList = null;  // edge list has changed - clear the cache
 72   }
 73  
 74   /**
 75    * @return the coordinate for the node this star is based at
 76    */
 77   public Coordinate getCoordinate()
 78   {
 79     Iterator it = iterator();
 80     if (! it.hasNext()) return null;
 81     EdgeEnd e = (EdgeEnd) it.next();
 82     return e.getCoordinate();
 83   }
 84   public int getDegree()
 85   {
 86     return edgeMap.size();
 87   }
 88  
 89   /**
 90    * Iterator access to the ordered list of edges is optimized by
 91    * copying the map collection to a list.  (This assumes that
 92    * once an iterator is requested, it is likely that insertion into
 93    * the map is complete).
 94    */
 95   public Iterator iterator()
 96   {
 97     return getEdges().iterator();
 98   }
 99   public List getEdges()
100   {
101     if (edgeList == null) {
102       edgeList = new ArrayList(edgeMap.values());
103     }
104     return edgeList;
105   }
106   public EdgeEnd getNextCW(EdgeEnd ee)
107   {
108     getEdges();
109     int i = edgeList.indexOf(ee);
110     int iNextCW = i - 1;
111     if (i == 0)
112       iNextCW = edgeList.size() - 1;
113     return (EdgeEnd) edgeList.get(iNextCW);
114   }
115  
116   public void computeLabelling(GeometryGraph[] geomGraph)
117   {
118     computeEdgeEndLabels(geomGraph[0].getBoundaryNodeRule());
119     // Propagate side labels  around the edges in the star
120     // for each parent Geometry
121 //Debug.print(this);
122     propagateSideLabels(0);
123 //Debug.print(this);
124 //Debug.printIfWatch(this);
125     propagateSideLabels(1);
126 //Debug.print(this);
127 //Debug.printIfWatch(this);
128  
129     /**
130      * If there are edges that still have null labels for a geometry
131      * this must be because there are no area edges for that geometry incident on this node.
132      * In this case, to label the edge for that geometry we must test whether the
133      * edge is in the interior of the geometry.
134      * To do this it suffices to determine whether the node for the edge is in the interior of an area.
135      * If so, the edge has location INTERIOR for the geometry.
136      * In all other cases (e.g. the node is on a line, on a point, or not on the geometry at all) the edge
137      * has the location EXTERIOR for the geometry.
138      * <p>
139      * Note that the edge cannot be on the BOUNDARY of the geometry, since then
140      * there would have been a parallel edge from the Geometry at this node also labelled BOUNDARY
141      * and this edge would have been labelled in the previous step.
142      * <p>
143      * This code causes a problem when dimensional collapses are present, since it may try and
144      * determine the location of a node where a dimensional collapse has occurred.
145      * The point should be considered to be on the EXTERIOR
146      * of the polygon, but locate() will return INTERIOR, since it is passed
147      * the original Geometry, not the collapsed version.
148      *
149      * If there are incident edges which are Line edges labelled BOUNDARY,
150      * then they must be edges resulting from dimensional collapses.
151      * In this case the other edges can be labelled EXTERIOR for this Geometry.
152      *
153      * MD 8/11/01 - NOT TRUE!  The collapsed edges may in fact be in the interior of the Geometry,
154      * which means the other edges should be labelled INTERIOR for this Geometry.
155      * Not sure how solve this...  Possibly labelling needs to be split into several phases:
156      * area label propagation, symLabel merging, then finally null label resolution.
157      */
158     boolean[] hasDimensionalCollapseEdge = { false, false };
159     for (Iterator it = iterator(); it.hasNext(); ) {
160       EdgeEnd e = (EdgeEnd) it.next();
161       Label label = e.getLabel();
162       for (int geomi = 0; geomi < 2; geomi++) {
163         if (label.isLine(geomi) && label.getLocation(geomi) == Location.BOUNDARY)
164           hasDimensionalCollapseEdge[geomi] = true;
165       }
166     }
167 //Debug.print(this);
168     for (Iterator it = iterator(); it.hasNext(); ) {
169       EdgeEnd e = (EdgeEnd) it.next();
170       Label label = e.getLabel();
171 //Debug.println(e);
172       for (int geomi = 0; geomi < 2; geomi++) {
173         if (label.isAnyNull(geomi)) {
174           int loc = Location.NONE;
175           if (hasDimensionalCollapseEdge[geomi]) {
176             loc = Location.EXTERIOR;
177           }
178           else {
179             Coordinate p = e.getCoordinate();
180             loc = getLocation(geomi, p, geomGraph);
181           }
182           label.setAllLocationsIfNull(geomi, loc);
183         }
184       }
185 //Debug.println(e);
186     }
187 //Debug.print(this);
188 //Debug.printIfWatch(this);
189   }
190  
191   private void computeEdgeEndLabels(BoundaryNodeRule boundaryNodeRule)
192   {
193     // Compute edge label for each EdgeEnd
194     for (Iterator it = iterator(); it.hasNext(); ) {
195       EdgeEnd ee = (EdgeEnd) it.next();
196       ee.computeLabel(boundaryNodeRule);
197     }
198   }
199   
200   private int getLocation(int geomIndex, Coordinate p, GeometryGraph[] geom)
201   {
202     // compute location only on demand
203     if (ptInAreaLocation[geomIndex] == Location.NONE) {
204       ptInAreaLocation[geomIndex] = SimplePointInAreaLocator.locate(p, geom[geomIndex].getGeometry());
205     }
206     return ptInAreaLocation[geomIndex];
207   }
208  
209   public boolean isAreaLabelsConsistent(GeometryGraph geomGraph)
210   {
211     computeEdgeEndLabels(geomGraph.getBoundaryNodeRule());
212     return checkAreaLabelsConsistent(0);
213   }
214  
215   private boolean checkAreaLabelsConsistent(int geomIndex)
216   {
217     // Since edges are stored in CCW order around the node,
218     // As we move around the ring we move from the right to the left side of the edge
219     List edges = getEdges();
220     // if no edges, trivially consistent
221     if (edges.size() <= 0)
222       return true;
223     // initialize startLoc to location of last L side (if any)
224     int lastEdgeIndex = edges.size() - 1;
225     Label startLabel = ((EdgeEnd) edges.get(lastEdgeIndex)).getLabel();
226     int startLoc = startLabel.getLocation(geomIndex, Position.LEFT);
227     Assert.isTrue(startLoc != Location.NONE, "Found unlabelled area edge");
228  
229     int currLoc = startLoc;
230     for (Iterator it = iterator(); it.hasNext(); ) {
231       EdgeEnd e = (EdgeEnd) it.next();
232       Label label = e.getLabel();
233       // we assume that we are only checking a area
234       Assert.isTrue(label.isArea(geomIndex), "Found non-area edge");
235       int leftLoc   = label.getLocation(geomIndex, Position.LEFT);
236       int rightLoc  = label.getLocation(geomIndex, Position.RIGHT);
237 //System.out.println(leftLoc + " " + rightLoc);
238 //Debug.print(this);
239       // check that edge is really a boundary between inside and outside!
240       if (leftLoc == rightLoc) {
241         return false;
242       }
243       // check side location conflict
244       //Assert.isTrue(rightLoc == currLoc, "side location conflict " + locStr);
245       if (rightLoc != currLoc) {
246 //Debug.print(this);
247         return false;
248       }
249       currLoc = leftLoc;
250     }
251     return true;
252   }
253   void propagateSideLabels(int geomIndex)
254   {
255     // Since edges are stored in CCW order around the node,
256     // As we move around the ring we move from the right to the left side of the edge
257     int startLoc = Location.NONE ;
258     
259     // initialize loc to location of last L side (if any)
260 //System.out.println("finding start location");
261     for (Iterator it = iterator(); it.hasNext(); ) {
262       EdgeEnd e = (EdgeEnd) it.next();
263       Label label = e.getLabel();
264       if (label.isArea(geomIndex) && label.getLocation(geomIndex, Position.LEFT) != Location.NONE)
265         startLoc = label.getLocation(geomIndex, Position.LEFT);
266     }
267     
268     // no labelled sides found, so no labels to propagate
269     if (startLoc == Location.NONE) return;
270  
271     int currLoc = startLoc;
272     for (Iterator it = iterator(); it.hasNext(); ) {
273       EdgeEnd e = (EdgeEnd) it.next();
274       Label label = e.getLabel();
275       // set null ON values to be in current location
276       if (label.getLocation(geomIndex, Position.ON) == Location.NONE)
277           label.setLocation(geomIndex, Position.ON, currLoc);
278       // set side labels (if any)
279       if (label.isArea(geomIndex)) {
280         int leftLoc   = label.getLocation(geomIndex, Position.LEFT);
281         int rightLoc  = label.getLocation(geomIndex, Position.RIGHT);
282         // if there is a right location, that is the next location to propagate
283         if (rightLoc != Location.NONE) {
284 //Debug.print(rightLoc != currLoc, this);
285           if (rightLoc != currLoc)
286             throw new TopologyException("side location conflict", e.getCoordinate());
287           if (leftLoc == Location.NONE) {
288             Assert.shouldNeverReachHere("found single null side (at " + e.getCoordinate() + ")");
289           }
290           currLoc = leftLoc;
291         }
292         else {
293           /** RHS is null - LHS must be null too.
294            *  This must be an edge from the other geometry, which has no location
295            *  labelling for this geometry.  This edge must lie wholly inside or outside
296            *  the other geometry (which is determined by the current location).
297            *  Assign both sides to be the current location.
298            */
299           Assert.isTrue(label.getLocation(geomIndex, Position.LEFT) == Location.NONE, "found single null side");
300           label.setLocation(geomIndex, Position.RIGHT, currLoc);
301           label.setLocation(geomIndex, Position.LEFT, currLoc);
302         }
303       }
304     }
305   }
306  
307   public int findIndex(EdgeEnd eSearch)
308   {
309     iterator();   // force edgelist to be computed
310     for (int i = 0; i < edgeList.size(); i++ ) {
311       EdgeEnd e = (EdgeEnd) edgeList.get(i);
312       if (e == eSearch) return i;
313     }
314     return -1;
315   }
316  
317   public void print(PrintStream out)
318   {
319     System.out.println("EdgeEndStar:   " + getCoordinate());
320     for (Iterator it = iterator(); it.hasNext(); ) {
321       EdgeEnd e = (EdgeEnd) it.next();
322       e.print(out);
323     }
324   }
325   
326   public String toString()
327   {
328     StringBuffer buf = new StringBuffer();
329     buf.append("EdgeEndStar:   " + getCoordinate());
330     buf.append("\n");
331     for (Iterator it = iterator(); it.hasNext(); ) {
332       EdgeEnd e = (EdgeEnd) it.next();
333       buf.append(e);
334       buf.append("\n");
335     }
336     return buf.toString();
337   }
338 }
339