GEOS
3.9.0dev

A class that contains the QuadEdges representing a planar subdivision that models a triangulation. More...
#include <QuadEdgeSubdivision.h>
Public Types  
typedef std::vector< QuadEdge * >  QuadEdgeList 
Public Member Functions  
QuadEdgeSubdivision (const geom::Envelope &env, double tolerance)  
Creates a new instance of a quadedge subdivision based on a frame triangle that encloses a supplied bounding box. A new superbounding box that contains the triangle is computed and stored. More...  
double  getTolerance () const 
Gets the vertexequality tolerance value used in this subdivision. More...  
const geom::Envelope &  getEnvelope () const 
Gets the envelope of the Subdivision (including the frame). More...  
std::deque< QuadEdgeQuartet > &  getEdges () 
Gets the collection of base QuadEdges (one for every pair of vertices which is connected). More...  
void  setLocator (std::unique_ptr< QuadEdgeLocator > p_locator) 
Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision. More...  
virtual QuadEdge &  makeEdge (const Vertex &o, const Vertex &d) 
Creates a new quadedge, recording it in the edges list. More...  
virtual QuadEdge &  connect (QuadEdge &a, QuadEdge &b) 
Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all three have the same left face after the connection is complete. The quadedge is recorded in the edges list. More...  
void  remove (QuadEdge &e) 
Deletes a quadedge from the subdivision. Linked quadedges are updated to reflect the deletion. More...  
QuadEdge *  locateFromEdge (const Vertex &v, const QuadEdge &startEdge) const 
Locates an edge of a triangle which contains a location specified by a Vertex v . More...  
QuadEdge *  locate (const Vertex &v) const 
Finds a quadedge of a triangle containing a location specified by a Vertex, if one exists. More...  
QuadEdge *  locate (const geom::Coordinate &p) 
Finds a quadedge of a triangle containing a location specified by a geom::Coordinate, if one exists. More...  
QuadEdge *  locate (const geom::Coordinate &p0, const geom::Coordinate &p1) 
Locates the edge between the given vertices, if it exists in the subdivision. More...  
QuadEdge &  insertSite (const Vertex &v) 
Inserts a new site into the Subdivision, connecting it to the vertices of the containing triangle (or quadrilateral, if the split point falls on an existing edge). More...  
bool  isFrameEdge (const QuadEdge &e) const 
Tests whether a QuadEdge is an edge incident on a frame triangle vertex. More...  
bool  isFrameBorderEdge (const QuadEdge &e) const 
Tests whether a QuadEdge is an edge on the border of the frame facets and the internal facets. E.g. an edge which does not itself touch a frame vertex, but which touches an edge which does. More...  
bool  isFrameVertex (const Vertex &v) const 
Tests whether a vertex is a vertex of the outer triangle. More...  
bool  isOnEdge (const QuadEdge &e, const geom::Coordinate &p) const 
Tests whether a Coordinate lies on a QuadEdge, up to a tolerance determined by the subdivision tolerance. More...  
bool  isVertexOfEdge (const QuadEdge &e, const Vertex &v) const 
Tests whether a Vertex is the start or end vertex of a QuadEdge, up to the subdivision tolerance distance. More...  
std::unique_ptr< QuadEdgeList >  getPrimaryEdges (bool includeFrame) 
Gets all primary quadedges in the subdivision. More...  
void  visitTriangles (TriangleVisitor *triVisitor, bool includeFrame) 
std::unique_ptr < geom::MultiLineString >  getEdges (const geom::GeometryFactory &geomFact) 
Gets the geometry for the edges in the subdivision as a MultiLineString containing 2point lines. More...  
std::unique_ptr < geom::GeometryCollection >  getTriangles (const geom::GeometryFactory &geomFact) 
Gets the geometry for the triangles in a triangulated subdivision as a GeometryCollection of triangular Polygons. More...  
std::unique_ptr < geom::GeometryCollection >  getVoronoiDiagram (const geom::GeometryFactory &geomFact) 
Gets the cells in the Voronoi diagram for this triangulation. The cells are returned as a GeometryCollection of Polygons. More...  
std::unique_ptr < geom::MultiLineString >  getVoronoiDiagramEdges (const geom::GeometryFactory &geomFact) 
Gets the cells in the Voronoi diagram for this triangulation. More...  
std::vector< std::unique_ptr < geom::Geometry > >  getVoronoiCellPolygons (const geom::GeometryFactory &geomFact) 
Gets a List of Polygons for the Voronoi cells of this triangulation. More...  
std::vector< std::unique_ptr < geom::Geometry > >  getVoronoiCellEdges (const geom::GeometryFactory &geomFact) 
Gets a List of LineStrings for the Voronoi cells of this triangulation. More...  
std::unique_ptr < QuadEdgeSubdivision::QuadEdgeList >  getVertexUniqueEdges (bool includeFrame) 
Gets a collection of QuadEdges whose origin vertices are a unique set which includes all vertices in the subdivision. More...  
std::unique_ptr< geom::Geometry >  getVoronoiCellPolygon (const QuadEdge *qe, const geom::GeometryFactory &geomFact) 
Gets the Voronoi cell around a site specified by the origin of a QuadEdge. More...  
std::unique_ptr< geom::Geometry >  getVoronoiCellEdge (const QuadEdge *qe, const geom::GeometryFactory &geomFact) 
Gets the Voronoi cell edge around a site specified by the origin of a QuadEdge. More...  
Static Public Member Functions  
static void  getTriangleEdges (const QuadEdge &startQE, const QuadEdge *triEdge[3]) 
Gets the edges for the triangle to the left of the given QuadEdge. More...  
A class that contains the QuadEdges representing a planar subdivision that models a triangulation.
The subdivision is constructed using the quadedge algebra defined in the class QuadEdge.
All metric calculations are done in the Vertex class. In addition to a triangulation, subdivisions support extraction of Voronoi diagrams. This is easily accomplished, since the Voronoi diagram is the dual of the Delaunay triangulation.
Subdivisions can be provided with a tolerance value. Inserted vertices which are closer than this value to vertices already in the subdivision will be ignored. Using a suitable tolerance value can prevent robustness failures from happening during Delaunay triangulation.
Subdivisions maintain a frame triangle around the clientcreated edges. The frame is used to provide a bounded "container" for all edges within a TIN. Normally the frame edges, frame connecting edges, and frame triangles are not included in client processing.
geos::triangulate::quadedge::QuadEdgeSubdivision::QuadEdgeSubdivision  (  const geom::Envelope &  env, 
double  tolerance  
) 
Creates a new instance of a quadedge subdivision based on a frame triangle that encloses a supplied bounding box. A new superbounding box that contains the triangle is computed and stored.
env  the bouding box to surround 
tolerance  the tolerance value for determining if two sites are equal 

