geos::operation::polygonize::PolygonizeGraph Class Reference

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:

## Public Member Functions

| PolygonizeGraph (const geom::GeometryFactory *newFactory)
| Create a new polygonization graph.
| ~PolygonizeGraph () override
| Destroy a polygonization graph.
void | addEdge (const geom::LineString *line)
| Add a LineString forming an edge of the polygon graph.
void | getEdgeRings (std::vector< EdgeRing * > &edgeRingList)
| Computes the EdgeRings formed by the edges in this graph.
void | deleteCutEdges (std::vector< const geom::LineString * > &cutLines)
| Finds and removes all cut edges from the graph.
void | deleteDangles (std::vector< const geom::LineString * > &dangleLines)
| Marks all edges from the graph which are "dangles".
Public Member Functions inherited from geos::planargraph::PlanarGraph
| PlanarGraph ()
| Constructs a PlanarGraph without any Edges, DirectedEdges, or Nodes.
Node * | findNode (const geom::Coordinate &pt)
| Returns the Node at the given location, or null if no Node was there.
NodeMap::container::iterator | nodeIterator ()
| Returns an Iterator over the Nodes in this PlanarGraph.
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.
std::vector< DirectedEdge * >::iterator | dirEdgeIterator ()
| Returns an Iterator over the DirectedEdges in this PlanarGraph, in the order in which they were added.
std::vector< DirectedEdge * >::iterator | dirEdgeBegin ()
std::vector< DirectedEdge * >::iterator | dirEdgeEnd ()
std::vector< Edge * >::iterator | edgeIterator ()
| Alias for edgeBegin().
std::vector< Edge * >::iterator | edgeBegin ()
| Returns an iterator to first Edge in this graph.
std::vector< Edge * >::iterator | edgeEnd ()
| Returns an iterator to one-past last Edge in this graph.
std::vector< Edge * > * | getEdges ()
void | remove (Edge *edge)
| Removes an Edge and its associated DirectedEdges from their from-Nodes and from this PlanarGraph.
void | remove (DirectedEdge *de)
| Removes DirectedEdge from its from-Node and from this PlanarGraph.
void | remove (Node *node)
| Removes a node from the graph, along with any associated DirectedEdges and Edges.
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.
void | findNodesOfDegree (std::size_t degree, std::vector< Node * > &to)
| Get all Nodes with the given number of Edges around it.

## Static Public Member Functions

static void | deleteAllEdges (planargraph::Node *node)
| Deletes all edges at a node.

## 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.
void | add (Edge *edge)
| Adds the Edge and its DirectedEdges with this PlanarGraph.
void | add (DirectedEdge *dirEdge)
| Adds the Edge to this PlanarGraph.
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.

## Member Function Documentation

## addEdge()

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

## deleteCutEdges()

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

## deleteDangles()

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

## getEdgeRings()

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.

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

- PolygonizeGraph.h