Class QuadEdgeSubdivision
- java.lang.Object
-
- org.locationtech.jts.triangulate.quadedge.QuadEdgeSubdivision
-
public class QuadEdgeSubdivision extends java.lang.Object
A class that contains theQuadEdge
s representing a planar subdivision that models a triangulation. The subdivision is constructed using the quadedge algebra defined in the classQuadEdge
. All metric calculations are done in theVertex
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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
QuadEdgeSubdivision.TriangleCircumcentreVisitor
A TriangleVisitor which computes and sets the circumcentre as the origin of the dual edges originating in each triangle.private static class
QuadEdgeSubdivision.TriangleCoordinatesVisitor
private static class
QuadEdgeSubdivision.TriangleEdgesListVisitor
private static class
QuadEdgeSubdivision.TriangleVertexListVisitor
-
Field Summary
Fields Modifier and Type Field Description private static double
EDGE_COINCIDENCE_TOL_FACTOR
private double
edgeCoincidenceTolerance
private Envelope
frameEnv
private Vertex[]
frameVertex
private QuadEdgeLocator
locator
private java.util.List
quadEdges
private LineSegment
seg
private QuadEdge
startingEdge
private double
tolerance
private QuadEdge[]
triEdges
The quadedges forming a single triangle.private int
visitedKey
-
Constructor Summary
Constructors Constructor Description QuadEdgeSubdivision(Envelope env, double tolerance)
Creates a new instance of a quad-edge subdivision based on a frame triangle that encloses a supplied bounding box.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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.private void
createFrame(Envelope env)
void
delete(QuadEdge e)
Deletes a quadedge from the subdivision.private QuadEdge[]
fetchTriangleToVisit(QuadEdge edge, java.util.Stack edgeStack, boolean includeFrame, java.util.Set visitedEdges)
Stores the edges for a visited triangle.java.util.Collection
getEdges()
Gets the collection of baseQuadEdge
s (one for every pair of vertices which is connected).Geometry
getEdges(GeometryFactory geomFact)
Gets the geometry for the edges in the subdivision as aMultiLineString
containing 2-point 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 vertex-equality tolerance value used in this subdivisionjava.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 givenQuadEdge
.Geometry
getTriangles(GeometryFactory geomFact)
Gets the geometry for the triangles in a triangulated subdivision as aGeometryCollection
of triangularPolygon
s.java.util.List
getTriangleVertices(boolean includeFrame)
Gets a list of the triangles in the subdivision, specified as an array of the triangleVertex
es.java.util.List
getVertexUniqueEdges(boolean includeFrame)
Gets a collection ofQuadEdge
s whose origin vertices are a unique set which includes all vertices in the subdivision.java.util.Collection
getVertices(boolean includeFrame)
Gets the uniqueVertex
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 ofPolygon
s for the Voronoi cells of this triangulation.Geometry
getVoronoiDiagram(GeometryFactory geomFact)
Gets the cells in the Voronoi diagram for this triangulation.private QuadEdge
initSubdiv()
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 aCoordinate
lies on aQuadEdge
, 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 aCoordinate
, 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 aVertex
, 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 theQuadEdgeLocator
to use for locating containing triangles in this subdivision.void
visitTriangles(TriangleVisitor triVisitor, boolean includeFrame)
Visitors
-
-
-
Field Detail
-
EDGE_COINCIDENCE_TOL_FACTOR
private static final double EDGE_COINCIDENCE_TOL_FACTOR
- See Also:
- Constant Field Values
-
visitedKey
private int visitedKey
-
quadEdges
private java.util.List quadEdges
-
startingEdge
private QuadEdge startingEdge
-
tolerance
private double tolerance
-
edgeCoincidenceTolerance
private double edgeCoincidenceTolerance
-
frameVertex
private Vertex[] frameVertex
-
frameEnv
private Envelope frameEnv
-
locator
private QuadEdgeLocator locator
-
seg
private LineSegment seg
-
triEdges
private QuadEdge[] triEdges
The quadedges forming a single triangle. Only one visitor is allowed to be active at a time, so this is safe.
-
-
Constructor Detail
-
QuadEdgeSubdivision
public QuadEdgeSubdivision(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:
env
- the bounding box to surroundtolerance
- the tolerance value for determining if two sites are equal
-
-
Method Detail
-
getTriangleEdges
public static void getTriangleEdges(QuadEdge startQE, QuadEdge[] triEdge)
Gets the edges for the triangle to the left of the givenQuadEdge
.- Parameters:
startQE
-triEdge
-- Throws:
java.lang.IllegalArgumentException
- if the edges do not form a triangle
-
createFrame
private void createFrame(Envelope env)
-
initSubdiv
private QuadEdge initSubdiv()
-
getTolerance
public double getTolerance()
Gets the vertex-equality tolerance value used in this subdivision- Returns:
- the tolerance value
-
getEnvelope
public Envelope getEnvelope()
Gets the envelope of the Subdivision (including the frame).- Returns:
- the envelope
-
getEdges
public java.util.Collection getEdges()
Gets the collection of baseQuadEdge
s (one for every pair of vertices which is connected).- Returns:
- a collection of QuadEdges
-
setLocator
public void setLocator(QuadEdgeLocator locator)
Sets theQuadEdgeLocator
to use for locating containing triangles in this subdivision.- Parameters:
locator
- a QuadEdgeLocator
-
makeEdge
public QuadEdge makeEdge(Vertex o, Vertex d)
Creates a new quadedge, recording it in the edges list.- Parameters:
o
-d
-- Returns:
- a new quadedge
-
connect
public 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.- Parameters:
a
-b
-- Returns:
- a quadedge
-
delete
public void delete(QuadEdge e)
Deletes a quadedge from the subdivision. Linked quadedges are updated to reflect the deletion.- Parameters:
e
- the quadedge to delete
-
locateFromEdge
public QuadEdge locateFromEdge(Vertex v, QuadEdge startEdge)
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:
v
- the location to search forstartEdge
- an edge of the subdivision to start searching at- Returns:
- a QuadEdge which contains v, or is on the edge of a triangle containing v
- Throws:
LocateFailureException
- if the location algorithm fails to converge in a reasonable number of iterations
-
locate
public QuadEdge locate(Vertex v)
Finds a quadedge of a triangle containing a location specified by aVertex
, if one exists.- Parameters:
v
- the vertex to locate- Returns:
- a quadedge on the edge of a triangle which touches or contains the location or null if no such triangle exists
-
locate
public QuadEdge locate(Coordinate p)
Finds a quadedge of a triangle containing a location specified by aCoordinate
, if one exists.- Parameters:
p
- the Coordinate to locate- Returns:
- a quadedge on the edge of a triangle which touches or contains the location or null if no such triangle exists
-
locate
public QuadEdge locate(Coordinate p0, Coordinate p1)
Locates the edge between the given vertices, if it exists in the subdivision.- Parameters:
p0
- a coordinatep1
- another coordinate- Returns:
- the edge joining the coordinates, if present or null if no such edge exists
-
insertSite
public 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).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:
v
- the vertex to insert- Returns:
- a new quad edge terminating in v
-
isFrameEdge
public boolean isFrameEdge(QuadEdge e)
Tests whether a QuadEdge is an edge incident on a frame triangle vertex.- Parameters:
e
- the edge to test- Returns:
- true if the edge is connected to the frame triangle
-
isFrameBorderEdge
public boolean isFrameBorderEdge(QuadEdge e)
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:
e
- the edge to test- Returns:
- true if the edge is on the border of the frame
-
isFrameVertex
public boolean isFrameVertex(Vertex v)
Tests whether a vertex is a vertex of the outer triangle.- Parameters:
v
- the vertex to test- Returns:
- true if the vertex is an outer triangle vertex
-
isOnEdge
public boolean isOnEdge(QuadEdge e, Coordinate p)
Tests whether aCoordinate
lies on aQuadEdge
, up to a tolerance determined by the subdivision tolerance.- Parameters:
e
- a QuadEdgep
- a point- Returns:
- true if the vertex lies on the edge
-
isVertexOfEdge
public boolean isVertexOfEdge(QuadEdge e, Vertex v)
Tests whether aVertex
is the start or end vertex of aQuadEdge
, up to the subdivision tolerance distance.- Parameters:
e
-v
-- Returns:
- true if the vertex is a endpoint of the edge
-
getVertices
public java.util.Collection getVertices(boolean includeFrame)
Gets the uniqueVertex
es in the subdivision, including the frame vertices if desired.- Parameters:
includeFrame
- true if the frame vertices should be included- Returns:
- a collection of the subdivision vertices
- See Also:
getVertexUniqueEdges(boolean)
-
getVertexUniqueEdges
public java.util.List getVertexUniqueEdges(boolean includeFrame)
Gets a collection ofQuadEdge
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.- Parameters:
includeFrame
- true if the frame vertices should be included- Returns:
- a collection of QuadEdge with the vertices of the subdivision as their origins
-
getPrimaryEdges
public java.util.List getPrimaryEdges(boolean includeFrame)
Gets all primary quadedges in the subdivision. A primary edge is aQuadEdge
which occupies the 0'th position in its array of associated quadedges. These provide the unique geometric edges of the triangulation.- Parameters:
includeFrame
- true if the frame edges are to be included- Returns:
- a List of QuadEdges
-
visitTriangles
public void visitTriangles(TriangleVisitor triVisitor, boolean includeFrame)
Visitors
-
fetchTriangleToVisit
private QuadEdge[] fetchTriangleToVisit(QuadEdge edge, java.util.Stack edgeStack, boolean includeFrame, java.util.Set visitedEdges)
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 or null if the triangle should not be visited (for instance, if it is outer)
-
getTriangleEdges
public 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.- Parameters:
includeFrame
- true if the frame triangles should be included- Returns:
- a List of QuadEdge[3] arrays
-
getTriangleVertices
public java.util.List getTriangleVertices(boolean includeFrame)
Gets a list of the triangles in the subdivision, specified as an array of the triangleVertex
es.- Parameters:
includeFrame
- true if the frame triangles should be included- Returns:
- a List of Vertex[3] arrays
-
getTriangleCoordinates
public java.util.List getTriangleCoordinates(boolean includeFrame)
Gets the coordinates for each triangle in the subdivision as an array.- Parameters:
includeFrame
- true if the frame triangles should be included- Returns:
- a list of Coordinate[4] representing each triangle
-
getEdges
public Geometry getEdges(GeometryFactory geomFact)
Gets the geometry for the edges in the subdivision as aMultiLineString
containing 2-point lines.- Parameters:
geomFact
- the GeometryFactory to use- Returns:
- a MultiLineString
-
getTriangles
public Geometry getTriangles(GeometryFactory geomFact)
Gets the geometry for the triangles in a triangulated subdivision as aGeometryCollection
of triangularPolygon
s.- Parameters:
geomFact
- the GeometryFactory to use- Returns:
- a GeometryCollection of triangular Polygons
-
getVoronoiDiagram
public Geometry getVoronoiDiagram(GeometryFactory geomFact)
Gets the cells in the Voronoi diagram for this triangulation. The cells are returned as aGeometryCollection
ofPolygon
sThe 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:
geomFact
- a geometry factory- Returns:
- a GeometryCollection of Polygons
-
getVoronoiCellPolygons
public java.util.List getVoronoiCellPolygons(GeometryFactory geomFact)
Gets a List ofPolygon
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.- Parameters:
geomFact
- a geometry factory- Returns:
- a List of Polygons
-
getVoronoiCellPolygon
public Polygon getVoronoiCellPolygon(QuadEdge qe, 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:
qe
- a quadedge originating at the cell sitegeomFact
- a factory for building the polygon- Returns:
- a polygon indicating the cell extent
-
-