Represents a planar graph of edges that can be used to compute a polygonization, and implements the algorithms to compute the EdgeRings formed by the graph. More...

#include <PolygonizeGraph.h>

Inheritance diagram for geos::operation::polygonize::PolygonizeGraph:

[legend]

Collaboration diagram for geos::operation::polygonize::PolygonizeGraph:

[legend]

Public Member Functions
	PolygonizeGraph (const geom::GeometryFactory *newFactory)
	Create a new polygonization graph. More...

	~PolygonizeGraph () override
	Destroy a polygonization graph. More...

void	addEdge (const geom::LineString *line)
	Add a LineString forming an edge of the polygon graph. More...

void	getEdgeRings (std::vector< EdgeRing * > &edgeRingList)
	Computes the EdgeRings formed by the edges in this graph. More...

void	deleteCutEdges (std::vector< const geom::LineString * > &cutLines)
	Finds and removes all cut edges from the graph. More...

void	deleteDangles (std::vector< const geom::LineString * > &dangleLines)
	Marks all edges from the graph which are "dangles". More...

Public Member Functions inherited from geos::planargraph::PlanarGraph
	PlanarGraph ()
	Constructs a PlanarGraph without any Edges, DirectedEdges, or Nodes. More...

virtual	~PlanarGraph ()

Node *	findNode (const geom::Coordinate &pt)
	Returns the Node at the given location, or null if no Node was there. More...

NodeMap::container::iterator	nodeIterator ()
	Returns an Iterator over the Nodes in this PlanarGraph. More...

NodeMap::container::iterator	nodeBegin ()

NodeMap::container::const_iterator	nodeBegin () const

NodeMap::container::iterator	nodeEnd ()

NodeMap::container::const_iterator	nodeEnd () const

void	getNodes (std::vector< Node * > &nodes)
	Returns the Nodes in this PlanarGraph. More...

std::vector< DirectedEdge * >::iterator	dirEdgeIterator ()
	Returns an Iterator over the DirectedEdges in this PlanarGraph, in the order in which they were added. More...

std::vector< Edge * >::iterator	edgeIterator ()
	Alias for edgeBegin() More...

std::vector< Edge * >::iterator	edgeBegin ()
	Returns an iterator to first Edge in this graph. More...

std::vector< Edge * >::iterator	edgeEnd ()
	Returns an iterator to one-past last Edge in this graph. More...

std::vector< Edge * > *	getEdges ()

void	remove (Edge *edge)
	Removes an Edge and its associated DirectedEdges from their from-Nodes and from this PlanarGraph. More...

void	remove (DirectedEdge *de)
	Removes DirectedEdge from its from-Node and from this PlanarGraph. More...

void	remove (Node *node)
	Removes a node from the graph, along with any associated DirectedEdges and Edges. More...

std::vector< Node * > *	findNodesOfDegree (std::size_t degree)
	Returns all Nodes with the given number of Edges around it. The return value is a newly allocated vector of existing nodes. More...

void	findNodesOfDegree (std::size_t degree, std::vector< Node * > &to)
	Get all Nodes with the given number of Edges around it. More...

Static Public Member Functions
static void	deleteAllEdges (planargraph::Node *node)
	Deletes all edges at a node. More...

Private Member Functions
planargraph::Node *	getNode (const geom::Coordinate &pt)

void	computeNextCWEdges ()

void	convertMaximalToMinimalEdgeRings (std::vector< PolygonizeDirectedEdge * > &ringEdges)
	Convert the maximal edge rings found by the initial graph traversal into the minimal edge rings required by JTS polygon topology rules. More...

EdgeRing *	findEdgeRing (PolygonizeDirectedEdge *startDE)

Static Private Member Functions
static int	getDegreeNonDeleted (planargraph::Node *node)

static int	getDegree (planargraph::Node *node, long label)

static void	findIntersectionNodes (PolygonizeDirectedEdge startDE, long label, std::vector< planargraph::Node > &intNodes)
	Finds all nodes in a maximal edgering which are self-intersection nodes. More...

static void	findLabeledEdgeRings (std::vector< planargraph::DirectedEdge * > &dirEdgesIn, std::vector< PolygonizeDirectedEdge * > &dirEdgesOut)

static void	label (std::vector< PolygonizeDirectedEdge * > &dirEdges, long label)

static void	label (std::vector< planargraph::DirectedEdge * > &dirEdges, long label)

static void	computeNextCWEdges (planargraph::Node *node)

static void	computeNextCCWEdges (planargraph::Node *node, long label)
	Computes the next edge pointers going CCW around the given node, for the given edgering label. This algorithm has the effect of converting maximal edgerings into minimal edgerings. More...

Private Attributes
const geom::GeometryFactory *	factory

std::vector< planargraph::Edge * >	newEdges

std::vector< planargraph::DirectedEdge * >	newDirEdges

std::vector< planargraph::Node * >	newNodes

std::vector< EdgeRing * >	newEdgeRings

std::vector< geom::CoordinateSequence * >	newCoords

Additional Inherited Members
Public Types inherited from geos::planargraph::PlanarGraph
typedef std::vector< Edge * >	EdgeContainer

typedef EdgeContainer::iterator	EdgeIterator

Protected Member Functions inherited from geos::planargraph::PlanarGraph
void	add (Node *node)
	Adds a node to the std::map, replacing any that is already at that location. More...

void	add (Edge *edge)
	Adds the Edge and its DirectedEdges with this PlanarGraph. More...

void	add (DirectedEdge *dirEdge)
	Adds the Edge to this PlanarGraph. More...

Protected Attributes inherited from geos::planargraph::PlanarGraph
std::vector< Edge * >	edges

std::vector< DirectedEdge * >	dirEdges

NodeMap	nodeMap

