GEOS  3.4.2
Public Types | Public Member Functions | Static Public Member Functions
geos::triangulate::quadedge::QuadEdgeSubdivision Class Reference

#include <QuadEdgeSubdivision.h>

List of all members.

Public Types

typedef std::list< QuadEdge * > QuadEdgeList

Public Member Functions

 QuadEdgeSubdivision (const geom::Envelope &env, double tolerance)
double getTolerance () const
const geom::EnvelopegetEnvelope () const
const QuadEdgeList & getEdges () const
void setLocator (std::auto_ptr< QuadEdgeLocator > locator)
virtual QuadEdgemakeEdge (const Vertex &o, const Vertex &d)
virtual QuadEdgeconnect (QuadEdge &a, QuadEdge &b)
void remove (QuadEdge &e)
QuadEdgelocateFromEdge (const Vertex &v, const QuadEdge &startEdge) const
QuadEdgelocate (const Vertex &v) const
QuadEdgelocate (const geom::Coordinate &p)
QuadEdgelocate (const geom::Coordinate &p0, const geom::Coordinate &p1)
QuadEdgeinsertSite (const Vertex &v)
bool isFrameEdge (const QuadEdge &e) const
bool isFrameBorderEdge (const QuadEdge &e) const
bool isFrameVertex (const Vertex &v) const
bool isOnEdge (const QuadEdge &e, const geom::Coordinate &p) const
bool isVertexOfEdge (const QuadEdge &e, const Vertex &v) const
std::auto_ptr< QuadEdgeList > getPrimaryEdges (bool includeFrame)
void visitTriangles (TriangleVisitor *triVisitor, bool includeFrame)
std::auto_ptr
< geom::MultiLineString
getEdges (const geom::GeometryFactory &geomFact)
std::auto_ptr
< geom::GeometryCollection
getTriangles (const geom::GeometryFactory &geomFact)

Static Public Member Functions

static void getTriangleEdges (const QuadEdge &startQE, const QuadEdge *triEdge[3])

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

Constructor & Destructor Documentation

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

Member Function Documentation

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:
const QuadEdgeList& geos::triangulate::quadedge::QuadEdgeSubdivision::getEdges ( ) const [inline]

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

Returns:
a QuadEdgeList

Gets the geometry for the edges in the subdivision as a MultiLineString containing 2-point lines.

Parameters:
geomFactthe GeometryFactory to use
Returns:
a MultiLineString. The caller takes ownership of the returned object.

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

Returns:
the envelope
std::auto_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.

Gets the vertex-equality tolerance value used in this subdivision

Returns:
the tolerance value
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

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. The caller takes ownership of the returned object.

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

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

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

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

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

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

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

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

Finds a quadedge of a triangle containing a location specified by a 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. The returned pointer should not be freed be the caller.

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
the caller should not free the returned pointer

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

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

Parameters:
ethe quadedge to delete

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

Parameters:
locatora QuadEdgeLocator

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