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.
Algorithms
Several algorithms for computing constrained Delaunay triangulations of planar straight-line graphs in time 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 Chew, L. Paul (1987). "Constrained Delaunay Triangulations". Proceedings of the Third Annual Symposium on Computational Geometry.
- ^
Shewchuk, Jonathan R. (2008). "General-Dimensional Constrained Delaunay and Constrained Regular Triangulations, I: Combinatorial Properties". 39 (1–3): 580–637.
{{cite journal}}: Cite journal requires|journal=(help); Unknown parameter|book-title=ignored (help) - ^ 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
- ^ 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, 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 expanding it. |