Detailed Description

Represents a planar graph of edges that can be used to compute a polygonization, and implements the algorithms to compute the EdgeRings formed by the graph.

The marked flag on DirectedEdge is used to indicate that a directed edge has be logically deleted from the graph.

Definition at line 69 of file PolygonizeGraph.h.

Constructor & Destructor Documentation

geos::operation::polygonize::PolygonizeGraph::PolygonizeGraph ( const geom::GeometryFactory * newFactory )

explicit

Create a new polygonization graph.

geos::operation::polygonize::PolygonizeGraph::~PolygonizeGraph ( )

override

Destroy a polygonization graph.

Member Function Documentation

void geos::operation::polygonize::PolygonizeGraph::addEdge ( const geom::LineString * line )

Add a LineString forming an edge of the polygon graph.

Parameters

line	the line to add

static void geos::operation::polygonize::PolygonizeGraph::computeNextCCWEdges	(	planargraph::Node *	node,
		long	label
	)

staticprivate

Computes the next edge pointers going CCW around the given node, for the given edgering label. This algorithm has the effect of converting maximal edgerings into minimal edgerings.

void geos::operation::polygonize::PolygonizeGraph::computeNextCWEdges ( )

private

static void geos::operation::polygonize::PolygonizeGraph::computeNextCWEdges ( planargraph::Node * node )

staticprivate

void geos::operation::polygonize::PolygonizeGraph::convertMaximalToMinimalEdgeRings ( std::vector< PolygonizeDirectedEdge * > & ringEdges )

private

Convert the maximal edge rings found by the initial graph traversal into the minimal edge rings required by JTS polygon topology rules.

Parameters

ringEdges the list of start edges for the edgeRings to convert.

static void geos::operation::polygonize::PolygonizeGraph::deleteAllEdges ( planargraph::Node * node )

static

Deletes all edges at a node.

void geos::operation::polygonize::PolygonizeGraph::deleteCutEdges ( std::vector< const geom::LineString * > & cutLines )

Finds and removes all cut edges from the graph.

Parameters

cutLines : the list of the LineString forming the removed cut edges will be pushed here.

TODO: document ownership of the returned LineStrings

void geos::operation::polygonize::PolygonizeGraph::deleteDangles ( std::vector< const geom::LineString * > & dangleLines )

Marks all edges from the graph which are "dangles".

Dangles are which are incident on a node with degree 1. This process is recursive, since removing a dangling edge may result in another edge becoming a dangle. In order to handle large recursion depths efficiently, an explicit recursion stack is used

Parameters

dangleLines : the LineStrings that formed dangles will be push_back'ed here

EdgeRing* geos::operation::polygonize::PolygonizeGraph::findEdgeRing ( PolygonizeDirectedEdge * startDE )

private

static void geos::operation::polygonize::PolygonizeGraph::findIntersectionNodes	(	PolygonizeDirectedEdge *	startDE,
		long	label,
		std::vector< planargraph::Node * > &	intNodes
	)

staticprivate

Finds all nodes in a maximal edgering which are self-intersection nodes.

Parameters

startDE
label
intNodes	: intersection nodes found will be pushed here the vector won't be cleared before pushing.

static void geos::operation::polygonize::PolygonizeGraph::findLabeledEdgeRings	(	std::vector< planargraph::DirectedEdge * > &	dirEdgesIn,
		std::vector< PolygonizeDirectedEdge * > &	dirEdgesOut
	)

staticprivate

Finds and labels all edgerings in the graph.

The edge rings are labeling with unique integers. The labeling allows detecting cut edges.

Parameters

dirEdgesIn	a list of the DirectedEdges in the graph
dirEdgesOut	each ring found will be pushed here

static int geos::operation::polygonize::PolygonizeGraph::getDegree	(	planargraph::Node *	node,
		long	label
	)

staticprivate

static int geos::operation::polygonize::PolygonizeGraph::getDegreeNonDeleted ( planargraph::Node * node )

staticprivate

void geos::operation::polygonize::PolygonizeGraph::getEdgeRings ( std::vector< EdgeRing * > & edgeRingList )

Computes the EdgeRings formed by the edges in this graph.

Parameters

edgeRingList : the EdgeRing found by the polygonization process will be pushed here.

planargraph::Node* geos::operation::polygonize::PolygonizeGraph::getNode ( const geom::Coordinate & pt )

private

static void geos::operation::polygonize::PolygonizeGraph::label	(	std::vector< PolygonizeDirectedEdge * > &	dirEdges,
		long	label
	)

staticprivate

static void geos::operation::polygonize::PolygonizeGraph::label	(	std::vector< planargraph::DirectedEdge * > &	dirEdges,
		long	label
	)

staticprivate

Member Data Documentation

const geom::GeometryFactory* geos::operation::polygonize::PolygonizeGraph::factory

private

Definition at line 139 of file PolygonizeGraph.h.

std::vector<geom::CoordinateSequence*> geos::operation::polygonize::PolygonizeGraph::newCoords

private

Definition at line 205 of file PolygonizeGraph.h.

std::vector<planargraph::DirectedEdge*> geos::operation::polygonize::PolygonizeGraph::newDirEdges

private

Definition at line 202 of file PolygonizeGraph.h.

std::vector<EdgeRing*> geos::operation::polygonize::PolygonizeGraph::newEdgeRings

private

Definition at line 204 of file PolygonizeGraph.h.

std::vector<planargraph::Edge*> geos::operation::polygonize::PolygonizeGraph::newEdges

private

Definition at line 201 of file PolygonizeGraph.h.

std::vector<planargraph::Node*> geos::operation::polygonize::PolygonizeGraph::newNodes

private

Definition at line 203 of file PolygonizeGraph.h.

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

PolygonizeGraph.h

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation