Constrained Delaunay triangulation

In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges,^[1]^[2] 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 $e$ added to this input to make it into a triangulation, there should exist a circle through the endpoints of $e$ , such that any vertex interior to the circle is blocked from visibility from at least one endpoint of $e$ 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.^[1]

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.^[2]

Algorithms[]

Several algorithms for computing constrained Delaunay triangulations of planar straight-line graphs in time $O(n\log n)$ are known.^[1]^[3] The constrained Delaunay triangulation of a simple polygon can be constructed in linear time.^[4]

Applications[]

In topographic surveying, 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, as a way to force the mesh to conform with the domain boundaries as it is being refined.

References[]

^ ^a ^b ^c Chew, L. Paul (1989), "Constrained Delaunay triangulations", Algorithmica, 4 (1): 97–108, doi:10.1007/BF01553881, MR 0983658, S2CID 189918468
^ ^a ^b Shewchuk, Jonathan Richard (2008), "General-dimensional constrained Delaunay and constrained regular triangulations. I. Combinatorial properties", Discrete & Computational Geometry, 39 (1–3): 580–637, doi:10.1007/s00454-008-9060-3, MR 2383774
^ Wang, Cao An; Schubert, Lenhart K. (1987), "An optimal algorithm for constructing the Delaunay triangulation of a set of line segments", in Soule, D. (ed.), Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987, ACM, pp. 223–232, doi:10.1145/41958.41982, S2CID 18490297
^ Chin, Francis; Wang, Cao An (1999), "Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time", SIAM Journal on Computing, 28 (2): 471–486, doi:10.1137/S0097539795285916, hdl:10722/47094, MR 1634357

External links[]

Daedalus Lib Open Source. Daedalus Lib manages fully dynamic constrained Delaunay triangulations.

This algorithms or data structures-related article is a stub. You can help Wikipedia by .

[chew-1] Chew, L. Paul (1989), "Constrained Delaunay triangulations", Algorithmica, 4 (1): 97–108, doi:10.1007/BF01553881, MR 0983658, S2CID 189918468

[shewchuk-2] Shewchuk, Jonathan Richard (2008), "General-dimensional constrained Delaunay and constrained regular triangulations. I. Combinatorial properties", Discrete & Computational Geometry, 39 (1–3): 580–637, doi:10.1007/s00454-008-9060-3, MR 2383774

[3] Wang, Cao An; Schubert, Lenhart K. (1987), "An optimal algorithm for constructing the Delaunay triangulation of a set of line segments", in Soule, D. (ed.), Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987, ACM, pp. 223–232, doi:10.1145/41958.41982, S2CID 18490297

[4] Chin, Francis; Wang, Cao An (1999), "Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time", SIAM Journal on Computing, 28 (2): 471–486, doi:10.1137/S0097539795285916, hdl:10722/47094, MR 1634357

[1]

[2]

[3]

[4]