Chapter 4Triangulation
Chapters 5–7 discuss the subject of triangulation. Historically, triangulation has been of interest when measuring the distance between two points without necessarily needing to move between them. To do this, it is enough to take a segment and to calculate, at its extremities, the angle formed by this segment and a distant target point. Knowing these two angles makes it possible to then find the distance between the target point and its extremities, with these three points forming a triangle (a well-known application of this procedure was the calculation made in 1792 of the distance between Dunkirk and Barcelona along the Paris meridian1). Let us also note that in daily life, the term “triangulation” has other meanings. Our interest in triangulation, of course, lies in the crucial role it plays both in geometric modeling as well as being a fundamental component that allows for the construction of meshes, in particular in the context of numerical simulations in which the mesh represents, discretely, the computational domain.
Generally speaking, triangulations, especially Delaunay triangulations, have been widely studied in computational geometry (CG) with the seminal book [Preparata, Shamos-1985] and [Edelsbrunner-1987], [Sedgewick-1988], [Moret, Shapiro-1991], [O’Rourke-1994] as well as [Boissonnat, Yvinec-1997] and [Edelsbrunner-2001] are just a few of the essential references that contain substantial sections devoted to triangulations. A triangulation, ...