Hjelle Ø. Dæhlen M. Triangulations and Applications

Springer, 2006. — 237 p.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.Triangles and Triangulations
Triangles
Triangulations
Some Properties of Triangulations
A Triangulation Algorithm
Edge Insertion
Using Triangulations
Exercises
Graphs and Data Structures
Graph Theoretic Concepts
Generalized Maps (G-maps)
Data Structures for Triangulations
A Minimal Triangle-Based Data Structure
Triangle-Based Data Structure with Neighbors
Vertex-Based Data Structure with Neighbors
Half-Edge Data Structure
Dart-Based Data Structure
Triangles for Visualization
Binary Triangulations
Exercises
Delaunay Triangulations and Voronoi Diagrams
Optimal Triangulations
The Neutral Case
Voronoi Diagrams
Delaunay Triangulation as the Dual of the Voronoi Diagram
The Circle Criterion
Equivalence of the Delaunay Criteria
for Strictly Convex Quadrilaterals
Computing the Circumcircle Test
The Local Optimization Procedure (LOP)
Global Properties of the Delaunay Triangulation
Exercises
Algorithms for Delaunay Triangulation
A Simple Algorithm Based on Previous Results
Radial Sweep
A Step-by-Step Approach for Making Delaunay Triangles
Incremental Algorithms
Inserting a Point into a Delaunay Triangulation
Point Insertion and Edge-Swapping
Running Time of Incremental Algorithms
Divide-and-Conquer
Exercises
Data Dependent Triangulations
Motivation
Optimal Triangulations Revisited
The General Concept
Data Dependent Swapping Criteria
On Implementation of the LOP
Modified Local Optimization Procedures (MLOP)
Simulated Annealing
Exercises
Constrained Delaunay Triangulation
Delaunay Triangulation of a Planar Straight-Line Graph
Generalization of Delaunay Triangulation
Algorithms for Constrained Delaunay Triangulation
Inserting an Edge into a CDT
Edge Insertion and Swapping
Inserting a Point into a CDT
Exercises
Delaunay Refinement Mesh GenerationGeneral Requirements for Meshes
Node Insertion
Splitting Encroached Segments
The Delaunay Refinement Algorithm
Minimum Edge Length and Termination
Corner-Lopping for Handling Small Input Angles
Spatial Grading
Exercises
Least Squares Approximation of Scattered Data
Another Formulation of Surface Triangulations
Approximation over Triangulations of Subsets of Data
Existence and Uniqueness
Sparsity and Symmetry
Penalized Least Squares
Smoothing Terms for Penalized Least Squares
Approximation over General Triangulations
Weighted Least Squares
Constrained Least Squares
Approximation over Binary Triangulations
Numerical Examples for Binary Triangulations
Exercises
Programming Triangulations:
The Triangulation Template Library (TTL)
Implementation of the Half-Edge Data Structure
The Overall Design and the Adaptation Layer
Topological Queries and the Dart Class
Some Iterator Classes
Geometric Queries and the Traits Class
Geometric and Topological Modifiers
Generic Delaunay Triangulation
Exercises