Triangulations and ApplicationsThis book is entirely about triangulations. With emphasis on computational issues, we present the basic theory necessary to construct and manipulate triangulations. In particular, we make a tour through the theory behind the Delaunay triangulation, including algorithms and software issues. We also discuss various data structures used for the representation of triangulations. Throughout the book we relate the theory to selected applications, in part- ular surface construction, meshing and visualization. The ?eld of triangulation is part of the huge area of computational ge- etry, and over many years numerous books and articles have been written on the subject. Important results on triangulations have appeared in theore- cal books and articles, mostly within the realm of computational geometry. However, many important results on triangulations have also been presented in publications within other research areas, where they have played and play an important role in solving speci?c scienti?c and applied problems. We will touch upon some of these areas in this book. Triangulations, almost everywhere. The early development of triangulation comes from surveying and the art of constructing maps – cartography. S- veyors and cartographers used triangles as the basic geometric feature for calculating distances between points on the Earth’s surface and a position’s elevation above sea level. |
Contents
| 1 | |
Graphs and Data Structures | 23 |
Delaunay Triangulations and Voronoi Diagrams 47 | 46 |
Algorithms for Delaunay Triangulation | 73 |
Data Dependent Triangulations 95 | 94 |
Constrained Delaunay Triangulation | 113 |
Delaunay Refinement Mesh Generation | 131 |
Least Squares Approximation of Scattered Data 157 | 156 |
References | 223 |
Other editions - View all
Common terms and phrases
a-iterators Algorithm 7.1 AN+1 applied approximation binary triangulation boundary Chapter circle criterion circumcenter circumcircle test closed polygon cocircular Computational Geometry Computer constrained Delaunay triangulation constrained edge constructing convex hull cost function data structure defined Delaunay edge Delaunay triangulation diagonal edge-swaps edges and triangles encroached endpoints equations example function templates G-maps geometric graph gulation implemented indicator vector influence polygon input PSLG insertion point inside interior angle interior edges intersect iterators least squares least squares approximation Lemma lexicographically linear locally optimal MaxMin angle criterion mesh node non-zero number of triangles OpenGL operations optimal triangulation plane point set positive semidefinite recursively scattered data Section segments set of points shortest edge simulated annealing skinny triangle strictly convex quadrilateral subset surface triangulation system matrix Theorem tion topological triangle fan triangle strip triangulation in Figure unique vertex Voronoi diagram Voronoi regions