Doc Classic

Class SegmentNodeList

  1 /*
  2  * Copyright (c) 2016 Vivid Solutions.
  3  *
  4  * All rights reserved. This program and the accompanying materials
  5  * are made available under the terms of the Eclipse Public License 2.0
  6  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
  7  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
  8  * and the Eclipse Distribution License is available at
  9  *
 10  * http://www.eclipse.org/org/documents/edl-v10.php.
 11  */
 12 package org.locationtech.jts.noding;
 13  
 14 import java.io.PrintStream;
 15 import java.util.ArrayList;
 16 import java.util.Collection;
 17 import java.util.Iterator;
 18 import java.util.List;
 19 import java.util.Map;
 20 import java.util.TreeMap;
 21  
 22 import org.locationtech.jts.geom.Coordinate;
 23 import org.locationtech.jts.geom.CoordinateList;
 24 import org.locationtech.jts.util.Assert;
 25  
 26  
 27 /**
 28  * A list of the {@link SegmentNode}s present along a noded {@link SegmentString}.
 29  *
 30  * @version 1.7
 31  */
 32 public class SegmentNodeList
 33 {
 34   private Map nodeMap = new TreeMap();
 35   private NodedSegmentString edge;  // the parent edge
 36  
 37   public SegmentNodeList(NodedSegmentString edge)
 38   {
 39     this.edge = edge;
 40   }
 41  
 42   public NodedSegmentString getEdge() { return edge; }
 43  
 44   /**
 45    * Adds an intersection into the list, if it isn't already there.
 46    * The input segmentIndex and dist are expected to be normalized.
 47    *
 48    * @return the SegmentIntersection found or added
 49    */
 50   public SegmentNode add(Coordinate intPt, int segmentIndex)
 51   {
 52     SegmentNode eiNew = new SegmentNode(edge, intPt, segmentIndex, edge.getSegmentOctant(segmentIndex));
 53     SegmentNode ei = (SegmentNode) nodeMap.get(eiNew);
 54     if (ei != null) {
 55       // debugging sanity check
 56       Assert.isTrue(ei.coord.equals2D(intPt), "Found equal nodes with different coordinates");
 57 //      if (! ei.coord.equals2D(intPt))
 58 //        Debug.println("Found equal nodes with different coordinates");
 59  
 60       return ei;
 61     }
 62     // node does not exist, so create it
 63     nodeMap.put(eiNew, eiNew);
 64     return eiNew;
 65   }
 66  
 67   /**
 68    * returns an iterator of SegmentNodes
 69    */
 70   public Iterator iterator() { return nodeMap.values().iterator(); }
 71  
 72   /**
 73    * Adds nodes for the first and last points of the edge
 74    */
 75   private void addEndpoints()
 76   {
 77     int maxSegIndex = edge.size() - 1;
 78     add(edge.getCoordinate(0), 0);
 79     add(edge.getCoordinate(maxSegIndex), maxSegIndex);
 80   }
 81  
 82   /**
 83    * Adds nodes for any collapsed edge pairs.
 84    * Collapsed edge pairs can be caused by inserted nodes, or they can be
 85    * pre-existing in the edge vertex list.
 86    * In order to provide the correct fully noded semantics,
 87    * the vertex at the base of a collapsed pair must also be added as a node.
 88    */
 89   private void addCollapsedNodes()
 90   {
 91     List collapsedVertexIndexes = new ArrayList();
 92  
 93     findCollapsesFromInsertedNodes(collapsedVertexIndexes);
 94     findCollapsesFromExistingVertices(collapsedVertexIndexes);
 95  
 96     // node the collapses
 97     for (Iterator it = collapsedVertexIndexes.iterator(); it.hasNext(); ) {
 98       int vertexIndex = ((Integer) it.next()).intValue();
 99       add(edge.getCoordinate(vertexIndex), vertexIndex);
100     }
101   }
102  
103   /**
104    * Adds nodes for any collapsed edge pairs
105    * which are pre-existing in the vertex list.
106    */
107   private void findCollapsesFromExistingVertices(List collapsedVertexIndexes)
108   {
109     for (int i = 0; i < edge.size() - 2; i++) {
110       Coordinate p0 = edge.getCoordinate(i);
111       Coordinate p1 = edge.getCoordinate(i + 1);
112       Coordinate p2 = edge.getCoordinate(i + 2);
113       if (p0.equals2D(p2)) {
114         // add base of collapse as node
115         collapsedVertexIndexes.add(i + 1);
116       }
117     }
118   }
119  
120   /**
121    * Adds nodes for any collapsed edge pairs caused by inserted nodes
122    * Collapsed edge pairs occur when the same coordinate is inserted as a node
123    * both before and after an existing edge vertex.
124    * To provide the correct fully noded semantics,
125    * the vertex must be added as a node as well.
126    */
127   private void findCollapsesFromInsertedNodes(List collapsedVertexIndexes)
128   {
129     int[] collapsedVertexIndex = new int[1];
130     Iterator it = iterator();
131     // there should always be at least two entries in the list, since the endpoints are nodes
132     SegmentNode eiPrev = (SegmentNode) it.next();
133     while (it.hasNext()) {
134       SegmentNode ei = (SegmentNode) it.next();
135       boolean isCollapsed = findCollapseIndex(eiPrev, ei, collapsedVertexIndex);
136       if (isCollapsed)
137         collapsedVertexIndexes.add(collapsedVertexIndex[0]);
138  
139       eiPrev = ei;
140     }
141   }
142  
143   private boolean findCollapseIndex(SegmentNode ei0, SegmentNode ei1, int[] collapsedVertexIndex)
144   {
145     // only looking for equal nodes
146     if (! ei0.coord.equals2D(ei1.coord)) return false;
147  
148     int numVerticesBetween = ei1.segmentIndex - ei0.segmentIndex;
149     if (! ei1.isInterior()) {
150       numVerticesBetween--;
151     }
152  
153     // if there is a single vertex between the two equal nodes, this is a collapse
154     if (numVerticesBetween == 1) {
155       collapsedVertexIndex[0] = ei0.segmentIndex + 1;
156       return true;
157     }
158     return false;
159   }
160  
161  
162   /**
163    * Creates new edges for all the edges that the intersections in this
164    * list split the parent edge into.
165    * Adds the edges to the provided argument list
166    * (this is so a single list can be used to accumulate all split edges
167    * for a set of {@link SegmentString}s).
168    */
169   public void addSplitEdges(Collection edgeList)
170   {
171     // ensure that the list has entries for the first and last point of the edge
172     addEndpoints();
173     addCollapsedNodes();
174  
175     Iterator it = iterator();
176     // there should always be at least two entries in the list, since the endpoints are nodes
177     SegmentNode eiPrev = (SegmentNode) it.next();
178     while (it.hasNext()) {
179       SegmentNode ei = (SegmentNode) it.next();
180       SegmentString newEdge = createSplitEdge(eiPrev, ei);
181       /*
182       if (newEdge.size() < 2)
183         throw new RuntimeException("created single point edge: " + newEdge.toString());
184       */
185       edgeList.add(newEdge);
186       eiPrev = ei;
187     }
188     //checkSplitEdgesCorrectness(testingSplitEdges);
189   }
190  
191   /**
192    * Checks the correctness of the set of split edges corresponding to this edge.
193    *
194    * @param splitEdges the split edges for this edge (in order)
195    */
196   private void checkSplitEdgesCorrectness(List splitEdges)
197   {
198     Coordinate[] edgePts = edge.getCoordinates();
199  
200     // check that first and last points of split edges are same as endpoints of edge
201     SegmentString split0 = (SegmentString) splitEdges.get(0);
202     Coordinate pt0 = split0.getCoordinate(0);
203     if (! pt0.equals2D(edgePts[0]))
204       throw new RuntimeException("bad split edge start point at " + pt0);
205  
206     SegmentString splitn = (SegmentString) splitEdges.get(splitEdges.size() - 1);
207     Coordinate[] splitnPts = splitn.getCoordinates();
208     Coordinate ptn = splitnPts[splitnPts.length - 1];
209     if (! ptn.equals2D(edgePts[edgePts.length - 1]))
210       throw new RuntimeException("bad split edge end point at " + ptn);
211   }
212  
213   /**
214    * Create a new "split edge" with the section of points between
215    * (and including) the two intersections.
216    * The label for the new edge is the same as the label for the parent edge.
217    */
218   private SegmentString createSplitEdge(SegmentNode ei0, SegmentNode ei1)
219   {
220     Coordinate[] pts = createSplitEdgePts(ei0, ei1);
221     return new NodedSegmentString(pts, edge.getData());
222   }
223   
224   /**
225    * Extracts the points for a split edge running between two nodes.
226    * The extracted points should contain no duplicate points.
227    * There should always be at least two points extracted
228    * (which will be the given nodes).
229    * 
230    * @param ei0 the start node of the split edge
231    * @param ei1 the end node of the split edge
232    * @return the points for the split edge
233    */
234   private Coordinate[] createSplitEdgePts(SegmentNode ei0, SegmentNode ei1) {
235 //Debug.println("\ncreateSplitEdge"); Debug.print(ei0); Debug.print(ei1);
236     int npts = ei1.segmentIndex - ei0.segmentIndex + 2;
237  
238     // if only two points in split edge they must be the node points
239     if (npts == 2) return new Coordinate[] { new Coordinate(ei0.coord), new Coordinate(ei1.coord) };
240     
241     Coordinate lastSegStartPt = edge.getCoordinate(ei1.segmentIndex);
242     /**
243      * If the last intersection point is not equal to the its segment start pt,
244      * add it to the points list as well.
245      * This check is needed because the distance metric is not totally reliable!
246      * 
247      * Also ensure that the created edge always has at least 2 points.
248      * 
249      * The check for point equality is 2D only - Z values are ignored
250      */
251     boolean useIntPt1 = ei1.isInterior() || ! ei1.coord.equals2D(lastSegStartPt);
252     if (! useIntPt1) {
253       npts--;
254     }
255  
256     Coordinate[] pts = new Coordinate[npts];
257     int ipt = 0;
258     pts[ipt++] = new Coordinate(ei0.coord);
259     for (int i = ei0.segmentIndex + 1; i <= ei1.segmentIndex; i++) {
260       pts[ipt++] = edge.getCoordinate(i);
261     }
262     if (useIntPt1) pts[ipt] = new Coordinate(ei1.coord);
263     return pts;
264   }
265  
266   /**
267    * Gets the list of coordinates for the fully noded segment string,
268    * including all original segment string vertices and vertices
269    * introduced by nodes in this list.
270    * Repeated coordinates are collapsed.
271    * 
272    * @return an array of Coordinates
273    * 
274    */
275   public Coordinate[] getSplitCoordinates()
276   {
277     CoordinateList coordList = new CoordinateList();
278     // ensure that the list has entries for the first and last point of the edge
279     addEndpoints();
280  
281     Iterator it = iterator();
282     // there should always be at least two entries in the list, since the endpoints are nodes
283     SegmentNode eiPrev = (SegmentNode) it.next();
284     while (it.hasNext()) {
285       SegmentNode ei = (SegmentNode) it.next();
286       addEdgeCoordinates(eiPrev, ei, coordList);
287       eiPrev = ei;
288     }
289     return coordList.toCoordinateArray();
290   }
291  
292   private void addEdgeCoordinates(SegmentNode ei0, SegmentNode ei1,
293       CoordinateList coordList) {
294     Coordinate[] pts = createSplitEdgePts(ei0, ei1);
295     coordList.add(pts, false);
296   }
297  
298   public void print(PrintStream out)
299   {
300     out.println("Intersections:");
301     for (Iterator it = iterator(); it.hasNext(); ) {
302       SegmentNode ei = (SegmentNode) it.next();
303       ei.print(out);
304     }
305   }
306 }
307  
308 // INCOMPLETE!
309 class NodeVertexIterator
310     implements Iterator
311 {
312   private SegmentNodeList nodeList;
313   private NodedSegmentString edge;
314   private Iterator nodeIt;
315   private SegmentNode currNode = null;
316   private SegmentNode nextNode = null;
317   private int currSegIndex = 0;
318  
319   NodeVertexIterator(SegmentNodeList nodeList)
320   {
321     this.nodeList = nodeList;
322     edge = nodeList.getEdge();
323     nodeIt = nodeList.iterator();
324     readNextNode();
325   }
326  
327   public boolean hasNext() {
328     if (nextNode == null) return false;
329     return true;
330   }
331  
332   public Object next()
333   {
334     if (currNode == null) {
335       currNode = nextNode;
336       currSegIndex = currNode.segmentIndex;
337       readNextNode();
338       return currNode;
339     }
340     // check for trying to read too far
341     if (nextNode == null) return null;
342  
343     if (nextNode.segmentIndex == currNode.segmentIndex) {
344       currNode = nextNode;
345       currSegIndex = currNode.segmentIndex;
346       readNextNode();
347       return currNode;
348     }
349  
350     if (nextNode.segmentIndex > currNode.segmentIndex) {
351  
352     }
353     return null;
354   }
355  
356   private void readNextNode()
357   {
358     if (nodeIt.hasNext())
359       nextNode = (SegmentNode) nodeIt.next();
360     else
361       nextNode = null;
362   }
363   /**
364    *  Not implemented.
365    *
366    *@throws  UnsupportedOperationException  This method is not implemented.
367    */
368   public void remove() {
369     throw new UnsupportedOperationException(getClass().getName());
370   }
371  
372 }
373  
374