public class QuadEdgeSubdivision extends Object
QuadEdge
s 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.
Constructor and Description 

QuadEdgeSubdivision(Envelope env,
double tolerance)
Creates a new instance of a quadedge subdivision based on a frame triangle
that encloses a supplied bounding box.

Modifier and Type  Method and Description 

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.

void 
delete(QuadEdge e)
Deletes a quadedge from the subdivision.

Collection 
getEdges()
Gets the collection of base
QuadEdge s (one for every pair of
vertices which is connected). 
Geometry 
getEdges(GeometryFactory geomFact)
Gets the geometry for the edges in the subdivision as a
MultiLineString
containing 2point lines. 
Envelope 
getEnvelope()
Gets the envelope of the Subdivision (including the frame).

List 
getPrimaryEdges(boolean includeFrame)
Gets all primary quadedges in the subdivision.

double 
getTolerance()
Gets the vertexequality tolerance value
used in this subdivision

List 
getTriangleCoordinates(boolean includeFrame)
Gets the coordinates for each triangle in the subdivision as an array.

List 
getTriangleEdges(boolean includeFrame)
Gets a list of the triangles
in the subdivision, specified as
an array of the primary quadedges around the triangle.

static void 
getTriangleEdges(QuadEdge startQE,
QuadEdge[] triEdge)
Gets the edges for the triangle to the left of the given
QuadEdge . 
Geometry 
getTriangles(GeometryFactory geomFact)
Gets the geometry for the triangles in a triangulated subdivision as a
GeometryCollection
of triangular Polygon s. 
List 
getTriangleVertices(boolean includeFrame)
Gets a list of the triangles in the subdivision,
specified as an array of the triangle
Vertex es. 
List 
getVertexUniqueEdges(boolean includeFrame)
Gets a collection of
QuadEdge s whose origin
vertices are a unique set which includes
all vertices in the subdivision. 
Collection 
getVertices(boolean includeFrame)
Gets the unique
Vertex es in the subdivision,
including the frame vertices if desired. 
Polygon 
getVoronoiCellPolygon(QuadEdge qe,
GeometryFactory geomFact)
Gets the Voronoi cell around a site specified
by the origin of a QuadEdge.

List 
getVoronoiCellPolygons(GeometryFactory geomFact)
Gets a List of
Polygon s for the Voronoi cells
of this triangulation. 
Geometry 
getVoronoiDiagram(GeometryFactory geomFact)
Gets the cells in the Voronoi diagram for this triangulation.

QuadEdge 
insertSite(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).

boolean 
isFrameBorderEdge(QuadEdge e)
Tests whether a QuadEdge is an edge on the border of the frame facets and
the internal facets.

boolean 
isFrameEdge(QuadEdge e)
Tests whether a QuadEdge is an edge incident on a frame triangle vertex.

boolean 
isFrameVertex(Vertex v)
Tests whether a vertex is a vertex of the outer triangle.

boolean 
isOnEdge(QuadEdge e,
Coordinate p)
Tests whether a
Coordinate lies on a QuadEdge , up to a
tolerance determined by the subdivision tolerance. 
boolean 
isVertexOfEdge(QuadEdge e,
Vertex v)

QuadEdge 
locate(Coordinate p)
Finds a quadedge of a triangle containing a location
specified by a
Coordinate , if one exists. 
QuadEdge 
locate(Coordinate p0,
Coordinate p1)
Locates the edge between the given vertices, if it exists in the
subdivision.

QuadEdge 
locate(Vertex v)
Finds a quadedge of a triangle containing a location
specified by a
Vertex , if one exists. 
QuadEdge 
locateFromEdge(Vertex v,
QuadEdge startEdge)
Locates an edge of a triangle which contains a location
specified by a Vertex v.

QuadEdge 
makeEdge(Vertex o,
Vertex d)
Creates a new quadedge, recording it in the edges list.

void 
setLocator(QuadEdgeLocator locator)
Sets the
QuadEdgeLocator to use for locating containing triangles
in this subdivision. 
void 
visitTriangles(TriangleVisitor triVisitor,
boolean includeFrame)
Visitors

