GEOS  3.8.0dev
Public Member Functions | Static Public Member Functions | List of all members
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:
geos::planargraph::PlanarGraph

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. 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.
 
NodefindNode (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. 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()
 
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.
 
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. More...
 

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

Member Function Documentation

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

Add a LineString forming an edge of the polygon graph.

Parameters
linethe line to add
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
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: