Chapter 6Triangulation and Constraints
We have seen that the triangulation of a point cloud is defined as the covering of the convex hull of this cloud by simplices. The triangulation of a domain, however, is defined as the covering of this domain by simplices. Consequently, the border (curve or surface) of the domain constitutes an immediate geometric constraint that must be preserved, as will be explained, by the desired triangulation. Demanding the existence of a border k-face (or even a non-border, and thus an internal k-face) called the constrained k-face in a triangulation is the simplest constrained triangulation problem that we can imagine. In this chapter, we will essentially explore constrained triangulation in two and three dimensions.
There is, nonetheless, a situation where, given a set of edges (faces), the Delaunay triangulation constructed by inserting the extremities of these edges (the vertices of the faces) is such that all these entities are present as the edges (faces) of the constructed elements. We then say that the edges (faces) are Delaunay admissible.
Beyond these geometric constraints, we can think of specific constraints that concern geometric properties that we would like to see verified. The simplest example of a constraint of this nature is (in two dimensions) acute triangulations (meshes). The constraint is that the three angles of the triangles must be acute. We can imagine all kinds of other specific constraints: angle, orthogonality, autocentering, ...