public class ConformingDelaunayTriangulator
extends java.lang.Object
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();
Modifier and Type | Field and 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 and Description |
---|
ConformingDelaunayTriangulator(java.util.Collection initialVertices,
double tolerance)
Creates a Conforming Delaunay Triangulation based on the given
unconstrained initial vertices.
|
Modifier and Type | Method and 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 segment
|
void |
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 a
Coordinate 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 the
Segment 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 the
KdTree which contains the vertices of the triangulation. |
private Coordinate[] |
getPointArray() |
QuadEdgeSubdivision |
getSubdivision()
Gets the
QuadEdgeSubdivision 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.
|
private ConstraintVertex |
insertSite(ConstraintVertex v) |
void |
insertSite(Coordinate p)
Inserts a site into the triangulation, maintaining the conformal Delaunay property.
|
private void |
insertSites(java.util.Collection vertices)
Inserts all sites in a collection
|
void |
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 the
ConstraintSplitPointFinder to be
used during constraint enforcement. |
void |
setVertexFactory(ConstraintVertexFactory vertexFactory)
Sets a custom
ConstraintVertexFactory to be used
to allow vertices carrying extra information to be created. |
private java.util.List initialVertices
private java.util.List segVertices
private java.util.List segments
private QuadEdgeSubdivision subdiv
private IncrementalDelaunayTriangulator incDel
private Geometry convexHull
private ConstraintSplitPointFinder splitFinder
private KdTree kdt
private ConstraintVertexFactory vertexFactory
private Envelope computeAreaEnv
private Coordinate splitPt
private double tolerance
private static final int MAX_SPLIT_ITER
public ConformingDelaunayTriangulator(java.util.Collection initialVertices, double tolerance)
initialVertices
- a collection of ConstraintVertex
tolerance
- the distance tolerance below which points are considered identicalprivate static Envelope computeVertexEnvelope(java.util.Collection vertices)
public void setConstraints(java.util.List segments, java.util.List segVertices)
ConstraintVertex
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.segments
- a list of the constraint Segment
ssegVertices
- the set of unique ConstraintVertex
es referenced by the segmentspublic void setSplitPointFinder(ConstraintSplitPointFinder splitFinder)
ConstraintSplitPointFinder
to be
used during constraint enforcement.
Different splitting strategies may be appropriate
for special situations.splitFinder
- the ConstraintSplitPointFinder to be usedpublic double getTolerance()
public ConstraintVertexFactory getVertexFactory()
public void setVertexFactory(ConstraintVertexFactory vertexFactory)
ConstraintVertexFactory
to be used
to allow vertices carrying extra information to be created.vertexFactory
- the ConstraintVertexFactory to be usedpublic QuadEdgeSubdivision getSubdivision()
QuadEdgeSubdivision
which represents the triangulation.public KdTree getKDT()
KdTree
which contains the vertices of the triangulation.public java.util.List getInitialVertices()
public java.util.Collection getConstraintSegments()
Segment
s which represent the constraints.public Geometry getConvexHull()
private void computeBoundingBox()
private void computeConvexHull()
private Coordinate[] getPointArray()
private ConstraintVertex createVertex(Coordinate p)
private ConstraintVertex createVertex(Coordinate p, Segment seg)
p
- the location of the vertex to createseg
- the constraint segment it lies onprivate void insertSites(java.util.Collection vertices)
vertices
- a collection of ConstraintVertexprivate ConstraintVertex insertSite(ConstraintVertex v)
public void insertSite(Coordinate p)
p
- the location of the site to insertpublic void formInitialDelaunay()
public void enforceConstraints()
ConstraintEnforcementException
- if the constraints cannot be enforcedprivate void addConstraintVertices()
private int enforceGabriel(java.util.Collection segsToInsert)
private Coordinate findNonGabrielPoint(Segment seg)
Coordinate
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.p
- start of the line segmentq
- end of the line segment