ART

In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation.[1][2] Because a Delaunay triangulation is almost always unique, often a constrained Delaunay triangulation contains edges that do not satisfy the Delaunay condition. Thus a constrained Delaunay triangulation often is not a Delaunay triangulation itself.

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.
See also

Chew's second algorithm

References

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.

External links

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

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License