Effective Computational Geometry for Curves and SurfacesJean-Daniel Boissonnat, Monique Teillaud Springer Science & Business Media, 24 באוק׳ 2006 - 344 עמודים Computational geometry emerged as a discipline in the seventies and has had considerable success in improving the asymptotic complexity of the solutions tobasicgeometricproblemsincludingconstructionsofdatastructures,convex hulls, triangulations, Voronoi diagrams and geometric arrangements as well as geometric optimisation. However, in the mid-nineties, it was recognized that the computational geometry techniques were far from satisfactory in practice and a vigorous e?ort has been undertaken to make computational geometry more practical. This e?ort led to major advances in robustness, geometric software engineering and experimental studies, and to the development of a large library of computational geometry algorithms, Cgal. The goal of this book is to take into consideration the multidisciplinary nature of the problem and to provide solid mathematical and algorithmic foundationsfore?ectivecomputationalgeometryforcurvesandsurfaces. This book covers two main approaches. In a ?rst part, we discuss exact geometric algorithms for curves and s- faces. We revisit two prominent data structures of computational geometry, namely arrangements (Chap. 1) and Voronoi diagrams (Chap. 2) in order to understand how these structures, which are well-known for linear objects, behave when de?ned on curved objects. The mathematical properties of these structures are presented together with algorithms for their construction. To ensure the e?ectiveness of our algorithms, the basic numerical computations that need to be performed are precisely speci?ed, and tradeo?s are considered between the complexity of the algorithms (i. e. the number of primitive calls), and the complexity of the primitives and their numerical stability. Chap. |
תוכן
| 1 | |
| 4 | |
Curved Voronoi Diagrams | 67 |
Algebraic Issues in Computational Geometry | 117 |
Differential Geometry on Discrete Surfaces | 156 |
Meshing of Surfaces | 181 |
Delaunay Triangulation Based Surface Reconstruction | 230 |
7 | 277 |
Appendix Generic Programming and The CGAL Library | 313 |
References | 321 |
20 | 322 |
| 338 | |
| 341 | |
מהדורות אחרות - הצג הכל
מונחים וביטויים נפוצים
algebraic numbers algorithm Apollonius diagram approximation arrangement Betti numbers bisectors Boissonnat bound boundary Cgal coefficients combinatorial component Computational Geometry conic connected convex coordinates critical points curvature curve data structures defined definition Delaunay triangulation denote dimension distance functions edges endpoints equation Euclidean Voronoi diagram example finite function f geometric graph Hausdorff distance homeomorphic homotopy hyperplane hyperspheres implementation input insert intersection points interval arithmetic isolating interval isotopy Lemma linear manifold medial axis mesh minimization diagram Möbius diagram Morse function normal objects operations oriented planar polygon polynomial power diagram predicates problem projection radius real roots region restricted Delaunay triangulation result sample points Sect simplicial complex singular points slab points smooth surface space sphere stable manifolds Sturm sequence subset surface reconstruction tangent plane Theorem torus traits class vector vertex vertices Voronoi cell Voronoi diagram x-coordinates x-critical x-monotone