logo资料库

CGAL手册（计算机几何学）†Œ.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：29.90M 资料格式：pdf 举报 版权申诉
第1页 / 共4126页
第2页 / 共4126页
第3页 / 共4126页
第4页 / 共4126页
第5页 / 共4126页
第6页 / 共4126页
第7页 / 共4126页
第8页 / 共4126页
资料共4126页，剩余部分请下载后查看
    I General Introduction
    1 Introduction
    1.1 Organization of the Manual
    1.2 Demos and Examples
    1.3 Hello World
    1.4 Further Reading
    Reference Manual
    2 Preliminaries
    2.1 License Issues
    2.2 Third Party Software
    2.3 Marking of Advanced Features
    2.4 Namespace CGAL
    2.5 Inclusion Order of Header Files
    2.6 Compile-time Flags to Control Inlining
    2.7 Identifying the Version of CGAL
    2.8 Thread Safety
    2.9 Code Deprecation
    2.10 Checks
    Reference Manual
    II Arithmetic and Algebra
    3 Algebraic Foundations
    3.1 Introduction
    3.2 Algebraic Structures
    3.3 Real Embeddable
    3.4 Real Number Types
    3.5 Interoperability
    3.6 Fractions
    Reference Manual
    3.7 Classified Reference Pages
    3.8 Alphabetical List of Reference Pages
    4 Number Types
    4.1 Introduction
    4.2 Built-in Number Types
    4.3 Number Types Provided by CGAL
    4.4 Number Types Provided by GMP
    4.5 Number Types Provided by LEDA
    4.6 Number Types Provided by CORE
    4.7 User-supplied Number Types
    Reference Manual
    4.8 Classified Reference Pages
    4.9 Alphabetical List of Reference Pages
    5 Polynomial
    5.1 Fundamentals
    5.2 General Design
    5.3 Constructing a multivariate polynomial
    5.4 Coefficient Access
    5.5 Degree, total degree and degree vector
    5.6 Changing the order of variables
    5.7 GCD and More
    5.8 Evaluation and Substitution
    5.9 Resultants, Subresultants and Sturm-Habicht sequences
    5.10 Design and Implementation History
    Reference Manual
    5.11 Classified Reference Pages
    5.12 Alphabetical List of Reference Pages
    6 Modular Arithmetic
    6.1 Introduction
    6.2 Design and Implementation History
    Reference Manual
    6.3 Classified Reference Pages
    6.4 Alphabetical List of Reference Pages
    III Combinatorial Algorithms
    7 Monotone and Sorted Matrix Search
    Reference Manual
    7.1 Classified References Pages
    7.2 Alphabetical List of Reference Pages
    8 Linear and Quadratic Programming Solver
    8.1 Which Programs can be Solved?
    8.2 Design, Efficiency, and Robustness
    8.3 How to Enter and Solve a Program
    8.4 Solving Linear and Nonnegative Programs
    8.5 Working from Iterators
    8.6 Important Variables and Constraints
    8.7 Solution Certificates
    8.8 Customizing the Solver
    8.9 Some Benchmarks for Convex Hull Containment
    Reference Manual
    8.10 Classified Reference Pages
    8.11 Alphabetical List of Reference Pages
    IV Geometry Kernels
    9 2D and 3D Geometry Kernel
    9.1 Introduction
    9.2 Kernel Representations
    9.3 Kernel Geometry
    9.4 Predicates and Constructions
    9.5 Extensible Kernel
    9.6 Design and Implementation History
    Reference Manual
    9.7 Concepts
    9.8 Kernel Classes and Operations
    9.9 Predefined Kernels
    9.10 Kernel Objects
    9.11 Constants and Enumerations
    9.12 Global Functions
    9.13 Kernel Geometric Object Concepts
    9.14 Kernel Function Object Concepts
    9.15 Dimension handling tools
    10 dD Geometry Kernel
    10.1 Introduction
    10.2 Kernel Representations
    10.3 Kernel Geometry
    10.4 Predicates and Constructions
    10.5 Design and Implementation History
    Reference Manual
    10.6 Linear Algebra Concepts and Classes
    10.7 Kernels
    10.8 Kernel Objects
    10.9 Global Kernel Functions
    10.10 Kernel Concept
    11 2D Circular Geometry Kernel
    11.1 Introduction
    11.2 Software Design
    11.3 Examples
    11.4 Design and Implementation History
    Reference Manual
    11.5 Geometric Concepts
    11.6 Geometric Kernels and Classes
    11.7 Geometric Global Functions
    11.8 Algebraic Concepts
    11.9 Algebraic Kernel and Classes
    11.10 Alphabetical List of Reference Pages
    12 3D Spherical Geometry Kernel
    12.1 Introduction
    12.2 Spherical Kernel Objects
    12.3 Software Design
    12.4 Examples
    12.5 Design and Implementation History
    Reference Manual
    12.6 Geometric Concepts
    12.7 Geometric Kernels and Classes
    12.8 Geometric Global Functions
    12.9 Algebraic Concepts
    12.10 Algebraic Kernel and Classes
    12.11 Alphabetical List of Reference Pages
    V Convex Hull Algorithms
    13 2D Convex Hulls and Extreme Points
    13.1 Introduction
    13.2 Convex Hull
    13.3 Example using Graham-Andrew's Algorithm
    13.4 Extreme Points and Hull Subsequences
    13.5 Traits Classes
    13.6 Convexity Checking
    Reference Manual
    13.7 Classified Reference Pages
    13.8 Alphabetical List of Reference Pages
    14 3D Convex Hulls
    14.1 Introduction
    14.2 Static Convex Hull Construction
    14.3 Incremental Convex Hull Construction
    14.4 Dynamic Convex Hull Construction
    Reference Manual
    14.5 Classified Reference Pages
    14.6 Alphabetical List of Reference Pages
    15 dD Convex Hulls and Delaunay Triangulations
    15.1 Introduction
    15.2 dD Convex Hull
    15.3 Delaunay Triangulation
    Reference Manual
    15.4 Classified Reference Pages
    15.5 Alphabetical List of Reference Pages
    VI Polygons
    16 2D Polygons
    16.1 Introduction
    16.2 Example
    Reference Manual
    16.3 Classified Reference Pages
    16.4 Alphabetical List of Reference Pages
    17 2D Regularized Boolean Set-Operations
    17.1 Introduction
    17.2 Terms and Definitions
    17.3 Boolean Set-Operations on Linear Polygons
    17.4 Boolean Set-Operations on General Polygons
    Reference Manual
    17.5 Classified Reference Pages
    17.6 Alphabetical List of Reference Pages
    18 2D Boolean Operations on Nef Polygons
    18.1 Introduction
    18.2 Construction and Composition
    18.3 Exploration
    18.4 Traits Classes
    18.5 Implementation
    Reference Manual
    18.6 Classified Reference Pages
    18.7 Alphabetical List of Reference Pages
    19 2D Boolean Operations on Nef Polygons Embedded on the Sphere
    19.1 Introduction
    19.2 Restricted Spherical Geometry
    19.3 Example Programs
    Reference Manual
    19.4 Classified Reference Pages
    19.5 Alphabetical List of Reference Pages
    20 2D Polygon Partitioning
    20.1 Introduction
    20.2 Monotone Partitioning
    20.3 Convex Partitioning
    Reference Manual
    20.4 Classified Reference Pages
    20.5 Alphabetical List of Reference Pages
    21 2D Straight Skeleton and Polygon Offsetting
    21.1 Definitions
    21.2 Representation
    21.3 API
    21.4 Straight Skeletons, Medial Axis and Voronoi Diagrams
    21.5 Usages of the Straight Skeletons
    21.6 Straight Skeleton of a General Figure in the Plane
    Reference Manual
    21.7 Classified Reference Pages
    21.8 Alphabetical List of Reference Pages
    22 2D Minkowski Sums
    22.1 Introduction
    22.2 Computing the Minkowski Sum of Two Polygons
    22.3 Offsetting a Polygon
    Reference Manual
    22.4 Alphabetical List of Reference Pages
    VII Polyhedra
    23 3D Polyhedral Surfaces
    23.1 Introduction
    23.2 Definition
    23.3 Example Programs
    23.4 File I/O
    23.5 Extending Vertices, Halfedges, and Facets
    23.6 Advanced Example Programs
    Reference Manual
    23.7 Classified Reference Pages
    23.8 Alphabetical List of Reference Pages
    24 Halfedge Data Structures
    24.1 Introduction
    24.2 Software Design
    24.3 Example Programs
    Reference Manual
    24.4 Classified Reference Pages
    24.5 Alphabetical List of Reference Pages
    25 3D Boolean Operations on Nef Polyhedra
    25.1 Introduction
    25.2 Definition
    25.3 Infimaximal Box
    25.4 Regularized Set Operations
    25.5 Example Programs
    25.6 File I/O
    25.7 Further Example Programs
    25.8 Visualization
    Reference Manual
    25.9 Classified Reference Pages
    25.10 Alphabetical List of Reference Pages
    26 Convex Decomposition of Polyhedra
    26.1 Introduction
    26.2 Interface and Usage
    Reference Manual
    26.3 Classified Reference Pages
    26.4 Alphabetical List of Reference Pages
    27 3D Minkowski Sum of Polyhedra
    27.1 Introduction
    27.2 Decomposition Method
    27.3 Features and Restrictions
    27.4 Usage
    27.5 Glide
    Reference Manual
    27.6 Classified Reference Pages
    27.7 Alphabetical List of Reference Pages
    VIII Arrangements
    28 2D Arrangements
    28.1 Introduction
    28.2 The Main Arrangement Class
    28.3 Issuing Queries on an Arrangement
    28.4 Free Functions in the Arrangement Package
    28.5 Arrangements of Unbounded Curves
    28.6 Traits Classes
    28.7 The Notification Mechanism
    28.8 Extending the Dcel
    28.9 Overlaying Arrangements
    28.10 Storing the Curve History
    28.11 Input/Output Streams
    28.12 Adapting to Boost Graphs
    28.13 How To Speed Up Your Computation
    Reference Manual
    28.14 Classified Reference Pages
    28.15 Alphabetical List of Reference Pages
    29 2D Intersection of Curves
    29.1 Introduction
    29.2 Example
    29.3 Design and Implementation History
    Reference Manual
    29.4 Alphabetical List of Reference Pages
    30 2D Snap Rounding
    30.1 Introduction
    30.2 What is Snap Rounding/Iterated Snap Rounding
    30.3 Terms and Software Design
    30.4 Four Line Segment Example
    Reference Manual
    30.5 Alphabetical List of Reference Pages
    31 Envelopes of Curves in 2D
    31.1 Introduction
    31.2 The Envelope Diagram
    31.3 Examples
    Reference Manual
    31.4 Alphabetical List of Reference Pages
    32 Envelopes of Surfaces in 3D
    32.1 Introduction
    32.2 The Envelope-Traits Concept
    32.3 Examples
    Reference Manual
    32.4 Alphabetical List of Reference Pages
    IX Triangulations and Delaunay Triangulations
    33 2D Triangulations
    33.1 Definitions
    33.2 Representation
    33.3 Software Design
    33.4 Basic Triangulations
    33.5 Delaunay Triangulations
    33.6 Regular Triangulations
    33.7 Constrained Triangulations
    33.8 Constrained Delaunay Triangulations
    33.9 Constrained Triangulations Plus
    33.10 The Triangulation Hierarchy
    33.11 Flexibility: Using Customized Vertices and Faces
    33.12 Design and Implementation History
    Reference Manual
    33.13 Classified Reference Pages
    33.14 Alphabetical List of Reference Pages
    34 2D Triangulation Data Structure
    34.1 Definition
    34.2 The Concept of Triangulation Data Structure
    34.3 The Default Triangulation Data Structure
    Reference Manual
    34.4 Classified Reference Pages
    34.5 Alphabetical List of Reference Pages
    35 3D Triangulations
    35.1 Representation
    35.2 Delaunay Triangulation
    35.3 Regular Triangulation
    35.4 Triangulation Hierarchy
    35.5 Software Design
    35.6 Examples
    35.7 Design and Implementation History
    Reference Manual
    35.8 Classified Reference Pages
    35.9 Alphabetical List of Reference Pages
    36 3D Triangulation Data Structure
    36.1 Representation
    36.2 Software Design
    36.3 Examples
    36.4 Design and Implementation History
    Reference Manual
    36.5 Classified Reference Pages
    36.6 Alphabetical List of Reference Pages
    37 3D Periodic Triangulations
    37.1 The flat torus
    37.2 Representation
    37.3 Delaunay Triangulation
    37.4 Triangulation Hierarchy
    37.5 Software Design
    37.6 Examples
    37.7 Design and Implementation History
    Reference Manual
    37.8 Classified Reference Pages
    37.9 Alphabetical List of Reference Pages
    38 2D Alpha Shapes
    38.1 Definitions
    38.2 Functionality
    38.3 Concepts and Models
    38.4 Examples
    Reference Manual
    38.5 Classified Reference Pages
    38.6 Alphabetical List of Reference Pages
    39 3D Alpha Shapes
    39.1 Definitions
    39.2 Functionality
    39.3 Concepts and Models
    39.4 Examples
    Reference Manual
    39.5 Classified Reference Pages
    39.6 Alphabetical List of Reference Pages
    X Voronoi Diagrams
    40 2D Segment Delaunay Graphs
    40.1 Definitions
    40.2 Software Design
    40.3 The Geometric Traits
    40.4 The Segment Delaunay Graph Hierarchy
    40.5 Examples
    Reference Manual
    40.6 Classified Reference Pages
    40.7 Alphabetical List of Reference Pages
    41 2D Apollonius Graphs (Delaunay Graphs of Disks)
    41.1 Definitions
    41.2 Software Design
    41.3 The Geometric Traits
    41.4 The Apollonius Graph Hierarchy
    41.5 Examples
    Reference Manual
    41.6 Classified Reference Pages
    41.7 Alphabetical List of Reference Pages
    42 2D Voronoi Diagram Adaptor
    42.1 Introduction
    42.2 Software Design
    42.3 The Adaptation Traits
    42.4 The Adaptation Policy
    42.5 Examples
    Reference Manual
    42.6 Classified Reference Pages
    42.7 Alphabetical List of Reference Pages
    XI Mesh Generation
    43 2D Conforming Triangulations and Meshes
    43.1 Conforming Triangulations
    43.2 Meshes
    Reference Manual
    43.3 Classified Reference Pages
    43.4 Alphabetical List of Reference Pages
    44 3D Surface Mesh Generation
    44.1 Introduction
    44.2 The Surface Mesh Generator Interface for Smooth Surfaces
    44.3 Examples
    44.4 Meshing Criteria, Guarantees and Variations
    44.5 Output
    44.6 Undocumented Features Available in Demos
    44.7 Design and Implementation History
    Reference Manual
    44.8 Classified Reference Pages
    44.9 Alphabetical List of Reference Pages
    45 Surface Reconstruction from Point Sets
    45.1 Introduction
    45.2 Common Reconstruction Pipeline
    45.3 Poisson
    45.4 Contouring
    45.5 Output
    45.6 Case Studies
    45.7 Performances
    Reference Manual
    45.8 Classified Reference Pages
    45.9 Alphabetical List of Reference Pages
    46 3D Skin Surface Meshing
    46.1 Introduction
    46.2 Definition of a Skin Surface
    46.3 The Interface
    46.4 Timings
    46.5 Example Programs
    Reference Manual
    46.6 Alphabetical List of Reference Pages
    47 3D Mesh Generation
    47.1 Introduction
    47.2 Interface
    47.3 Examples
    Reference Manual
    47.4 Classified Reference Pages
    47.5 Alphabetical List of Reference Pages
    XII Geometry Processing
    48 3D Surface Subdivision Methods
    48.1 Introduction
    48.2 Subdivision Method
    48.3 A Quick Example: Catmull-Clark Subdivision
    48.4 Catmull-Clark Subdivision
    48.5 Refinement Host
    48.6 Geometry Policy
    48.7 The Four Subdivision Methods
    48.8 Other Subdivision Methods
    Reference Manual
    48.9 Classified Reference Pages
    48.10 Alphabetical List of Reference Pages
    49 Triangulated Surface Mesh Simplification
    49.1 Introduction
    49.2 Overview of the Simplification Process
    49.3 Cost Strategy
    49.4 API
    Reference Manual
    49.5 Classified Reference Pages
    49.6 Alphabetical List of Reference Pages
    50 Planar Parameterization of Triangulated Surface Meshes
    50.1 Introduction
    50.2 Basics
    50.3 Surface Parameterization Methods
    50.4 Sparse Linear Algebra
    50.5 Cutting a Mesh
    50.6 Output
    50.7 Complexity and Guarantees
    50.8 Software Design
    50.9 Extending the Package and Reusing Code
    Reference Manual
    50.10 Classified Reference Pages
    50.11 Alphabetical List of Reference Pages
    51 2D Placement of Streamlines
    51.1 Definitions
    51.2 Fundamental Notions
    51.3 Farthest Point Seeding Strategy
    51.4 Implementation
    51.5 Examples
    Reference Manual
    51.6 Classified Reference Pages
    51.7 Alphabetical List of Reference Pages
    52 Approximation of Ridges and Umbilics on Triangulated Surface Meshes
    52.1 Ridges and Umbilics of a Smooth Surface
    52.2 Approximating Ridges on Triangulated Surface Meshes
    52.3 Approximating Umbilics on Triangulated Surface Meshes
    52.4 Software Design
    52.5 Examples
    Reference Manual
    52.6 Alphabetical List of Reference Pages
    53 Estimation of Local Differential Properties
    53.1 Introduction
    53.2 Software Design
    53.3 Examples
    53.4 Mathematical and Algorithmic Details
    Reference Manual
    53.5 Alphabetical List of Reference Pages
    54 Point Set Processing
    54.1 Introduction
    54.2 Input/Output
    54.3 Analysis
    54.4 Outlier Removal
    54.5 Simplification
    54.6 Smoothing
    54.7 Normal Estimation
    54.8 Normal Orientation
    Reference Manual
    54.9 Classified Reference Pages
    54.10 Alphabetical List of Reference Pages
    XIII Spatial Searching and Sorting
    55 2D Range and Neighbor Search
    55.1 Introduction
    55.2 Example: Range Search
    Reference Manual
    55.3 Classified Reference Pages
    55.4 Alphabetical List of Reference Pages
    56 Interval Skip List
    56.1 Definition
    56.2 Example Programs
    Reference Manual
    56.3 Classified Reference Pages
    56.4 Alphabetical List of Reference Pages
    57 dD Spatial Searching
    57.1 Introduction
    57.2 Splitting Rules
    57.3 Example Programs
    57.4 Software Design
    Reference Manual
    57.5 Classified Reference Pages
    57.6 Alphabetical List of Reference Pages
    58 dD Range and Segment Trees
    58.1 Introduction
    58.2 Definitions
    58.3 Software Design
    58.4 Creating an Arbitrary Multilayer Tree
    58.5 Range Trees
    58.6 Segment Trees
    Reference Manual
    58.7 Classified Reference Pages
    58.8 Alphabetical List of Reference Pages
    59 Intersecting Sequences of dD Iso-oriented Boxes
    59.1 Introduction
    59.2 Definition
    59.3 Software Design
    59.4 Minimal Example for Intersecting Boxes
    59.5 Example for Finding Intersecting 3D Triangles
    59.6 Example for Using Pointers to Boxes
    59.7 Example Using the topology and the cutoff Parameters
    59.8 Runtime Performance
    59.9 Example Using a Custom Box Implementation
    59.10 Example for Point Proximity Search with a Custom Traits Class
    59.11 Design and Implementation History
    Reference Manual
    59.12 Classified Reference Pages
    59.13 Alphabetical List of Reference Pages
    60 AABB Tree
    60.1 Introduction
    60.2 Interface
    60.3 Examples
    60.4 Performances
    60.5 Implementation Details
    60.6 Design and Implementation History
    Reference Manual
    60.7 Classified Reference Pages
    60.8 Alphabetical List of Reference Pages
    61 Spatial Sorting
    61.1 Introduction
    61.2 Spatial Sorting
    Reference Manual
    61.3 Alphabetical List of Reference Pages
    XIV Geometric Optimization
    62 Bounding Volumes
    Reference Manual
    62.1 Classified References Pages
    62.2 Alphabetical List of Reference Pages
    63 Inscribed Areas
    Reference Manual
    63.1 Classified References Pages
    63.2 Alphabetical List of Reference Pages
    64 Optimal Distances
    Reference Manual
    64.1 Classified References Pages
    64.2 Alphabetical List of Reference Pages
    65 Principal Component Analysis
    65.1 Definitions
    65.2 Examples
    Reference Manual
    65.3 Classified Reference Pages
    65.4 Alphabetical List of Reference Pages
    XV Interpolation
    66 2D and Surface Function Interpolation
    66.1 Natural Neighbor Coordinates
    66.2 Surface Natural Neighbor Coordinates and Surface Neighbors
    66.3 Interpolation Methods
    Reference Manual
    66.4 Classified Reference Pages
    66.5 Alphabetical List of Reference Pages
    XVI Kinetic Data Structures
    67 Kinetic Data Structures
    67.1 Quick Hints
    67.2 An Overview of Kinetic Data Structures and Sweep Algorithms
    67.3 An Overview of the Kinetic Framework
    67.4 Using Kinetic Data Structures
    Reference Manual
    67.5 Classified Reference Pages
    67.6 Alphabetical List of Reference Pages
    68 Kinetic Framework
    68.1 Architecture
    68.2 Algebraic Kernel
    68.3 Examples
    Reference Manual
    68.4 Classified Reference Pages
    68.5 Alphabetical List of Reference Pages
    XVII Support Library
    69 STL Extensions for CGAL
    69.1 Doubly-Connected List Managing Items in Place
    69.2 Compact Container
    69.3 Multiset with Extended Functionality
    69.4 Polymorphic Object
    69.5 Uncertainty Management
    69.6 Default types in template arguments lists
    Reference Manual
    69.7 Classified Reference Pages
    69.8 Alphabetical List of Reference Pages
    70 CGAL and the Boost Graph Library
    70.1 A Short Introduction to the Boost Graph Library
    70.2 Extensions of the BGL
    70.3 Header Files, Namespaces, and Naming Conventions
    70.4 Polyhedral Surfaces as Model of the Boost Graph Concept
    70.5 Triangulations as Models of the Boost Graph Concept
    70.6 Arrangements as Models of the Boost Graph Concept
    Reference Manual
    70.7 Classified Reference Pages
    70.8 Alphabetical List of Reference Pages
    71 CGAL and Boost Property Maps
    71.1 A Short Introduction to the Boost Property Maps Library
    71.2 CGAL and Boost Property Maps
    Reference Manual
    71.3 Classified Reference Pages
    71.4 Alphabetical List of Reference Pages
    72 Handles and Circulators
    72.1 Handles
    72.2 Circulators
    Reference Manual
    72.3 Classified Reference Pages
    72.4 Alphabetical List of Reference Pages
    73 Geometric Object Generators
    73.1 Introduction
    73.2 Example Generating Degenerate Point Sets
    73.3 Example Generating Grid Points
    73.4 Examples Generating Segments
    Reference Manual
    73.5 Classified Reference Pages
    73.6 Alphabetical List of Reference Pages
    74 Profiling tools, Hash Map, Union-find, Modifiers
    74.1 Timers
    74.2 Memory Size
    74.3 Profiling
    74.4 Unique Hash Map
    74.5 Union-find
    74.6 Protected Access to Internal Representations
    Reference Manual
    74.7 Classified Reference Pages
    74.8 Alphabetical List of Reference Pages
    75 IO Streams
    75.1 Output Operator
    75.2 Input Operator
    75.3 IO for non-Cgal types
    75.4 Colors
    75.5 Stream Support
    Reference Manual
    75.6 Classified Reference Pages
    75.7 Alphabetical List of Reference Pages
    76 Geomview
    76.1 Definition
    76.2 Implementation
    76.3 Example
    Reference Manual
    76.4 Alphabetical List of Reference Pages
    77 CGAL and the Qt Graphics View Framework
    77.1 Introduction
    77.2 Overall Design
    Reference Manual
    77.3 Classified Reference Pages
    77.4 Alphabetical List of Reference Pages
    78 CGAL Ipelets
    78.1 Introduction
    78.2 CGAL Ipelets
    78.3 Example
    78.4 Installation of the Demo Ipelets
    78.5 Design and Implementation History
    Reference Manual
    78.6 Alphabetical List of Reference Pages
    Index
    User and Reference Manual: All Parts Release 3.5.1 19 December 2009 Built from 3.5.1-I-212
    Contents I General Introduction 1 Introduction 1.1 Organization of the Manual . 1.2 Demos and Examples . 1.3 Hello World . . . 1.4 Further Reading . . . Reference Manual . . . . . . . 2 Preliminaries 2.1 License Issues . . . . . 2.2 Third Party Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3 3 3 4 6 7 9 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Marking of Advanced Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Namespace CGAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5 Inclusion Order of Header Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.6 Compile-time Flags to Control Inlining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.7 Identifying the Version of CGAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.8 Thread Safety . . . 2.9 Code Deprecation . 2.10 Checks . . . . . . . Reference Manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 i
    II Arithmetic and Algebra 3 Algebraic Foundations 21 23 3.1 Introduction . . . . . 3.2 Algebraic Structures 3.3 Real Embeddable . . 3.4 Real Number Types . 3.5 Interoperability . 3.6 Fractions . . . . . . Reference Manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Classified Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.8 Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4 Number Types 123 4.1 Introduction . . . . . . . 4.2 Built-in Number Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.3 Number Types Provided by CGAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 4.4 Number Types Provided by GMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 4.5 Number Types Provided by LEDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.6 Number Types Provided by CORE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.7 User-supplied Number Types . Reference Manual . . . . . . 4.8 Classified Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.9 Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 5 Polynomial 187 5.1 Fundamentals . . 5.2 General Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 5.3 Constructing a multivariate polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 5.4 Coefficient Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 5.5 Degree, total degree and degree vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 ii
    5.6 Changing the order of variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 5.7 GCD and More . . . . . . . 5.8 Evaluation and Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 5.9 Resultants, Subresultants and Sturm-Habicht sequences . . . . . . . . . . . . . . . . . . . . . . 198 5.10 Design and Implementation History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 Reference Manual . . . . . . 5.11 Classified Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 5.12 Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 6 Modular Arithmetic 321 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 6.2 Design and Implementation History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 Reference Manual . . . . . . 6.3 Classified Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 6.4 Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 III Combinatorial Algorithms 7 Monotone and Sorted Matrix Search Reference Manual . . . . . . 7.1 Classified References Pages . . . . 333 335 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 7.2 Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 8 Linear and Quadratic Programming Solver 353 8.1 Which Programs can be Solved? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 8.2 Design, Efficiency, and Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 8.3 How to Enter and Solve a Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 8.4 Solving Linear and Nonnegative Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 8.5 Working from Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 8.6 Important Variables and Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368 8.7 Solution Certificates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 iii
    8.8 Customizing the Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 8.9 Some Benchmarks for Convex Hull Containment . . . . . . . . . . . . . . . . . . . . . . . . . 373 Reference Manual . . . . . . 8.10 Classified Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 8.11 Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 IV Geometry Kernels 9 2D and 3D Geometry Kernel 437 439 9.1 Introduction . . . . . . . 9.2 Kernel Representations . 9.3 Kernel Geometry . . . . . . . . . . . . . 9.4 Predicates and Constructions . 9.5 Extensible Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 9.6 Design and Implementation History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 Reference Manual . 9.7 Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 9.8 Kernel Classes and Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 9.9 Predefined Kernels 9.10 Kernel Objects . . . . . . . . . . . . . . 9.11 Constants and Enumerations . 9.12 Global Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559 9.13 Kernel Geometric Object Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649 9.14 Kernel Function Object Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674 9.15 Dimension handling tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906 10 dD Geometry Kernel 911 10.1 Introduction . . . . . . . 10.2 Kernel Representations . 10.3 Kernel Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915 iv
    10.4 Predicates and Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917 10.5 Design and Implementation History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918 Reference Manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 921 10.6 Linear Algebra Concepts and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923 10.7 Kernels . . . . 10.8 Kernel Objects . . . . . . . . . . 10.9 Global Kernel Functions 10.10Kernel Concept . . . . . 11 2D Circular Geometry Kernel 11.1 Introduction . . . 11.2 Software Design . 11.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 933 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 963 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985 1019 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1019 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1019 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1020 11.4 Design and Implementation History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1022 Reference Manual . . 11.5 Geometric Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1023 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1023 11.6 Geometric Kernels and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1024 11.7 Geometric Global Functions 11.8 Algebraic Concepts . . . . . . . 11.9 Algebraic Kernel and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1024 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1025 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1025 11.10Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1026 12 3D Spherical Geometry Kernel 1103 12.1 Introduction . . . . . . . . 12.2 Spherical Kernel Objects . 12.3 Software Design . 12.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1103 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1103 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1106 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1106 12.5 Design and Implementation History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1109 Reference Manual . . 12.6 Geometric Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1111 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1111 v
    12.7 Geometric Kernels and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1112 12.8 Geometric Global Functions 12.9 Algebraic Concepts . . . . . . . 12.10Algebraic Kernel and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1113 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1113 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1114 12.11Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1114 V Convex Hull Algorithms 13 2D Convex Hulls and Extreme Points 1209 1211 13.1 Introduction . 13.2 Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1211 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1212 13.3 Example using Graham-Andrew’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1212 13.4 Extreme Points and Hull Subsequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1213 13.5 Traits Classes . . . . 13.6 Convexity Checking . Reference Manual . . . . . . . . . . . . . . 13.7 Classified Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1213 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1214 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1215 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1215 13.8 Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1217 14 3D Convex Hulls 1257 14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1257 14.2 Static Convex Hull Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1258 14.3 Incremental Convex Hull Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1259 14.4 Dynamic Convex Hull Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1261 Reference Manual . . . . . . 14.5 Classified Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1263 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1263 14.6 Alphabetical List of Reference Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1265 15 dD Convex Hulls and Delaunay Triangulations 1283 15.1 Introduction . . . 15.2 dD Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1283 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1283 vi
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料