
JTS Topology Suite version 1.12  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object com.vividsolutions.jts.triangulate.quadedge.QuadEdgeSubdivision
public class QuadEdgeSubdivision
A class that contains the QuadEdge
s 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 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 Summary  

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

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. 
java.util.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). 
java.util.List 
getPrimaryEdges(boolean includeFrame)
Gets all primary quadedges in the subdivision. 
double 
getTolerance()
Gets the vertexequality tolerance value used in this subdivision 
java.util.List 
getTriangleCoordinates(boolean includeFrame)
Gets the coordinates for each triangle in the subdivision as an array. 
java.util.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. 
java.util.List 
getTriangleVertices(boolean includeFrame)
Gets a list of the triangles in the subdivision, specified as an array of the triangle Vertex es. 
java.util.List 
getVertexUniqueEdges(boolean includeFrame)
Gets a collection of QuadEdge s whose origin
vertices are a unique set which includes
all vertices in the subdivision. 
java.util.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. 
java.util.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)
Tests whether a Vertex is the start or end vertex of a
QuadEdge , up to the subdivision tolerance distance. 
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 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Constructor Detail 

public QuadEdgeSubdivision(Envelope env, double tolerance)
env
 the bouding box to surroundtolerance
 the tolerance value for determining if two sites are equalMethod Detail 

public static void getTriangleEdges(QuadEdge startQE, QuadEdge[] triEdge)
QuadEdge
.
startQE
 triEdge

java.lang.IllegalArgumentException
 if the edges do not form a trianglepublic double getTolerance()
public Envelope getEnvelope()
public java.util.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 at
LocateFailureException
 if the location algorithm fails to converge in a reasonable
number of iterationspublic QuadEdge locate(Vertex v)
Vertex
, if one exists.
x
 the vertex to locate
public QuadEdge locate(Coordinate p)
Coordinate
, if one exists.
p
 the Coordinate to locate
public QuadEdge locate(Coordinate p0, Coordinate p1)
p0
 a coordinatep1
 another coordinate
public 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 insert
public boolean isFrameEdge(QuadEdge e)
e
 the edge to test
public boolean isFrameBorderEdge(QuadEdge e)
e
 the edge to test
public boolean isFrameVertex(Vertex v)
v
 the vertex to test
public boolean isOnEdge(QuadEdge e, Coordinate p)
Coordinate
lies on a QuadEdge
, up to a
tolerance determined by the subdivision tolerance.
e
 a QuadEdgep
 a point
public 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 java.util.Collection getVertices(boolean includeFrame)
Vertex
es in the subdivision,
including the frame vertices if desired.
includeFrame
 true if the frame vertices should be included
getVertexUniqueEdges(boolean)
public java.util.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 {@link #getVertices) and then locating quadedges attached to them.
includeFrame
 true if the frame vertices should be included
public java.util.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 included
public void visitTriangles(TriangleVisitor triVisitor, boolean includeFrame)
public java.util.List getTriangleEdges(boolean includeFrame)
includeFrame
 true if the frame triangles should be included
public java.util.List getTriangleVertices(boolean includeFrame)
Vertex
es.
includeFrame
 true if the frame triangles should be included
public java.util.List getTriangleCoordinates(boolean includeFrame)
includeFrame
 true if the frame triangles should be included
public Geometry getEdges(GeometryFactory geomFact)
MultiLineString
containing 2point lines.
geomFact
 the GeometryFactory to use
public Geometry getTriangles(GeometryFactory geomFact)
GeometryCollection
of triangular Polygon
s.
geomFact
 the GeometryFactory to use
public Geometry getVoronoiDiagram(GeometryFactory geomFact)
GeometryCollection
of Polygon
s
The userData of each polygon is set to be the {@link Coordinate) of the cell site. This allows easily associating external data associated with the sites to the cells.
geomFact
 a geometry factory
public java.util.List getVoronoiCellPolygons(GeometryFactory geomFact)
Polygon
s for the Voronoi cells
of this triangulation.
The userData of each polygon is set to be the {@link Coordinate) of the cell site. This allows easily associating external data associated with the sites to the cells.
geomFact
 a geometry factory
public Polygon getVoronoiCellPolygon(QuadEdge qe, GeometryFactory geomFact)
The userData of the polygon is set to be the {@link 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 polygon

JTS Topology Suite version 1.12  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 