Package org.locationtech.jts.operation.linemerge

Class LineSequencer

java.lang.Object

org.locationtech.jts.operation.linemerge.LineSequencer

public class LineSequencer
extends java.lang.Object

Builds a sequence from a set of LineStrings so that they are ordered end to end. A sequence is a complete non-repeating list of the linear components of the input. Each linestring is oriented so that identical endpoints are adjacent in the list.

A typical use case is to convert a set of unoriented geometric links from a linear network (e.g. such as block faces on a bus route) into a continuous oriented path through the network.

The input linestrings may form one or more connected sets. The input linestrings should be correctly noded, or the results may not be what is expected. The computed output is a single MultiLineString containing the ordered linestrings in the sequence.

The sequencing employs the classic Eulerian path graph algorithm. Since Eulerian paths are not uniquely determined, further rules are used to make the computed sequence preserve as much as possible of the input ordering. Within a connected subset of lines, the ordering rules are:

• If there is degree-1 node which is the start node of an linestring, use that node as the start of the sequence
• If there is a degree-1 node which is the end node of an linestring, use that node as the end of the sequence
• If the sequence has no degree-1 nodes, use any node as the start

Note that not all arrangements of lines can be sequenced. For a connected set of edges in a graph, Euler's Theorem states that there is a sequence containing each edge once if and only if there are no more than 2 nodes of odd degree. If it is not possible to find a sequence, the isSequenceable() method will return false.

Version:

1.7

Field Summary

Fields

Modifier and Type	Field	Description
private GeometryFactory	factory
private LineMergeGraph	graph
private boolean	isRun
private boolean	isSequenceable
private int	lineCount
private Geometry	sequencedGeometry

Constructor Summary

Constructors

Constructor	Description
LineSequencer()

Method Summary

Modifier and Type	Method	Description
void	add(java.util.Collection geometries)	Adds a Collection of Geometrys to be sequenced.
void	add(Geometry geometry)	Adds a Geometry to be sequenced.
private void	addLine(LineString lineString)
private void	addReverseSubpath(DirectedEdge de, java.util.ListIterator lit, boolean expectedClosed)
private Geometry	buildSequencedGeometry(java.util.List sequences)	Builds a geometry (LineString or MultiLineString ) representing the sequence.
private void	computeSequence()
private static Node	findLowestDegreeNode(Subgraph graph)
private java.util.List	findSequence(Subgraph graph)
private java.util.List	findSequences()
private static DirectedEdge	findUnvisitedBestOrientedDE(Node node)	Finds an DirectedEdge for an unvisited edge (if any), choosing the dirEdge which preserves orientation, if possible.
Geometry	getSequencedLineStrings()	Returns the LineString or MultiLineString built by the sequencing process, if one exists.
private boolean	hasSequence(Subgraph graph)	Tests whether a complete unique path exists in a graph using Euler's Theorem.
boolean	isSequenceable()	Tests whether the arrangement of linestrings has a valid sequence.
static boolean	isSequenced(Geometry geom)	Tests whether a Geometry is sequenced correctly.
private java.util.List	orient(java.util.List seq)	Computes a version of the sequence which is optimally oriented relative to the underlying geometry.
private java.util.List	reverse(java.util.List seq)	Reverse the sequence.
private static LineString	reverse(LineString line)
static Geometry	sequence(Geometry geom)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

graph

private LineMergeGraph graph

factory

private GeometryFactory factory

lineCount

private int lineCount

isRun

private boolean isRun

sequencedGeometry

private Geometry sequencedGeometry

isSequenceable

private boolean isSequenceable

Constructor Detail

LineSequencer

public LineSequencer()

Method Detail

sequence

public static Geometry sequence(Geometry geom)

isSequenced

public static boolean isSequenced(Geometry geom)

Tests whether a Geometry is sequenced correctly. LineStrings are trivially sequenced. MultiLineStrings are checked for correct sequencing. Otherwise, isSequenced is defined to be true for geometries that are not lineal.

Parameters:

geom - the geometry to test

Returns:

true if the geometry is sequenced or is not lineal

add

public void add(java.util.Collection geometries)

Adds a Collection of Geometrys to be sequenced. May be called multiple times. Any dimension of Geometry may be added; the constituent linework will be extracted.

Parameters:

geometries - a Collection of geometries to add

add

public void add(Geometry geometry)

Adds a Geometry to be sequenced. May be called multiple times. Any dimension of Geometry may be added; the constituent linework will be extracted.

Parameters:

geometry - the geometry to add

addLine

private void addLine(LineString lineString)

isSequenceable

public boolean isSequenceable()

Tests whether the arrangement of linestrings has a valid sequence.

Returns:

true if a valid sequence exists.

getSequencedLineStrings

public Geometry getSequencedLineStrings()

Returns the LineString or MultiLineString built by the sequencing process, if one exists.

Returns:

the sequenced linestrings, or null if a valid sequence does not exist

computeSequence

private void computeSequence()

findSequences

private java.util.List findSequences()

hasSequence

private boolean hasSequence(Subgraph graph)

Tests whether a complete unique path exists in a graph using Euler's Theorem.

Parameters:

graph - the subgraph containing the edges

Returns:

true if a sequence exists

findSequence

private java.util.List findSequence(Subgraph graph)

findUnvisitedBestOrientedDE

private static DirectedEdge findUnvisitedBestOrientedDE(Node node)

Finds an DirectedEdge for an unvisited edge (if any), choosing the dirEdge which preserves orientation, if possible.

Parameters:

node - the node to examine

Returns:

the dirEdge found, or null if none were unvisited

addReverseSubpath

private void addReverseSubpath(DirectedEdge de,
                               java.util.ListIterator lit,
                               boolean expectedClosed)

findLowestDegreeNode

private static Node findLowestDegreeNode(Subgraph graph)

orient

private java.util.List orient(java.util.List seq)

Computes a version of the sequence which is optimally oriented relative to the underlying geometry.

Heuristics used are:

• If the path has a degree-1 node which is the start node of an linestring, use that node as the start of the sequence
• If the path has a degree-1 node which is the end node of an linestring, use that node as the end of the sequence
• If the sequence has no degree-1 nodes, use any node as the start (NOTE: in this case could orient the sequence according to the majority of the linestring orientations)

Parameters:

seq - a List of DirectedEdges

Returns:

a List of DirectedEdges oriented appropriately

reverse

private java.util.List reverse(java.util.List seq)

Reverse the sequence. This requires reversing the order of the dirEdges, and flipping each dirEdge as well

Parameters:

seq - a List of DirectedEdges, in sequential order

Returns:

the reversed sequence

buildSequencedGeometry

private Geometry buildSequencedGeometry(java.util.List sequences)

Builds a geometry (LineString or MultiLineString ) representing the sequence.

Parameters:

sequences - a List of Lists of DirectedEdges with LineMergeEdges as their parent edges.

Returns:

the sequenced geometry, or null if no sequence exists

reverse

private static LineString reverse(LineString line)