Doc Classic

Class LineSequencer

  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.operation.linemerge;
 13  
 14 import java.util.ArrayList;
 15 import java.util.Collection;
 16 import java.util.Iterator;
 17 import java.util.LinkedList;
 18 import java.util.List;
 19 import java.util.ListIterator;
 20 import java.util.Set;
 21 import java.util.TreeSet;
 22  
 23 import org.locationtech.jts.geom.Coordinate;
 24 import org.locationtech.jts.geom.Geometry;
 25 import org.locationtech.jts.geom.GeometryComponentFilter;
 26 import org.locationtech.jts.geom.GeometryFactory;
 27 import org.locationtech.jts.geom.LineString;
 28 import org.locationtech.jts.geom.MultiLineString;
 29 import org.locationtech.jts.planargraph.DirectedEdge;
 30 import org.locationtech.jts.planargraph.GraphComponent;
 31 import org.locationtech.jts.planargraph.Node;
 32 import org.locationtech.jts.planargraph.Subgraph;
 33 import org.locationtech.jts.planargraph.algorithm.ConnectedSubgraphFinder;
 34 import org.locationtech.jts.util.Assert;
 35  
 36  
 37 /**
 38  * Builds a sequence from a set of LineStrings so that
 39  * they are ordered end to end.
 40  * A sequence is a complete non-repeating list of the linear
 41  * components of the input.  Each linestring is oriented
 42  * so that identical endpoints are adjacent in the list.
 43  * <p>
 44  * A typical use case is to convert a set of 
 45  * unoriented geometric links 
 46  * from a linear network
 47  * (e.g. such as block faces on a bus route)
 48  * into a continuous oriented path through the network. 
 49  * <p>
 50  * The input linestrings may form one or more connected sets.
 51  * The input linestrings should be correctly noded, or the results may
 52  * not be what is expected.
 53  * The computed output is a single {@link MultiLineString} containing the ordered
 54  * linestrings in the sequence.
 55  * <p>
 56  * The sequencing employs the classic <b>Eulerian path</b> graph algorithm.
 57  * Since Eulerian paths are not uniquely determined,
 58  * further rules are used to
 59  * make the computed sequence preserve as much as possible of the input
 60  * ordering.
 61  * Within a connected subset of lines, the ordering rules are:
 62  * <ul>
 63  * <li>If there is degree-1 node which is the start
 64  * node of an linestring, use that node as the start of the sequence
 65  * <li>If there is a degree-1 node which is the end
 66  * node of an linestring, use that node as the end of the sequence
 67  * <li>If the sequence has no degree-1 nodes, use any node as the start
 68  * </ul>
 69  *
 70  * Note that not all arrangements of lines can be sequenced.
 71  * For a connected set of edges in a graph,
 72  * <i>Euler's Theorem</i> states that there is a sequence containing each edge once
 73  * <b>if and only if</b> there are no more than 2 nodes of odd degree.
 74  * If it is not possible to find a sequence, the {@link #isSequenceable()} method
 75  * will return <code>false</code>.
 76  *
 77  * @version 1.7
 78  */
 79 public class LineSequencer
 80 {
 81     public static Geometry sequence(Geometry geom)
 82     {
 83         LineSequencer sequencer = new LineSequencer();
 84         sequencer.add(geom);
 85         return sequencer.getSequencedLineStrings();
 86     }
 87     
 88   /**
 89    * Tests whether a {@link Geometry} is sequenced correctly.
 90    * {@link LineString}s are trivially sequenced.
 91    * {@link MultiLineString}s are checked for correct sequencing.
 92    * Otherwise, <code>isSequenced</code> is defined
 93    * to be <code>true</code> for geometries that are not lineal.
 94    *
 95    * @param geom the geometry to test
 96    * @return <code>true</code> if the geometry is sequenced or is not lineal
 97    */
 98   public static boolean isSequenced(Geometry geom)
 99   {
100     if (! (geom instanceof MultiLineString)) {
101       return true;
102     }
103  
104     MultiLineString mls = (MultiLineString) geom;
105     // the nodes in all subgraphs which have been completely scanned
106     Set prevSubgraphNodes = new TreeSet();
107  
108     Coordinate lastNode = null;
109     List currNodes = new ArrayList();
110     for (int i = 0; i < mls.getNumGeometries(); i++) {
111       LineString line = (LineString) mls.getGeometryN(i);
112       Coordinate startNode = line.getCoordinateN(0);
113       Coordinate endNode = line.getCoordinateN(line.getNumPoints() - 1);
114  
115       /**
116        * If this linestring is connected to a previous subgraph, geom is not sequenced
117        */
118       if (prevSubgraphNodes.contains(startNode)) return false;
119       if (prevSubgraphNodes.contains(endNode)) return false;
120  
121       if (lastNode != null) {
122         if (! startNode.equals(lastNode)) {
123           // start new connected sequence
124           prevSubgraphNodes.addAll(currNodes);
125           currNodes.clear();
126         }
127       }
128       currNodes.add(startNode);
129       currNodes.add(endNode);
130       lastNode = endNode;
131     }
132     return true;
133   }
134  
135   private LineMergeGraph graph = new LineMergeGraph();
136   // initialize with default, in case no lines are input
137   private GeometryFactory factory = new GeometryFactory();
138   private int lineCount = 0;
139  
140   private boolean isRun = false;
141   private Geometry sequencedGeometry = null;
142   private boolean isSequenceable = false;
143  
144   /**
145    * Adds a {@link Collection} of {@link Geometry}s to be sequenced.
146    * May be called multiple times.
147    * Any dimension of Geometry may be added; the constituent linework will be
148    * extracted.
149    *
150    * @param geometries a Collection of geometries to add
151    */
152   public void add(Collection geometries) {
153     for (Iterator i = geometries.iterator(); i.hasNext(); ) {
154       Geometry geometry = (Geometry) i.next();
155       add(geometry);
156     }
157   }
158   /**
159    * Adds a {@link Geometry} to be sequenced.
160    * May be called multiple times.
161    * Any dimension of Geometry may be added; the constituent linework will be
162    * extracted.
163    *
164    * @param geometry the geometry to add
165    */
166   public void add(Geometry geometry) {
167     geometry.apply(new GeometryComponentFilter() {
168       public void filter(Geometry component) {
169         if (component instanceof LineString) {
170           addLine((LineString)component);
171         }
172       }
173     });
174   }
175  
176   private void addLine(LineString lineString) {
177     if (factory == null) {
178       this.factory = lineString.getFactory();
179     }
180     graph.addEdge(lineString);
181     lineCount++;
182   }
183  
184   /**
185    * Tests whether the arrangement of linestrings has a valid
186    * sequence.
187    *
188    * @return <code>true</code> if a valid sequence exists.
189    */
190   public boolean isSequenceable()
191   {
192     computeSequence();
193     return isSequenceable;
194   }
195   /**
196    * Returns the {@link LineString} or {@link MultiLineString}
197    * built by the sequencing process, if one exists.
198    *
199    * @return the sequenced linestrings,
200    * or <code>null</code> if a valid sequence does not exist
201    */
202   public Geometry getSequencedLineStrings() {
203     computeSequence();
204     return sequencedGeometry;
205   }
206  
207   private void computeSequence() {
208     if (isRun) { return; }
209     isRun = true;
210  
211     List sequences = findSequences();
212     if (sequences == null)
213       return;
214  
215     sequencedGeometry = buildSequencedGeometry(sequences);
216     isSequenceable = true;
217  
218     int finalLineCount = sequencedGeometry.getNumGeometries();
219     Assert.isTrue(lineCount == finalLineCount, "Lines were missing from result");
220     Assert.isTrue(sequencedGeometry instanceof LineString
221                   || sequencedGeometry instanceof MultiLineString,
222                   "Result is not lineal");
223   }
224  
225   private List findSequences()
226   {
227     List sequences = new ArrayList();
228     ConnectedSubgraphFinder csFinder = new ConnectedSubgraphFinder(graph);
229     List subgraphs = csFinder.getConnectedSubgraphs();
230     for (Iterator i = subgraphs.iterator(); i.hasNext(); ) {
231       Subgraph subgraph = (Subgraph) i.next();
232       if (hasSequence(subgraph)) {
233         List seq = findSequence(subgraph);
234         sequences.add(seq);
235       }
236       else {
237         // if any subgraph cannot be sequenced, abort
238         return null;
239       }
240     }
241     return sequences;
242   }
243  
244   /**
245    * Tests whether a complete unique path exists in a graph
246    * using Euler's Theorem.
247    *
248    * @param graph the subgraph containing the edges
249    * @return <code>true</code> if a sequence exists
250    */
251   private boolean hasSequence(Subgraph graph)
252   {
253     int oddDegreeCount = 0;
254     for (Iterator i = graph.nodeIterator(); i.hasNext(); ) {
255       Node node = (Node) i.next();
256       if (node.getDegree() % 2 == 1)
257         oddDegreeCount++;
258     }
259     return oddDegreeCount <= 2;
260   }
261  
262   private List findSequence(Subgraph graph)
263   {
264     GraphComponent.setVisited(graph.edgeIterator(), false);
265  
266     Node startNode = findLowestDegreeNode(graph);
267     DirectedEdge startDE = (DirectedEdge) startNode.getOutEdges().iterator().next();
268     DirectedEdge startDESym = startDE.getSym();
269  
270     List seq = new LinkedList();
271     ListIterator lit = seq.listIterator();
272     addReverseSubpath(startDESym, lit, false);
273     while (lit.hasPrevious()) {
274       DirectedEdge prev = (DirectedEdge) lit.previous();
275       DirectedEdge unvisitedOutDE = findUnvisitedBestOrientedDE(prev.getFromNode());
276       if (unvisitedOutDE != null)
277         addReverseSubpath(unvisitedOutDE.getSym(), lit, true);
278     }
279  
280     /**
281      * At this point, we have a valid sequence of graph DirectedEdges, but it
282      * is not necessarily appropriately oriented relative to the underlying
283      * geometry.
284      */
285     List orientedSeq = orient(seq);
286     return orientedSeq;
287   }
288  
289   /**
290    * Finds an {@link DirectedEdge} for an unvisited edge (if any),
291    * choosing the dirEdge which preserves orientation, if possible.
292    *
293    * @param node the node to examine
294    * @return the dirEdge found, or <code>null</code> if none were unvisited
295    */
296   private static DirectedEdge findUnvisitedBestOrientedDE(Node node)
297   {
298     DirectedEdge wellOrientedDE = null;
299     DirectedEdge unvisitedDE = null;
300     for (Iterator i = node.getOutEdges().iterator(); i.hasNext(); ) {
301        DirectedEdge de = (DirectedEdge) i.next();
302        if (! de.getEdge().isVisited()) {
303          unvisitedDE = de;
304          if (de.getEdgeDirection())
305            wellOrientedDE = de;
306        }
307     }
308     if (wellOrientedDE != null)
309       return wellOrientedDE;
310     return unvisitedDE;
311   }
312  
313   private void addReverseSubpath(DirectedEdge de, ListIterator lit, boolean expectedClosed)
314   {
315     // trace an unvisited path *backwards* from this de
316     Node endNode = de.getToNode();
317  
318     Node fromNode = null;
319     while (true) {
320       lit.add(de.getSym());
321       de.getEdge().setVisited(true);
322       fromNode = de.getFromNode();
323       DirectedEdge unvisitedOutDE = findUnvisitedBestOrientedDE(fromNode);
324       // this must terminate, since we are continually marking edges as visited
325       if (unvisitedOutDE == null)
326         break;
327       de = unvisitedOutDE.getSym();
328     }
329     if (expectedClosed) {
330       // the path should end at the toNode of this de, otherwise we have an error
331       Assert.isTrue(fromNode == endNode, "path not contiguous");
332     }
333   }
334  
335   private static Node findLowestDegreeNode(Subgraph graph)
336   {
337     int minDegree = Integer.MAX_VALUE;
338     Node minDegreeNode = null;
339     for (Iterator i = graph.nodeIterator(); i.hasNext(); ) {
340       Node node = (Node) i.next();
341       if (minDegreeNode == null || node.getDegree() < minDegree) {
342         minDegree = node.getDegree();
343         minDegreeNode = node;
344       }
345     }
346     return minDegreeNode;
347   }
348  
349   /**
350    * Computes a version of the sequence which is optimally
351    * oriented relative to the underlying geometry.
352    * <p>
353    * Heuristics used are:
354    * <ul>
355    * <li>If the path has a degree-1 node which is the start
356    * node of an linestring, use that node as the start of the sequence
357    * <li>If the path has a degree-1 node which is the end
358    * node of an linestring, use that node as the end of the sequence
359    * <li>If the sequence has no degree-1 nodes, use any node as the start
360    * (NOTE: in this case could orient the sequence according to the majority of the
361    * linestring orientations)
362    * </ul>
363    *
364    * @param seq a List of DirectedEdges
365    * @return a List of DirectedEdges oriented appropriately
366    */
367   private List orient(List seq)
368   {
369     DirectedEdge startEdge = (DirectedEdge) seq.get(0);
370     DirectedEdge endEdge = (DirectedEdge) seq.get(seq.size() - 1);
371     Node startNode = startEdge.getFromNode();
372     Node endNode = endEdge.getToNode();
373  
374     boolean flipSeq = false;
375     boolean hasDegree1Node = startNode.getDegree() == 1
376                            || endNode.getDegree() == 1;
377  
378     if (hasDegree1Node) {
379       boolean hasObviousStartNode = false;
380  
381       // test end edge before start edge, to make result stable
382       // (ie. if both are good starts, pick the actual start
383       if (endEdge.getToNode().getDegree() == 1 && endEdge.getEdgeDirection() == false) {
384         hasObviousStartNode = true;
385         flipSeq = true;
386       }
387       if (startEdge.getFromNode().getDegree() == 1 && startEdge.getEdgeDirection() == true) {
388         hasObviousStartNode = true;
389         flipSeq = false;
390       }
391  
392       // since there is no obvious start node, use any node of degree 1
393       if (! hasObviousStartNode) {
394         // check if the start node should actually be the end node
395         if (startEdge.getFromNode().getDegree() == 1)
396           flipSeq = true;
397         // if the end node is of degree 1, it is properly the end node
398       }
399  
400     }
401  
402  
403     // if there is no degree 1 node, just use the sequence as is
404     // (Could insert heuristic of taking direction of majority of lines as overall direction)
405  
406     if (flipSeq)
407       return reverse(seq);
408     return seq;
409   }
410  
411   /**
412    * Reverse the sequence.
413    * This requires reversing the order of the dirEdges, and flipping
414    * each dirEdge as well
415    *
416    * @param seq a List of DirectedEdges, in sequential order
417    * @return the reversed sequence
418    */
419   private List reverse(List seq)
420   {
421     LinkedList newSeq = new LinkedList();
422     for (Iterator i = seq.iterator(); i.hasNext(); ) {
423       DirectedEdge de = (DirectedEdge) i.next();
424       newSeq.addFirst(de.getSym());
425     }
426     return newSeq;
427   }
428  
429   /**
430    * Builds a geometry ({@link LineString} or {@link MultiLineString} )
431    * representing the sequence.
432    *
433    * @param sequences a List of Lists of DirectedEdges with
434    *   LineMergeEdges as their parent edges.
435    * @return the sequenced geometry, or <code>null</code> if no sequence exists
436    */
437   private Geometry buildSequencedGeometry(List sequences)
438   {
439     List lines = new ArrayList();
440  
441     for (Iterator i1 = sequences.iterator(); i1.hasNext(); ) {
442       List seq = (List) i1.next();
443       for (Iterator i2 = seq.iterator(); i2.hasNext(); ) {
444         DirectedEdge de = (DirectedEdge) i2.next();
445         LineMergeEdge e = (LineMergeEdge) de.getEdge();
446         LineString line = e.getLine();
447  
448         LineString lineToAdd = line;
449         if (! de.getEdgeDirection() && ! line.isClosed())
450           lineToAdd = reverse(line);
451  
452         lines.add(lineToAdd);
453       }
454     }
455     if (lines.size() == 0)
456       return factory.createMultiLineString(new LineString[0]);
457     return factory.buildGeometry(lines);
458   }
459  
460   private static LineString reverse(LineString line)
461   {
462     Coordinate[] pts = line.getCoordinates();
463     Coordinate[] revPts = new Coordinate[pts.length];
464     int len = pts.length;
465     for (int i = 0; i < len; i++) {
466       revPts[len - 1 - i] = new Coordinate(pts[i]);
467     }
468     return line.getFactory().createLineString(revPts);
469   }
470  
471 }
472