GEOS  3.9.1dev
Public Types | Public Member Functions | Static Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
geos::triangulate::quadedge::QuadEdgeSubdivision Class Reference

A class that contains the QuadEdges representing a planar subdivision that models a triangulation. More...

#include <QuadEdgeSubdivision.h>

Collaboration diagram for geos::triangulate::quadedge::QuadEdgeSubdivision:
[legend]

Public Types

typedef std::vector< QuadEdge * > QuadEdgeList
 

Public Member Functions

 QuadEdgeSubdivision (const geom::Envelope &env, double tolerance)
 Creates a new instance of a quad-edge subdivision based on a frame triangle that encloses a supplied bounding box. A new super-bounding box that contains the triangle is computed and stored. More...
 
virtual ~QuadEdgeSubdivision ()=default
 
double getTolerance () const
 Gets the vertex-equality tolerance value used in this subdivision. More...
 
const geom::EnvelopegetEnvelope () 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 QuadEdgemakeEdge (const Vertex &o, const Vertex &d)
 Creates a new quadedge, recording it in the edges list. More...
 
virtual QuadEdgeconnect (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...
 
QuadEdgelocateFromEdge (const Vertex &v, const QuadEdge &startEdge) const
 Locates an edge of a triangle which contains a location specified by a Vertex v. More...
 
QuadEdgelocate (const Vertex &v) const
 Finds a quadedge of a triangle containing a location specified by a Vertex, if one exists. More...
 
QuadEdgelocate (const geom::Coordinate &p)
 Finds a quadedge of a triangle containing a location specified by a geom::Coordinate, if one exists. More...
 
QuadEdgelocate (const geom::Coordinate &p0, const geom::Coordinate &p1)
 Locates the edge between the given vertices, if it exists in the subdivision. More...
 
QuadEdgeinsertSite (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< QuadEdgeListgetPrimaryEdges (bool includeFrame)
 Gets all primary quadedges in the subdivision. More...
 
void visitTriangles (TriangleVisitor *triVisitor, bool includeFrame)
 
std::unique_ptr< geom::MultiLineStringgetEdges (const geom::GeometryFactory &geomFact)
 Gets the geometry for the edges in the subdivision as a MultiLineString containing 2-point lines. More...
 
std::unique_ptr< geom::GeometryCollectiongetTriangles (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::GeometryCollectiongetVoronoiDiagram (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::MultiLineStringgetVoronoiDiagramEdges (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::QuadEdgeListgetVertexUniqueEdges (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::GeometrygetVoronoiCellPolygon (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::GeometrygetVoronoiCellEdge (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...
 

Private Types

typedef std::stack< QuadEdge * > QuadEdgeStack
 
typedef std::vector< std::unique_ptr< geom::CoordinateSequence > > TriList
 

Private Member Functions

virtual void createFrame (const geom::Envelope &env)
 
virtual void initSubdiv ()
 
void prepareVisit ()
 Resets the visited flag of each QuadEdge prior to iteration, if necessary. More...
 
QuadEdge ** fetchTriangleToVisit (QuadEdge *edge, QuadEdgeStack &edgeStack, bool includeFrame)
 Stores the edges for a visited triangle. Also pushes sym (neighbour) edges on stack to visit later. More...
 
void getTriangleCoordinates (TriList *triList, bool includeFrame)
 Gets the coordinates for each triangle in the subdivision as an array. More...
 

Private Attributes

std::deque< QuadEdgeQuartetquadEdges
 
std::array< QuadEdge *, 3 > startingEdges
 
double tolerance
 
double edgeCoincidenceTolerance
 
std::array< Vertex, 3 > frameVertex
 
geom::Envelope frameEnv
 
std::unique_ptr< QuadEdgeLocatorlocator
 
bool visit_state_clean
 
QuadEdgetriEdges [3]
 The quadedges forming a single triangle. More...
 

Detailed Description

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

Author
JTS: David Skea
JTS: Martin Davis
Benjamin Campbell

Definition at line 80 of file QuadEdgeSubdivision.h.

Member Typedef Documentation

Definition at line 82 of file QuadEdgeSubdivision.h.

Definition at line 355 of file QuadEdgeSubdivision.h.

Definition at line 356 of file QuadEdgeSubdivision.h.

Constructor & Destructor Documentation

geos::triangulate::quadedge::QuadEdgeSubdivision::QuadEdgeSubdivision ( const geom::Envelope env,
double  tolerance 
)

Creates a new instance of a quad-edge subdivision based on a frame triangle that encloses a supplied bounding box. A new super-bounding box that contains the triangle is computed and stored.

Parameters
envthe bouding box to surround
tolerancethe tolerance value for determining if two sites are equal
virtual geos::triangulate::quadedge::QuadEdgeSubdivision::~QuadEdgeSubdivision ( )
virtualdefault

Member Function Documentation

virtual QuadEdge& geos::triangulate::quadedge::QuadEdgeSubdivision::connect ( QuadEdge a,
QuadEdge b 
)
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.

Parameters
a
b
Returns
virtual void geos::triangulate::quadedge::QuadEdgeSubdivision::createFrame ( const geom::Envelope env)
privatevirtual
QuadEdge** geos::triangulate::quadedge::QuadEdgeSubdivision::fetchTriangleToVisit ( QuadEdge edge,
QuadEdgeStack edgeStack,
bool  includeFrame 
)
private

Stores the edges for a visited triangle. Also pushes sym (neighbour) edges on stack to visit later.

Parameters
edge
edgeStack
includeFrame
Returns
the visited triangle edges
null if the triangle should not be visited (for instance, if it is outer)
std::deque<QuadEdgeQuartet>& geos::triangulate::quadedge::QuadEdgeSubdivision::getEdges ( )
inline

Gets the collection of base QuadEdges (one for every pair of vertices which is connected).

Returns
a QuadEdgeList

Definition at line 157 of file QuadEdgeSubdivision.h.

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 2-point lines.

Parameters
geomFactthe GeometryFactory to use
Returns
a MultiLineString
Note
The caller takes ownership of the returned object.
const geom::Envelope& geos::triangulate::quadedge::QuadEdgeSubdivision::getEnvelope ( ) const
inline

Gets the envelope of the Subdivision (including the frame).

Returns
the envelope

Definition at line 145 of file QuadEdgeSubdivision.h.

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.

Parameters
includeFrametrue if the frame edges are to be included
Returns
a List of QuadEdges. The caller takes ownership of the returned QuadEdgeList but not the items it contains.
double geos::triangulate::quadedge::QuadEdgeSubdivision::getTolerance ( ) const
inline

Gets the vertex-equality tolerance value used in this subdivision.

Returns
the tolerance value

Definition at line 134 of file QuadEdgeSubdivision.h.

void geos::triangulate::quadedge::QuadEdgeSubdivision::getTriangleCoordinates ( TriList triList,
bool  includeFrame 
)
private

Gets the coordinates for each triangle in the subdivision as an array.

Parameters
includeFrametrue if the frame triangles should be included
triLista list of Coordinate[4] representing each triangle
static void geos::triangulate::quadedge::QuadEdgeSubdivision::getTriangleEdges ( const QuadEdge startQE,
const QuadEdge triEdge[3] 
)
static

Gets the edges for the triangle to the left of the given QuadEdge.

Parameters
startQE
triEdge
Exceptions
IllegalArgumentExceptionif 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.

Parameters
geomFactthe GeometryFactory to use
Returns
a GeometryCollection of triangular polygons.
Note
The caller takes ownership of the returned object.
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.

Parameters
includeFrametrue if the frame vertices should be included
Returns
a collection of QuadEdge with the vertices of the subdivision as their origins
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.

Parameters
qea quadedge originating at the cell site
geomFacta factory for building the polygon
Returns
a polygon indicating the cell extent
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.

Parameters
geomFacta geometry factory
Returns
a List of LineString
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.

Parameters
qea quadedge originating at the cell site
geomFacta factory for building the polygon
Returns
a polygon indicating the cell extent
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.

Parameters
geomFacta geometry factory
Returns
a List of Polygons
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.

Parameters
geomFacta geometry factory
Returns
a GeometryCollection of Polygons
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.

Parameters
geomFacta geometry factory
Returns
a MultiLineString
virtual void geos::triangulate::quadedge::QuadEdgeSubdivision::initSubdiv ( )
privatevirtual
QuadEdge& geos::triangulate::quadedge::QuadEdgeSubdivision::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).

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

Parameters
vthe vertex to insert
Returns
a new quad edge terminating in v
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.

Parameters
ethe edge to test
Returns
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.

Parameters
ethe edge to test
Returns
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.

Parameters
vthe vertex to test
Returns
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.

Parameters
ea QuadEdge
pa point
Returns
true if the vertex lies on the edge
bool geos::triangulate::quadedge::QuadEdgeSubdivision::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.

Parameters
e
v
Returns
true if the vertex is a endpoint of the edge
QuadEdge* geos::triangulate::quadedge::QuadEdgeSubdivision::locate ( const Vertex v) const
inline

Finds a quadedge of a triangle containing a location specified by a Vertex, if one exists.

Parameters
vthe vertex to locate
Returns
a QuadEdge on the edge of a triangle which touches or contains the location
null if no such triangle exists.
Note
The returned pointer should not be freed be the caller.

Definition at line 237 of file QuadEdgeSubdivision.h.

QuadEdge* geos::triangulate::quadedge::QuadEdgeSubdivision::locate ( const geom::Coordinate p)
inline

Finds a quadedge of a triangle containing a location specified by a geom::Coordinate, if one exists.

Parameters
pthe Coordinate to locate
Returns
a QuadEdge on the edge of a triangle which touches or contains the location
null if no such triangle exists.
Note
The returned pointer should not be freed be the caller.

Definition at line 253 of file QuadEdgeSubdivision.h.

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.

Parameters
p0a coordinate
p1another coordinate
Returns
the edge joining the coordinates, if present
null if no such edge exists
Note
the caller should not free the returned pointer
QuadEdge* 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 non-Delaunay subdivisions, this may loop for ever.

Parameters
vthe location to search for
startEdgean edge of the subdivision to start searching at
Returns
a QuadEdge which contains v, or is on the edge of a triangle containing v
Exceptions
LocateFailureExceptionif the location algorithm fails to converge in a reasonable number of iterations.
Note
The returned pointer should not be freed be the caller.
virtual QuadEdge& geos::triangulate::quadedge::QuadEdgeSubdivision::makeEdge ( const Vertex o,
const Vertex d 
)
virtual

Creates a new quadedge, recording it in the edges list.

Parameters
o
d
Returns
void geos::triangulate::quadedge::QuadEdgeSubdivision::prepareVisit ( )
private

Resets the visited flag of each QuadEdge prior to iteration, if necessary.

void geos::triangulate::quadedge::QuadEdgeSubdivision::remove ( QuadEdge e)

Deletes a quadedge from the subdivision. Linked quadedges are updated to reflect the deletion.

Parameters
ethe quadedge to delete
void geos::triangulate::quadedge::QuadEdgeSubdivision::setLocator ( std::unique_ptr< QuadEdgeLocator p_locator)
inline

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

Parameters
p_locatora QuadEdgeLocator

Definition at line 170 of file QuadEdgeSubdivision.h.

void geos::triangulate::quadedge::QuadEdgeSubdivision::visitTriangles ( TriangleVisitor triVisitor,
bool  includeFrame 
)

Member Data Documentation

double geos::triangulate::quadedge::QuadEdgeSubdivision::edgeCoincidenceTolerance
private

Definition at line 103 of file QuadEdgeSubdivision.h.

geom::Envelope geos::triangulate::quadedge::QuadEdgeSubdivision::frameEnv
private

Definition at line 105 of file QuadEdgeSubdivision.h.

std::array<Vertex, 3> geos::triangulate::quadedge::QuadEdgeSubdivision::frameVertex
private

Definition at line 104 of file QuadEdgeSubdivision.h.

std::unique_ptr<QuadEdgeLocator> geos::triangulate::quadedge::QuadEdgeSubdivision::locator
private

Definition at line 106 of file QuadEdgeSubdivision.h.

std::deque<QuadEdgeQuartet> geos::triangulate::quadedge::QuadEdgeSubdivision::quadEdges
private

Use a deque to ensure QuadEdge pointers are stable. Note that it is NOT safe to erase entries from the deque.

Definition at line 100 of file QuadEdgeSubdivision.h.

std::array<QuadEdge*, 3> geos::triangulate::quadedge::QuadEdgeSubdivision::startingEdges
private

Definition at line 101 of file QuadEdgeSubdivision.h.

double geos::triangulate::quadedge::QuadEdgeSubdivision::tolerance
private

Definition at line 102 of file QuadEdgeSubdivision.h.

QuadEdge* geos::triangulate::quadedge::QuadEdgeSubdivision::triEdges[3]
private

The quadedges forming a single triangle.

Only one visitor is allowed to be active at a time, so this is safe.

Definition at line 363 of file QuadEdgeSubdivision.h.

bool geos::triangulate::quadedge::QuadEdgeSubdivision::visit_state_clean
private

Definition at line 107 of file QuadEdgeSubdivision.h.


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