Triangulations and Applications (eBook)

Preface 5
Contents 9
1 Triangles and Triangulations 12
1.1 Triangles 12
1.2 Triangulations 16
1.3 Some Properties of Triangulations 18
1.4 A Triangulation Algorithm 21
1.5 Edge Insertion 27
1.6 Using Triangulations 29
1.7 Exercises 31
2 Graphs and Data Structures 34
2.1 Graph Theoretic Concepts 34
2.2 Generalized Maps (G-maps) 36
2.3 Data Structures for Triangulations 40
2.4 A Minimal Triangle-Based Data Structure 42
2.5 Triangle-Based Data Structure with Neighbors 43
2.6 Vertex-Based Data Structure with Neighbors 44
2.7 Half-Edge Data Structure 46
2.8 Dart-Based Data Structure 48
2.9 Triangles for Visualization 49
2.10 Binary Triangulations 52
2.11 Exercises 56
3 Delaunay Triangulations and Voronoi Diagrams 58
3.1 Optimal Triangulations 58
3.2 The Neutral Case 61
3.3 Voronoi Diagrams 62
3.4 Delaunay Triangulation as the Dual of the Voronoi Diagram 65
3.5 The Circle Criterion 68
3.6 Equivalence of the Delaunay Criteria for Strictly Convex Quadrilaterals 70
3.7 Computing the Circumcircle Test 73
3.8 The Local Optimization Procedure (LOP) 75
3.9 Global Properties of the Delaunay Triangulation 77
3.10 Exercises 82
4 Algorithms for Delaunay Triangulation 84
4.1 A Simple Algorithm Based on Previous Results 84
4.2 Radial Sweep 85
4.3 A Step-by-Step Approach for Making Delaunay Triangles 86
4.4 Incremental Algorithms 89
4.5 Inserting a Point into a Delaunay Triangulation 90
4.6 Point Insertion and Edge-Swapping 92
4.7 Running Time of Incremental Algorithms 98
4.8 Divide-and-Conquer 100
4.9 Exercises 103
5 Data Dependent Triangulations 106
5.1 Motivation 106
5.2 Optimal Triangulations Revisited 107
5.3 The General Concept 109
5.4 Data Dependent Swapping Criteria 112
5.5 On Implementation of the LOP 116
5.6 Modified Local Optimization Procedures (MLOP) 117
5.7 Simulated Annealing 117
5.8 Exercises 123
6 Constrained Delaunay Triangulation 124
6.1 Delaunay Triangulation of a Planar Straight-Line Graph 124
6.2 Generalization of Delaunay Triangulation 126
6.3 Algorithms for Constrained Delaunay Triangulation 129
6.4 Inserting an Edge into a CDT 130
6.5 Edge Insertion and Swapping 134
6.6 Inserting a Point into a CDT 138
6.7 Exercises 140
7 Delaunay Refinement Mesh Generation 142
7.1 Introduction 142
7.2 General Requirements for Meshes 143
7.3 Node Insertion 145
7.4 Splitting Encroached Segments 150
7.5 The Delaunay Refinement Algorithm 153
7.6 Minimum Edge Length and Termination 156
7.7 Corner-Lopping for Handling Small Input Angles 163
7.8 Spatial Grading 165
7.9 Exercises 165
8 Least Squares Approximation of Scattered Data 168
8.1 Another Formulation of Surface Triangulations 168
8.2 Approximation over Triangulations of Subsets of Data 171
8.3 Existence and Uniqueness 174
8.4 Sparsity and Symmetry 175
8.5 Penalized Least Squares 177
8.6 Smoothing Terms for Penalized Least Squares 179
8.7 Approximation over General Triangulations 186
8.8 Weighted Least Squares 189
8.9 Constrained Least Squares 191
8.10 Approximation over Binary Triangulations 193
8.11 Numerical Examples for Binary Triangulations 196
8.12 Exercises 202
9 Programming Triangulations: The Triangulation Template Library (TTL) 204
9.1 Implementation of the Half-Edge Data Structure 205
9.2 The Overall Design and the Adaptation Layer 208
9.3 Topological Queries and the Dart Class 210
9.4 Some Iterator Classes 214
9.5 Geometric Queries and the Traits Class 216
9.6 Geometric and Topological Modifiers 222
9.7 Generic Delaunay Triangulation 224
9.8 Exercises 232
References 234
Index 240