virtual 
Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all three have the same left face after the connection is complete. The quadedge is recorded in the edges list.
a  
b 

inline 
Gets the collection of base QuadEdges (one for every pair of vertices which is connected).
std::unique_ptr<geom::MultiLineString> geos::triangulate::quadedge::QuadEdgeSubdivision::getEdges  (  const geom::GeometryFactory &  geomFact  ) 
Gets the geometry for the edges in the subdivision as a MultiLineString containing 2point lines.
geomFact  the GeometryFactory to use 

inline 
Gets the envelope of the Subdivision (including the frame).
std::unique_ptr<QuadEdgeList> geos::triangulate::quadedge::QuadEdgeSubdivision::getPrimaryEdges  (  bool  includeFrame  ) 
Gets all primary quadedges in the subdivision.
A primary edge is a QuadEdge which occupies the 0'th position in its array of associated quadedges. These provide the unique geometric edges of the triangulation.
includeFrame  true if the frame edges are to be included 

inline 
Gets the vertexequality tolerance value used in this subdivision.

static 
Gets the edges for the triangle to the left of the given QuadEdge.
startQE  
triEdge 
IllegalArgumentException  if the edges do not form a triangle 
std::unique_ptr<geom::GeometryCollection> geos::triangulate::quadedge::QuadEdgeSubdivision::getTriangles  (  const geom::GeometryFactory &  geomFact  ) 
Gets the geometry for the triangles in a triangulated subdivision as a GeometryCollection of triangular Polygons.
geomFact  the GeometryFactory to use 
std::unique_ptr<QuadEdgeSubdivision::QuadEdgeList> geos::triangulate::quadedge::QuadEdgeSubdivision::getVertexUniqueEdges  (  bool  includeFrame  ) 
Gets a collection of QuadEdges whose origin vertices are a unique set which includes all vertices in the subdivision.
The frame vertices can be included if required. This is useful for algorithms which require traversing the subdivision starting at all vertices. Returning a quadedge for each vertex is more efficient than the alternative of finding the actual vertices using getVertices()
and then locating quadedges attached to them.
includeFrame  true if the frame vertices should be included 
std::unique_ptr<geom::Geometry> geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiCellEdge  (  const QuadEdge *  qe, 
const geom::GeometryFactory &  geomFact  
) 
Gets the Voronoi cell edge around a site specified by the origin of a QuadEdge.
The userData of the LineString is set to be the Coordinate of the site. This allows attaching external data associated with the site to this cell polygon.
qe  a quadedge originating at the cell site 
geomFact  a factory for building the polygon 
std::vector<std::unique_ptr<geom::Geometry> > geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiCellEdges  (  const geom::GeometryFactory &  geomFact  ) 
Gets a List of LineStrings for the Voronoi cells of this triangulation.
The userData of each LineString is set to be the Coordinate of the cell site. This allows easily associating external data associated with the sites to the cells.
geomFact  a geometry factory 
std::unique_ptr<geom::Geometry> geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiCellPolygon  (  const QuadEdge *  qe, 
const geom::GeometryFactory &  geomFact  
) 
Gets the Voronoi cell around a site specified by the origin of a QuadEdge.
The userData of the polygon is set to be the Coordinate of the site. This allows attaching external data associated with the site to this cell polygon.
qe  a quadedge originating at the cell site 
geomFact  a factory for building the polygon 
std::vector<std::unique_ptr<geom::Geometry> > geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiCellPolygons  (  const geom::GeometryFactory &  geomFact  ) 
Gets a List of Polygons for the Voronoi cells of this triangulation.
The userData of each polygon is set to be the Coordinate of the cell site. This allows easily associating external data associated with the sites to the cells.
geomFact  a geometry factory 
std::unique_ptr<geom::GeometryCollection> geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiDiagram  (  const geom::GeometryFactory &  geomFact  ) 
Gets the cells in the Voronoi diagram for this triangulation. The cells are returned as a GeometryCollection of Polygons.
The userData of each polygon is set to be the Coordinate of the cell site. This allows easily associating external data associated with the sites to the cells.
geomFact  a geometry factory 
std::unique_ptr<geom::MultiLineString> geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiDiagramEdges  (  const geom::GeometryFactory &  geomFact  ) 
Gets the cells in the Voronoi diagram for this triangulation.
The cells are returned as a GeometryCollection of LineStrings. The userData of each polygon is set to be the Coordinate of the cell site. This allows easily associating external data associated with the sites to the cells.
geomFact  a geometry factory 
Inserts a new site into the Subdivision, connecting it to the vertices of the containing triangle (or quadrilateral, if the split point falls on an existing edge).
This method does NOT maintain the Delaunay condition. If desired, this must be checked and enforced by the caller.
This method does NOT check if the inserted vertex falls on an edge. This must be checked by the caller, since this situation may cause erroneous triangulation
v  the vertex to insert 
bool geos::triangulate::quadedge::QuadEdgeSubdivision::isFrameBorderEdge  (  const QuadEdge &  e  )  const 
Tests whether a QuadEdge is an edge on the border of the frame facets and the internal facets. E.g. an edge which does not itself touch a frame vertex, but which touches an edge which does.
e  the edge to test 
true
if the edge is on the border of the frame bool geos::triangulate::quadedge::QuadEdgeSubdivision::isFrameEdge  (  const QuadEdge &  e  )  const 
Tests whether a QuadEdge is an edge incident on a frame triangle vertex.
e  the edge to test 
true
if the edge is connected to the frame triangle bool geos::triangulate::quadedge::QuadEdgeSubdivision::isFrameVertex  (  const Vertex &  v  )  const 
Tests whether a vertex is a vertex of the outer triangle.
v  the vertex to test 
true
if the vertex is an outer triangle vertex bool geos::triangulate::quadedge::QuadEdgeSubdivision::isOnEdge  (  const QuadEdge &  e, 
const geom::Coordinate &  p  
)  const 
Tests whether a Coordinate lies on a QuadEdge, up to a tolerance determined by the subdivision tolerance.
e  a QuadEdge 
p  a point 
true
if the vertex lies on the edge

