Builds a sequence from a set of LineStrings so that they are ordered end to end. More...

#include <LineSequencer.h>

Collaboration diagram for geos::operation::linemerge::LineSequencer:

Public Member Functions
	LineSequencer ()

bool	isSequenceable ()
	Tests whether the arrangement of linestrings has a valid sequence. More...

void	add (const geom::Geometry &geometry)
	Adds a Geometry to be sequenced. More...

template<class TargetContainer >
void	add (TargetContainer &geoms)

void	filter (const geom::Geometry *g)
	Act as a GeometryComponentFilter so to extract the linearworks. More...

geom::Geometry *	getSequencedLineStrings (bool release=1)
	Returns the LineString or MultiLineString built by the sequencing process, if one exists. More...

Static Public Member Functions
static geom::Geometry *	sequence (const geom::Geometry &geom)

static bool	isSequenced (const geom::Geometry *geom)
	Tests whether a Geometry is sequenced correctly. More...

Private Types
typedef std::list< planargraph::DirectedEdge * >	DirEdgeList

typedef std::vector< DirEdgeList * >	Sequences

Private Member Functions
void	addLine (const geom::LineString *lineString)

void	computeSequence ()

Sequences *	findSequences ()

DirEdgeList *	findSequence (planargraph::Subgraph &graph)

void	delAll (Sequences &)

geom::Geometry *	buildSequencedGeometry (const Sequences &sequences)

void	addReverseSubpath (const planargraph::DirectedEdge *de, DirEdgeList &deList, DirEdgeList::iterator lit, bool expectedClosed)

DirEdgeList *	orient (DirEdgeList *seq)

DirEdgeList *	reverse (DirEdgeList &seq)

bool	hasSequence (planargraph::Subgraph &graph)

Static Private Member Functions
static geom::LineString *	reverse (const geom::LineString *line)
	return a newly allocated LineString More...

static const planargraph::Node *	findLowestDegreeNode (const planargraph::Subgraph &graph)

static const planargraph::DirectedEdge *	findUnvisitedBestOrientedDE (const planargraph::Node *node)

Private Attributes
LineMergeGraph	graph

const geom::GeometryFactory *	factory

unsigned int	lineCount

bool	isRun

std::unique_ptr< geom::Geometry >	sequencedGeometry

bool	isSequenceableVar

Detailed Description

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: 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.

Definition at line 93 of file LineSequencer.h.

Member Typedef Documentation

typedef std::list<planargraph::DirectedEdge*> geos::operation::linemerge::LineSequencer::DirEdgeList

private

Definition at line 96 of file LineSequencer.h.

typedef std::vector< DirEdgeList* > geos::operation::linemerge::LineSequencer::Sequences

private

Definition at line 97 of file LineSequencer.h.

Constructor & Destructor Documentation

geos::operation::linemerge::LineSequencer::LineSequencer ( )

inline

Definition at line 198 of file LineSequencer.h.

Member Function Documentation

void geos::operation::linemerge::LineSequencer::add ( const geom::Geometry & geometry )

inline

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

Definition at line 243 of file LineSequencer.h.

References geos::geom::Geometry::applyComponentFilter().

Referenced by sequence().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TargetContainer >

void geos::operation::linemerge::LineSequencer::add ( TargetContainer & geoms )

inline

Definition at line 250 of file LineSequencer.h.

void geos::operation::linemerge::LineSequencer::addLine ( const geom::LineString * lineString )

private

void geos::operation::linemerge::LineSequencer::addReverseSubpath	(	const planargraph::DirectedEdge *	de,
		DirEdgeList &	deList,
		DirEdgeList::iterator	lit,
		bool	expectedClosed
	)

private

geom::Geometry* geos::operation::linemerge::LineSequencer::buildSequencedGeometry ( const Sequences & sequences )

private

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

Parameters

sequences a vector of vectors of const planarDirectedEdges with LineMergeEdges as their parent edges. Ownership of container and contents retained by caller.

Returns: the sequenced geometry, possibly NULL if no sequence exists

void geos::operation::linemerge::LineSequencer::computeSequence ( )

private

void geos::operation::linemerge::LineSequencer::delAll ( Sequences & )

private

void geos::operation::linemerge::LineSequencer::filter ( const geom::Geometry * g )

inline

Act as a GeometryComponentFilter so to extract the linearworks.

Definition at line 264 of file LineSequencer.h.

static const planargraph::Node* geos::operation::linemerge::LineSequencer::findLowestDegreeNode ( const planargraph::Subgraph & graph )

staticprivate

DirEdgeList* geos::operation::linemerge::LineSequencer::findSequence ( planargraph::Subgraph & graph )

private

Sequences* geos::operation::linemerge::LineSequencer::findSequences ( )

private

static const planargraph::DirectedEdge* geos::operation::linemerge::LineSequencer::findUnvisitedBestOrientedDE ( const planargraph::Node * node )

staticprivate

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

geom::Geometry* geos::operation::linemerge::LineSequencer::getSequencedLineStrings ( bool release = 1 )

inline

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

Parameters

release release ownership of computed Geometry

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

Definition at line 281 of file LineSequencer.h.

Referenced by sequence().

Here is the caller graph for this function:

bool geos::operation::linemerge::LineSequencer::hasSequence ( planargraph::Subgraph & graph )

private

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

bool geos::operation::linemerge::LineSequencer::isSequenceable ( )

inline

Tests whether the arrangement of linestrings has a valid sequence.

Returns: true if a valid sequence exists.

Definition at line 227 of file LineSequencer.h.

static bool geos::operation::linemerge::LineSequencer::isSequenced ( const geom::Geometry * geom )

static

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

DirEdgeList* geos::operation::linemerge::LineSequencer::orient ( DirEdgeList * seq )

private

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 planarDirectedEdges

Returns: the oriented sequence, possibly same as input if already oriented

static geom::LineString* geos::operation::linemerge::LineSequencer::reverse ( const geom::LineString * line )

staticprivate

return a newly allocated LineString

DirEdgeList* geos::operation::linemerge::LineSequencer::reverse ( DirEdgeList & seq )

private

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

static geom::Geometry* geos::operation::linemerge::LineSequencer::sequence ( const geom::Geometry & geom )

inlinestatic

Definition at line 191 of file LineSequencer.h.

References add(), and getSequencedLineStrings().

Here is the call graph for this function:

Member Data Documentation

const geom::GeometryFactory* geos::operation::linemerge::LineSequencer::factory

private

Definition at line 100 of file LineSequencer.h.

LineMergeGraph geos::operation::linemerge::LineSequencer::graph

private

Definition at line 99 of file LineSequencer.h.

bool geos::operation::linemerge::LineSequencer::isRun

private

Definition at line 102 of file LineSequencer.h.

bool geos::operation::linemerge::LineSequencer::isSequenceableVar

private

Definition at line 104 of file LineSequencer.h.

unsigned int geos::operation::linemerge::LineSequencer::lineCount

private

Definition at line 101 of file LineSequencer.h.

std::unique_ptr<geom::Geometry> geos::operation::linemerge::LineSequencer::sequencedGeometry

private

Definition at line 103 of file LineSequencer.h.

The documentation for this class was generated from the following file:

LineSequencer.h

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation