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