In
computational geometry, a constrained Delaunay triangulation is a generalization of the
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...
that forces certain required segments into the triangulation as edges,
unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation.
Definition
The input to the constrained Delaunay triangulation problem is a
planar straight-line graph, a set of points and non-crossing line segments in the plane.
The constrained Delaunay triangulation of this input is a triangulation of its
convex hull, including all of the input segments as edges, and using only the vertices of the input. For every additional edge
added to this input to make it into a triangulation, there should exist a circle through the endpoints of
, such that any vertex interior to the circle is blocked from visibility from at least one endpoint of
by a segment of the input. This generalizes the defining property of two-dimensional Delaunay triangulations of points, that each edge have a circle through its two endpoints containing no other vertices. A triangulation satisfying these properties always exists.
[
Jonathan Shewchuk has generalized this definition to constrained Delaunay triangulations of three-dimensional inputs, systems of points and non-crossing segments and triangles in three-dimensional space; however, not every input of this type has a constrained Delaunay triangulation according to his generalized definition.][
]
Algorithms
Several algorithms for computing constrained Delaunay triangulations of planar straight-line graphs in time are known.[ The constrained Delaunay triangulation of a ]simple polygon
In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If ...
can be constructed in linear time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
.
Applications
In topographic
Topography is the study of the forms and features of land surfaces. The topography of an area may refer to the land forms and features themselves, or a description or depiction in maps.
Topography is a field of geoscience and planetary sci ...
surveying
Surveying or land surveying is the technique, profession, art, and science of determining the terrestrial two-dimensional or three-dimensional positions of points and the distances and angles between them. A land surveying professional is ...
, one constructs a triangulation from points shot in the field. If an edge of the triangulation crosses a river, the resulting surface does not accurately model the path of the river. So one draws breaklines along rivers, edges of roads, mountain ridges, and the like. The breaklines are used as constraints when constructing the triangulation.
Constrained Delaunay triangulation can also be used in Delaunay refinement methods for mesh generation
Mesh generation is the practice of creating a polygon mesh, mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells.
Often these cells form a simplicial complex.
Usually the cells partition the geometric ...
, as a way to force the mesh to conform with the domain boundaries as it is being refined.
References
External links
Open Source implementation.
Geometry processing
Triangulation (geometry)
{{algorithm-stub