Class ConformingDelaunayTriangulator
- java.lang.Object
-
- org.locationtech.jts.triangulate.ConformingDelaunayTriangulator
-
public class ConformingDelaunayTriangulator extends java.lang.Object
Computes a Conforming Delaunay Triangulation over a set of sites and a set of linear constraints.A conforming Delaunay triangulation is a true Delaunay triangulation. In it each constraint segment is present as a union of one or more triangulation edges. Constraint segments may be subdivided into two or more triangulation edges by the insertion of additional sites. The additional sites are called Steiner points, and are necessary to allow the segments to be faithfully reflected in the triangulation while maintaining the Delaunay property. Another way of stating this is that in a conforming Delaunay triangulation every constraint segment will be the union of a subset of the triangulation edges (up to tolerance).
A Conforming Delaunay triangulation is distinct from a Constrained Delaunay triangulation. A Constrained Delaunay triangulation is not necessarily fully Delaunay, and it contains the constraint segments exactly as edges of the triangulation.
A typical usage pattern for the triangulator is:
ConformingDelaunayTriangulator cdt = new ConformingDelaunayTriangulator(sites, tolerance); // optional cdt.setSplitPointFinder(splitPointFinder); cdt.setVertexFactory(vertexFactory); cdt.setConstraints(segments, new ArrayList(vertexMap.values())); cdt.formInitialDelaunay(); cdt.enforceConstraints(); subdiv = cdt.getSubdivision();
-
-
Field Summary
Fields Modifier and Type Field Description private Envelope
computeAreaEnv
private Geometry
convexHull
private IncrementalDelaunayTriangulator
incDel
private java.util.List
initialVertices
private KdTree
kdt
private static int
MAX_SPLIT_ITER
private java.util.List
segments
private java.util.List
segVertices
private ConstraintSplitPointFinder
splitFinder
private Coordinate
splitPt
private QuadEdgeSubdivision
subdiv
private double
tolerance
private ConstraintVertexFactory
vertexFactory
-
Constructor Summary
Constructors Constructor Description ConformingDelaunayTriangulator(java.util.Collection initialVertices, double tolerance)
Creates a Conforming Delaunay Triangulation based on the given unconstrained initial vertices.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
addConstraintVertices()
private void
computeBoundingBox()
private void
computeConvexHull()
private static Envelope
computeVertexEnvelope(java.util.Collection vertices)
private ConstraintVertex
createVertex(Coordinate p)
private ConstraintVertex
createVertex(Coordinate p, Segment seg)
Creates a vertex on a constraint segmentvoid
enforceConstraints()
Enforces the supplied constraints into the triangulation.private int
enforceGabriel(java.util.Collection segsToInsert)
private Coordinate
findNonGabrielPoint(Segment seg)
Given a set of points stored in the kd-tree and a line segment defined by two points in this set, finds aCoordinate
in the circumcircle of the line segment, if one exists.void
formInitialDelaunay()
Computes the Delaunay triangulation of the initial sites.java.util.Collection
getConstraintSegments()
Gets theSegment
s which represent the constraints.Geometry
getConvexHull()
Gets the convex hull of all the sites in the triangulation, including constraint vertices.java.util.List
getInitialVertices()
Gets the sites (vertices) used to initialize the triangulation.KdTree
getKDT()
Gets theKdTree
which contains the vertices of the triangulation.private Coordinate[]
getPointArray()
QuadEdgeSubdivision
getSubdivision()
Gets theQuadEdgeSubdivision
which represents the triangulation.double
getTolerance()
Gets the tolerance value used to construct the triangulation.ConstraintVertexFactory
getVertexFactory()
Gets the ConstraintVertexFactory used to create new constraint vertices at split points.void
insertSite(Coordinate p)
Inserts a site into the triangulation, maintaining the conformal Delaunay property.private ConstraintVertex
insertSite(ConstraintVertex v)
private void
insertSites(java.util.Collection vertices)
Inserts all sites in a collectionvoid
setConstraints(java.util.List segments, java.util.List segVertices)
Sets the constraints to be conformed to by the computed triangulation.void
setSplitPointFinder(ConstraintSplitPointFinder splitFinder)
Sets theConstraintSplitPointFinder
to be used during constraint enforcement.void
setVertexFactory(ConstraintVertexFactory vertexFactory)
Sets a customConstraintVertexFactory
to be used to allow vertices carrying extra information to be created.
-
-
-
Field Detail
-
initialVertices
private java.util.List initialVertices
-
segVertices
private java.util.List segVertices
-
segments
private java.util.List segments
-
subdiv
private QuadEdgeSubdivision subdiv
-
incDel
private IncrementalDelaunayTriangulator incDel
-
convexHull
private Geometry convexHull
-
splitFinder
private ConstraintSplitPointFinder splitFinder
-
kdt
private KdTree kdt
-
vertexFactory
private ConstraintVertexFactory vertexFactory
-
computeAreaEnv
private Envelope computeAreaEnv
-
splitPt
private Coordinate splitPt
-
tolerance
private double tolerance
-
MAX_SPLIT_ITER
private static final int MAX_SPLIT_ITER
- See Also:
- Constant Field Values
-
-
Constructor Detail
-
ConformingDelaunayTriangulator
public ConformingDelaunayTriangulator(java.util.Collection initialVertices, double tolerance)
Creates a Conforming Delaunay Triangulation based on the given unconstrained initial vertices. The initial vertex set should not contain any vertices which appear in the constraint set.- Parameters:
initialVertices
- a collection ofConstraintVertex
tolerance
- the distance tolerance below which points are considered identical
-
-
Method Detail
-
computeVertexEnvelope
private static Envelope computeVertexEnvelope(java.util.Collection vertices)
-
setConstraints
public void setConstraints(java.util.List segments, java.util.List segVertices)
Sets the constraints to be conformed to by the computed triangulation. The constraints must not contain duplicate segments (up to orientation). The unique set of vertices (asConstraintVertex
es) forming the constraints must also be supplied. Supplying it explicitly allows the ConstraintVertexes to be initialized appropriately (e.g. with external data), and avoids re-computing the unique set if it is already available.- Parameters:
segments
- a list of the constraintSegment
ssegVertices
- the set of uniqueConstraintVertex
es referenced by the segments
-
setSplitPointFinder
public void setSplitPointFinder(ConstraintSplitPointFinder splitFinder)
Sets theConstraintSplitPointFinder
to be used during constraint enforcement. Different splitting strategies may be appropriate for special situations.- Parameters:
splitFinder
- the ConstraintSplitPointFinder to be used
-
getTolerance
public double getTolerance()
Gets the tolerance value used to construct the triangulation.- Returns:
- a tolerance value
-
getVertexFactory
public ConstraintVertexFactory getVertexFactory()
Gets the ConstraintVertexFactory used to create new constraint vertices at split points.- Returns:
- a new constraint vertex
-
setVertexFactory
public void setVertexFactory(ConstraintVertexFactory vertexFactory)
Sets a customConstraintVertexFactory
to be used to allow vertices carrying extra information to be created.- Parameters:
vertexFactory
- the ConstraintVertexFactory to be used
-
getSubdivision
public QuadEdgeSubdivision getSubdivision()
Gets theQuadEdgeSubdivision
which represents the triangulation.- Returns:
- a subdivision
-
getKDT
public KdTree getKDT()
Gets theKdTree
which contains the vertices of the triangulation.- Returns:
- a KdTree
-
getInitialVertices
public java.util.List getInitialVertices()
Gets the sites (vertices) used to initialize the triangulation.- Returns:
- a List of Vertex
-
getConstraintSegments
public java.util.Collection getConstraintSegments()
Gets theSegment
s which represent the constraints.- Returns:
- a collection of Segments
-
getConvexHull
public Geometry getConvexHull()
Gets the convex hull of all the sites in the triangulation, including constraint vertices. Only valid after the constraints have been enforced.- Returns:
- the convex hull of the sites
-
computeBoundingBox
private void computeBoundingBox()
-
computeConvexHull
private void computeConvexHull()
-
getPointArray
private Coordinate[] getPointArray()
-
createVertex
private ConstraintVertex createVertex(Coordinate p)
-
createVertex
private ConstraintVertex createVertex(Coordinate p, Segment seg)
Creates a vertex on a constraint segment- Parameters:
p
- the location of the vertex to createseg
- the constraint segment it lies on- Returns:
- the new constraint vertex
-
insertSites
private void insertSites(java.util.Collection vertices)
Inserts all sites in a collection- Parameters:
vertices
- a collection of ConstraintVertex
-
insertSite
private ConstraintVertex insertSite(ConstraintVertex v)
-
insertSite
public void insertSite(Coordinate p)
Inserts a site into the triangulation, maintaining the conformal Delaunay property. This can be used to further refine the triangulation if required (e.g. to approximate the medial axis of the constraints, or to improve the grading of the triangulation).- Parameters:
p
- the location of the site to insert
-
formInitialDelaunay
public void formInitialDelaunay()
Computes the Delaunay triangulation of the initial sites.
-
enforceConstraints
public void enforceConstraints()
Enforces the supplied constraints into the triangulation.- Throws:
ConstraintEnforcementException
- if the constraints cannot be enforced
-
addConstraintVertices
private void addConstraintVertices()
-
enforceGabriel
private int enforceGabriel(java.util.Collection segsToInsert)
-
findNonGabrielPoint
private Coordinate findNonGabrielPoint(Segment seg)
Given a set of points stored in the kd-tree and a line segment defined by two points in this set, finds aCoordinate
in the circumcircle of the line segment, if one exists. This is called the Gabriel point - if none exists then the segment is said to have the Gabriel condition. Uses the heuristic of finding the non-Gabriel point closest to the midpoint of the segment.- Parameters:
p
- start of the line segmentq
- end of the line segment- Returns:
- a point which is non-Gabriel or null if no point is non-Gabriel
-
-