## Triangulations and ApplicationsThis 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

12 Triangulations | 5 |

13 Some Properties of Triangulations | 7 |

14 A Triangulation Algorithm | 10 |

15 Edge Insertion | 16 |

16 Using Triangulations | 18 |

17 Exercises | 20 |

Graphs and Data Structures | 23 |

56 Modiﬁed Local Optimization Procedures MLOP | 106 |

58 Exercises | 112 |

Constrained Delaunay Triangulation | 113 |

62 Generalization of Delaunay Triangulation | 115 |

63 Algorithms for Constrained Delaunay Triangulation | 118 |

64 Inserting an Edge into a CDT | 119 |

65 Edge Insertion and Swapping | 123 |

66 Inserting a Point into a CDT | 127 |

22 Generalized Maps Gmaps | 25 |

23 Data Structures for Triangulations | 29 |

24 A Minimal TriangleBased Data Structure | 31 |

25 TriangleBased Data Structure with Neighbors | 32 |

26 VertexBased Data Structure with Neighbors | 33 |

27 HalfEdge Data Structure | 35 |

28 DartBased Data Structure | 37 |

29 Triangles for Visualization | 38 |

210 Binary Triangulations | 41 |

211 Exercises | 45 |

Delaunay Triangulations and Voronoi Diagrams | 46 |

32 The Neutral Case | 50 |

33 Voronoi Diagrams | 51 |

34 Delaunay Triangulation as the Dual of the Voronoi Diagram | 54 |

35 The Circle Criterion | 57 |

36 Equivalence of the Delaunay Criteria for Strictly Convex Quadrilaterals | 59 |

37 Computing the Circumcircle Test | 62 |

38 The Local Optimization Procedure LOP | 64 |

39 Global Properties of the Delaunay Triangulation | 66 |

310 Exercises | 71 |

Algorithms for Delaunay Triangulation | 73 |

42 Radial Sweep | 74 |

43 A StepbyStep Approach for Making Delaunay Triangles | 75 |

44 Incremental Algorithms | 78 |

45 Inserting a Point into a Delaunay Triangulation | 79 |

46 Point Insertion and EdgeSwapping | 81 |

47 Running Time of Incremental Algorithms | 87 |

48 DivideandConquer | 89 |

49 Exercises | 92 |

Data Dependent Triangulations | 94 |

52 Optimal Triangulations Revisited | 96 |

53 The General Concept | 98 |

54 Data Dependent Swapping Criteria | 101 |

55 On Implementation of the LOP | 105 |

67 Exercises | 129 |

Delaunay Reﬁnement Mesh Generation | 131 |

72 General Requirements for Meshes | 132 |

73 Node Insertion | 134 |

74 Splitting Encroached Segments | 139 |

75 The Delaunay Reﬁnement Algorithm | 142 |

76 Minimum Edge Length and Termination | 145 |

77 CornerLopping for Handling Small Input Angles | 152 |

78 Spatial Grading | 154 |

Least Squares Approximation of Scattered Data | 156 |

82 Approximation over Triangulations of Subsets of Data | 160 |

83 Existence and Uniqueness | 163 |

84 Sparsity and Symmetry | 164 |

85 Penalized Least Squares | 166 |

86 Smoothing Terms for Penalized Least Squares | 168 |

87 Approximation over General Triangulations | 175 |

88 Weighted Least Squares | 178 |

89 Constrained Least Squares | 180 |

810 Approximation over Binary Triangulations | 182 |

811 Numerical Examples for Binary Triangulations | 185 |

812 Exercises | 191 |

Programming Triangulations The Triangulation Template Library TTL | 193 |

91 Implementation of the HalfEdge Data Structure | 194 |

92 The Overall Design and the Adaptation Layer | 197 |

93 Topological Queries and the Dart Class | 199 |

94 Some Iterator Classes | 203 |

95 Geometric Queries and the Traits Class | 205 |

96 Geometric and Topological Modiﬁers | 211 |

97 Generic Delaunay Triangulation | 213 |

98 Exercises | 221 |

223 | |

229 | |

### Other editions - View all

### Common terms and phrases

application approximation binary triangulation boundary Chapter circle criterion circumcenter circumcircle circumcircle test closed polygon cocircular coeﬃcients constrained Delaunay triangulation constrained edge constructing convex hull cost function data structure deﬁned Deﬁnition Delaunay edge Delaunay triangulation diagonal diﬀerent edge-swaps edges and triangles encroached endpoints equations example ﬁgure ﬁnal ﬁnd ﬁnite ﬁrst ﬁxed function templates G-maps geometric graph gulation implemented indicator vector inﬂuence polygon input PSLG insertion point interior angle interior edges intersect iterator least squares least squares approximation Lemma lexicographically linear locally optimal MaxMin angle criterion mesh modiﬁed node non-zero number of triangles operations optimal triangulation pi and pj plane point set recursively reﬁnement scattered data Section segments set of points shortest edge simulated annealing skinny triangle strictly convex quadrilateral subset surface triangulation system matrix Theorem tion topological triangle fan triangle strip triangulation in Figure vertex Voronoi diagram Voronoi neighbors Voronoi regions