Class LineSequencer
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
isSequenceable()
method
will return false
.- Version:
- 1.7
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate GeometryFactory
private LineMergeGraph
private boolean
private boolean
private int
private Geometry
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
add
(Collection geometries) Adds aCollection
ofGeometry
s to be sequenced.void
Adds aGeometry
to be sequenced.private void
addLine
(LineString lineString) private void
addReverseSubpath
(DirectedEdge de, ListIterator lit, boolean expectedClosed) private Geometry
buildSequencedGeometry
(List sequences) Builds a geometry (LineString
orMultiLineString
) representing the sequence.private void
private static Node
findLowestDegreeNode
(Subgraph graph) private List
findSequence
(Subgraph graph) private List
private static DirectedEdge
Finds anDirectedEdge
for an unvisited edge (if any), choosing the dirEdge which preserves orientation, if possible.Returns theLineString
orMultiLineString
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
Tests whether the arrangement of linestrings has a valid sequence.static boolean
isSequenced
(Geometry geom) Tests whether aGeometry
is sequenced correctly.private List
Computes a version of the sequence which is optimally oriented relative to the underlying geometry.private List
Reverse the sequence.private static LineString
reverse
(LineString line) static Geometry
-
Field Details
-
graph
-
factory
-
lineCount
private int lineCount -
isRun
private boolean isRun -
sequencedGeometry
-
isSequenceable
private boolean isSequenceable
-
-
Constructor Details
-
LineSequencer
public LineSequencer()
-
-
Method Details
-
sequence
-
isSequenced
Tests whether aGeometry
is sequenced correctly.LineString
s are trivially sequenced.MultiLineString
s are checked for correct sequencing. Otherwise,isSequenced
is defined to betrue
for geometries that are not lineal.- Parameters:
geom
- the geometry to test- Returns:
true
if the geometry is sequenced or is not lineal
-
add
Adds aCollection
ofGeometry
s 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
Adds aGeometry
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
-
isSequenceable
public boolean isSequenceable()Tests whether the arrangement of linestrings has a valid sequence.- Returns:
true
if a valid sequence exists.
-
getSequencedLineStrings
Returns theLineString
orMultiLineString
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
-
hasSequence
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
-
findUnvisitedBestOrientedDE
Finds anDirectedEdge
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
-
findLowestDegreeNode
-
orient
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
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
Builds a geometry (LineString
orMultiLineString
) 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
-