资源大小： 7.89MB
发布时间： 2009-07-25
文件格式： pdf
下载次数： 4
分享到：

下载地址：

下载地址1
（本站为飞网专业下载站，域名：down.cfei.net）

资源简介：

Triangulations and ApplicationsContents1 Triangles and Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Some Properties of Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . 71.4 A Triangulation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.5 Edge Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.6 Using Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 Graphs and Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.1 Graph Theoretic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2 Generalized Maps (G-maps) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3 Data Structures for Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . 292.4 A Minimal Triangle-Based Data Structure . . . . . . . . . . . . . . . . . . 312.5 Triangle-Based Data Structure with Neighbors . . . . . . . . . . . . . . 322.6 Vertex-Based Data Structure with Neighbors . . . . . . . . . . . . . . . . 332.7 Half-Edge Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.8 Dart-Based Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.9 Triangles for Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.10 Binary Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 Delaunay Triangulations and Voronoi Diagrams . . . . . . . . . . . 473.1 Optimal Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.2 The Neutral Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.3 Voronoi Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.4 Delaunay Triangulation as the Dual of the Voronoi Diagram . . 543.5 The Circle Criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.6 Equivalence of the Delaunay Criteriafor Strictly Convex Quadrilaterals . . . . . . . . . . . . . . . . . . . . . . . . . 593.7 Computing the Circumcircle Test . . . . . . . . . . . . . . . . . . . . . . . . . . 623.8 The Local Optimization Procedure (LOP) . . . . . . . . . . . . . . . . . . 643.9 Global Properties of the Delaunay Triangulation . . . . . . . . . . . . 663.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714 Algorithms for Delaunay Triangulation . . . . . . . . . . . . . . . . . . . . 734.1 A Simple Algorithm Based on Previous Results . . . . . . . . . . . . . 734.2 Radial Sweep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744.3 A Step-by-Step Approach for Making Delaunay Triangles . . . . 754.4 Incremental Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 784.5 Inserting a Point into a Delaunay Triangulation . . . . . . . . . . . . . 794.6 Point Insertion and Edge-Swapping . . . . . . . . . . . . . . . . . . . . . . . . 814.7 Running Time of Incremental Algorithms . . . . . . . . . . . . . . . . . . . 874.8 Divide-and-Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 894.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925 Data Dependent Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955.2 Optimal Triangulations Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . 965.3 The General Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985.4 Data Dependent Swapping Criteria . . . . . . . . . . . . . . . . . . . . . . . . 1015.5 On Implementation of the LOP . . . . . . . . . . . . . . . . . . . . . . . . . . . 1055.6 Modified Local Optimization Procedures (MLOP) . . . . . . . . . . . 1065.7 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1065.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1126 Constrained Delaunay Triangulation . . . . . . . . . . . . . . . . . . . . . . . 1136.1 Delaunay Triangulation of a Planar Straight-Line Graph . . . . . 1136.2 Generalization of Delaunay Triangulation . . . . . . . . . . . . . . . . . . . 1156.3 Algorithms for Constrained Delaunay Triangulation . . . . . . . . . . 1186.4 Inserting an Edge into a CDT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1196.5 Edge Insertion and Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1236.6 Inserting a Point into a CDT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1276.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1297 Delaunay Refinement Mesh Generation . . . . . . . . . . . . . . . . . . . . 1317.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1317.2 General Requirements for Meshes. . . . . . . . . . . . . . . . . . . . . . . . . . 1327.3 Node Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1347.4 Splitting Encroached Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1397.5 The Delaunay Refinement Algorithm . . . . . . . . . . . . . . . . . . . . . . . 1427.6 Minimum Edge Length and Termination . . . . . . . . . . . . . . . . . . . 1457.7 Corner-Lopping for Handling Small Input Angles . . . . . . . . . . . . 1527.8 Spatial Grading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1547.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1548 Least Squares Approximation of Scattered Data . . . . . . . . . . . 1578.1 Another Formulation of Surface Triangulations . . . . . . . . . . . . . . 1578.2 Approximation over Triangulations of Subsets of Data . . . . . . . 1608.3 Existence and Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1638.4 Sparsity and Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1648.5 Penalized Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1668.6 Smoothing Terms for Penalized Least Squares . . . . . . . . . . . . . . 1688.7 Approximation over General Triangulations . . . . . . . . . . . . . . . . . 1758.8 Weighted Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1788.9 Constrained Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1808.10 Approximation over Binary Triangulations . . . . . . . . . . . . . . . . . . 1828.11 Numerical Examples for Binary Triangulations . . . . . . . . . . . . . . 1858.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1919 Programming Triangulations:The Triangulation Template Library (TTL) . . . . . . . . . . . . . . . . 1939.1 Implementation of the Half-Edge Data Structure . . . . . . . . . . . . 1949.2 The Overall Design and the Adaptation Layer . . . . . . . . . . . . . . . 1979.3 Topological Queries and the Dart Class . . . . . . . . . . . . . . . . . . . . 1999.4 Some Iterator Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2039.5 Geometric Queries and the Traits Class . . . . . . . . . . . . . . . . . . . . 2059.6 Geometric and Topological Modifiers . . . . . . . . . . . . . . . . . . . . . . . 2119.7 Generic Delaunay Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 2139.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229


飞网下载站，免费下载共享资料，内容涉及教育资源、专业资料、IT资源、娱乐生活、经济管理、办公文书、游戏资料等。