Springer Press：Triangulations and Applications

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