inline 
Finds a quadedge of a triangle containing a location specified by a geom::Coordinate, if one exists.
p  the Coordinate to locate 
null
if no such triangle exists.QuadEdge* geos::triangulate::quadedge::QuadEdgeSubdivision::locate  (  const geom::Coordinate &  p0, 
const geom::Coordinate &  p1  
) 
Locates the edge between the given vertices, if it exists in the subdivision.
p0  a coordinate 
p1  another coordinate 
null
if no such edge existsQuadEdge* geos::triangulate::quadedge::QuadEdgeSubdivision::locateFromEdge  (  const Vertex &  v, 
const QuadEdge &  startEdge  
)  const 
Locates an edge of a triangle which contains a location specified by a Vertex v
.
The edge returned has the property that either v is on e, or e is an edge of a triangle containing v. The search starts from startEdge and proceeds on the general direction of v.
This locate algorithm relies on the subdivision being Delaunay. For nonDelaunay subdivisions, this may loop for ever.
v  the location to search for 
startEdge  an edge of the subdivision to start searching at 
LocateFailureException  if the location algorithm fails to converge in a reasonable number of iterations. 

virtual 
Creates a new quadedge, recording it in the edges list.
o  
d 
void geos::triangulate::quadedge::QuadEdgeSubdivision::remove  (  QuadEdge &  e  ) 
Deletes a quadedge from the subdivision. Linked quadedges are updated to reflect the deletion.
e  the quadedge to delete 

inline 
Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision.
p_locator  a QuadEdgeLocator 