public class LineSequencer
extends java.lang.Object
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:
isSequenceable()
method
will return false
.Modifier and Type | Field and Description |
---|---|
private GeometryFactory |
factory |
private LineMergeGraph |
graph |
private boolean |
isRun |
private boolean |
isSequenceable |
private int |
lineCount |
private Geometry |
sequencedGeometry |
Constructor and Description |
---|
LineSequencer() |
Modifier and Type | Method and Description |
---|---|
void |
add(java.util.Collection geometries)
Adds a
Collection of Geometry s 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 static LineString |
reverse(LineString line) |
private java.util.List |
reverse(java.util.List seq)
Reverse the sequence.
|
static Geometry |
sequence(Geometry geom) |
private LineMergeGraph graph
private GeometryFactory factory
private int lineCount
private boolean isRun
private Geometry sequencedGeometry
private boolean isSequenceable
public static boolean isSequenced(Geometry geom)
Geometry
is sequenced correctly.
LineString
s are trivially sequenced.
MultiLineString
s are checked for correct sequencing.
Otherwise, isSequenced
is defined
to be true
for geometries that are not lineal.geom
- the geometry to testtrue
if the geometry is sequenced or is not linealpublic void add(java.util.Collection geometries)
Collection
of Geometry
s to be sequenced.
May be called multiple times.
Any dimension of Geometry may be added; the constituent linework will be
extracted.geometries
- a Collection of geometries to addpublic void add(Geometry geometry)
Geometry
to be sequenced.
May be called multiple times.
Any dimension of Geometry may be added; the constituent linework will be
extracted.geometry
- the geometry to addprivate void addLine(LineString lineString)
public boolean isSequenceable()
true
if a valid sequence exists.public Geometry getSequencedLineStrings()
LineString
or MultiLineString
built by the sequencing process, if one exists.null
if a valid sequence does not existprivate void computeSequence()
private java.util.List findSequences()
private boolean hasSequence(Subgraph graph)
graph
- the subgraph containing the edgestrue
if a sequence existsprivate java.util.List findSequence(Subgraph graph)
private static DirectedEdge findUnvisitedBestOrientedDE(Node node)
DirectedEdge
for an unvisited edge (if any),
choosing the dirEdge which preserves orientation, if possible.node
- the node to examinenull
if none were unvisitedprivate void addReverseSubpath(DirectedEdge de, java.util.ListIterator lit, boolean expectedClosed)
private java.util.List orient(java.util.List seq)
Heuristics used are:
seq
- a List of DirectedEdgesprivate java.util.List reverse(java.util.List seq)
seq
- a List of DirectedEdges, in sequential orderprivate Geometry buildSequencedGeometry(java.util.List sequences)
LineString
or MultiLineString
)
representing the sequence.sequences
- a List of Lists of DirectedEdges with
LineMergeEdges as their parent edges.null
if no sequence existsprivate static LineString reverse(LineString line)