Triangulations and applications

This 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.

1 Triangles and Triangulations	p. 1
1.1 Triangles	p. 1
1.2 Triangulations	p. 5
1.3 Some Properties of Triangulations	p. 7
1.4 A Triangulation Algorithm	p. 10
1.5 Edge Insertion	p. 16
1.6 Using Triangulations	p. 18
1.7 Exercises	p. 20
2 Graphs and Data Structures	p. 23
2.1 Graph Theoretic Concepts	p. 23
2.2 Generalized Maps (G-maps)	p. 25
2.3 Data Structures for Triangulations	p. 29
2.4 A Minimal Triangle-Based Data Structure	p. 31
2.5 Triangle-Based Data Structure with Neighbors	p. 32
2.6 Vertex-Based Data Structure with Neighbors	p. 33
2.7 Half-Edge Data Structure	p. 35
2.8 Dart-Based Data Structure	p. 37
2.9 Triangles for Visualization	p. 38
2.10 Binary Triangulations	p. 41
2.11 Exercises	p. 45
3 Delaunay Triangulations and Voronoi Diagrams	p. 47
3.1 Optimal Triangulations	p. 47
3.2 The Neutral Case	p. 50
3.3 Voronoi Diagrams	p. 51
3.4 Delaunay Triangulation as the Dual of the Voronoi Diagram	p. 54
3.5 The Circle Criterion	p. 57
3.6 Equivalence of the Delaunay Criteria for Strictly Convex Quadrilaterals	p. 59
3.7 Computing the Circumcircle Test	p. 62
3.8 The Local Optimization Procedure (LOP)	p. 64
3.9 Global Properties of the Delaunay Triangulation	p. 66
3.10 Exercises	p. 71
4 Algorithms for Delaunay Triangulation	p. 73
4.1 A Simple Algorithm Based on Previous Results	p. 73
4.2 Radial Sweep	p. 74
4.3 A Step-by-Step Approach for Making Delaunay Triangles	p. 75
4.4 Incremental Algorithms	p. 78
4.5 Inserting a Point into a Delaunay Triangulation	p. 79
4.6 Point Insertion and Edge-Swapping	p. 81
4.7 Running Time of Incremental Algorithms	p. 87
4.8 Divide-and-Conquer	p. 89
4.9 Exercises	p. 92
5 Data Dependent Triangulations	p. 95
5.1 Motivation	p. 95
5.2 Optimal Triangulations Revisited	p. 96
5.3 The General Concept	p. 98
5.4 Data Dependent Swapping Criteria	p. 101
5.5 On Implementation of the LOP	p. 105
5.6 Modified Local Optimization Procedures (MLOP)	p. 106
5.7 Simulated Annealing	p. 106
5.8 Exercises	p. 112
6 Constrained Delaunay Triangulation	p. 113
6.1 Delaunay Triangulation of a Planar Straight-Line Graph	p. 113
6.2 Generalization of Delaunay Triangulation	p. 115
6.3 Algorithms for Constrained Delaunay Triangulation	p. 118
6.4 Inserting an Edge into a CDT	p. 119
6.5 Edge Insertion and Swapping	p. 123
6.6 Inserting a Point into a CDT	p. 127
6.7 Exercises	p. 129
7 Delaunay Refinement Mesh Generation	p. 131
7.1 Introduction	p. 131
7.2 General Requirements for Meshes	p. 132
7.3 Node Insertion	p. 134
7.4 Splitting Encroached Segments	p. 139
7.5 The Delaunay Refinement Algorithm	p. 142
7.6 Minimum Edge Length and Termination	p. 145
7.7 Corner-Lopping for Handling Small Input Angles	p. 152
7.8 Spatial Grading	p. 154
7.9 Exercises	p. 154
8 Least Squares Approximation of Scattered Data	p. 157
8.1 Another Formulation of Surface Triangulations	p. 157
8.2 Approximation over Triangulations of Subsets of Data	p. 160
8.3 Existence and Uniqueness	p. 163
8.4 Sparsity and Symmetry	p. 164
8.5 Penalized Least Squares	p. 166
8.6 Smoothing Terms for Penalized Least Squares	p. 168
8.7 Approximation over General Triangulations	p. 175
8.8 Weighted Least Squares	p. 178
8.9 Constrained Least Squares	p. 180
8.10 Approximation over Binary Triangulations	p. 182
8.11 Numerical Examples for Binary Triangulations	p. 185
8.12 Exercises	p. 191
9 Programming Triangulations: The Triangulation Template Library (TTL)	p. 193
9.1 Implementation of the Half-Edge Data Structure	p. 194
9.2 The Overall Design and the Adaptation Layer	p. 197
9.3 Topological Queries and the Dart Class	p. 199
9.4 Some Iterator Classes	p. 203
9.5 Geometric Queries and the Traits Class	p. 205
9.6 Geometric and Topological Modifiers	p. 211
9.7 Generic Delaunay Triangulation	p. 213
9.8 Exercises	p. 221
References	p. 223
Index	p. 229

Available:*

On Order

Summary

Summary

Table of Contents