public QuadEdgeSubdivision(Envelope env, double tolerance)
env
 the bounding box to surroundtolerance
 the tolerance value for determining if two sites are equalpublic static void getTriangleEdges(QuadEdge startQE, QuadEdge[] triEdge)
QuadEdge
.startQE
 triEdge
 IllegalArgumentException
 if the edges do not form a trianglepublic double getTolerance()
public Envelope getEnvelope()
public Collection getEdges()
QuadEdge
s (one for every pair of
vertices which is connected).public void setLocator(QuadEdgeLocator locator)
QuadEdgeLocator
to use for locating containing triangles
in this subdivision.locator
 a QuadEdgeLocatorpublic QuadEdge makeEdge(Vertex o, Vertex d)
o
 d
 public QuadEdge connect(QuadEdge a, QuadEdge b)
a
 b
 public void delete(QuadEdge e)
e
 the quadedge to deletepublic QuadEdge locateFromEdge(Vertex v, QuadEdge startEdge)
This locate algorithm relies on the subdivision being Delaunay. For nonDelaunay subdivisions, this may loop for ever.
v
 the location to search forstartEdge
 an edge of the subdivision to start searching atLocateFailureException
 if the location algorithm fails to converge in a reasonable
number of iterationspublic QuadEdge locate(Vertex v)
Vertex
, if one exists.v
 the vertex to locatepublic QuadEdge locate(Coordinate p)
Coordinate
, if one exists.p
 the Coordinate to locatepublic QuadEdge locate(Coordinate p0, Coordinate p1)
p0
 a coordinatep1
 another coordinatepublic QuadEdge insertSite(Vertex v)
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 insertpublic boolean isFrameEdge(QuadEdge e)
e
 the edge to testpublic boolean isFrameBorderEdge(QuadEdge e)
e
 the edge to testpublic boolean isFrameVertex(Vertex v)
v
 the vertex to testpublic boolean isOnEdge(QuadEdge e, Coordinate p)
Coordinate
lies on a QuadEdge
, up to a
tolerance determined by the subdivision tolerance.e
 a QuadEdgep
 a pointpublic boolean isVertexOfEdge(QuadEdge e, Vertex v)
Vertex
is the start or end vertex of a
QuadEdge
, up to the subdivision tolerance distance.e
 v
 public Collection getVertices(boolean includeFrame)
Vertex
es in the subdivision,
including the frame vertices if desired.includeFrame
 true if the frame vertices should be includedgetVertexUniqueEdges(boolean)
public List getVertexUniqueEdges(boolean includeFrame)
QuadEdge
s 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(boolean)
and then locating
quadedges attached to them.
includeFrame
 true if the frame vertices should be includedpublic List getPrimaryEdges(boolean includeFrame)
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 includedpublic void visitTriangles(TriangleVisitor triVisitor, boolean includeFrame)
public List getTriangleEdges(boolean includeFrame)
includeFrame
 true if the frame triangles should be includedpublic List getTriangleVertices(boolean includeFrame)
Vertex
es.includeFrame
 true if the frame triangles should be includedpublic List getTriangleCoordinates(boolean includeFrame)
includeFrame
 true if the frame triangles should be includedpublic Geometry getEdges(GeometryFactory geomFact)
MultiLineString
containing 2point lines.geomFact
 the GeometryFactory to usepublic Geometry getTriangles(GeometryFactory geomFact)
GeometryCollection
of triangular Polygon
s.geomFact
 the GeometryFactory to usepublic Geometry getVoronoiDiagram(GeometryFactory geomFact)
GeometryCollection
of Polygon
s
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 factorypublic List getVoronoiCellPolygons(GeometryFactory geomFact)
Polygon
s 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 factorypublic Polygon getVoronoiCellPolygon(QuadEdge qe, GeometryFactory geomFact)
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 sitegeomFact
 a factory for building the polygonCopyright © 2020. All rights reserved.