CGAL User and Reference Manual
Table of Contents


Title Page Bibliography
Package Overview Index
Table of Contents Short Table of Contents


I   General Introduction

1   General Introduction
   1.1 License Issues
   1.2 Third Party Software
   1.3 Advanced
   1.4 Namespace CGAL
   1.5 Inclusion Order of Header Files
   1.6 Compile-time Flags to Control Inlining
   1.7 Checks


II   Kernels

2   2D and 3D Kernel
     User Manual
   2.1 Introduction
   2.2 Kernel Representations
   2.3 Kernel Geometry
   2.4 Predicates and Constructions
   2.5 Extensible Kernel
   2.6 Kernel Related Tools

 
  Reference Manual
2.7 Concepts
2.8 Kernel Classes and Operations
2.9 Predefined Kernels
2.10 Kernel Objects
2.11 Constants and Enumerations
2.12 Global Functions
2.13 Kernel Function Object Concepts
2.14 Tag Classes

3   dD Kernel
     User Manual
   3.1 Introduction
   3.2 Kernel Representations
   3.3 Kernel Geometry
   3.4 Predicates and Constructions

 
  Reference Manual
3.5 Linear Algebra Concepts and Classes
3.6 Kernel Objects
3.7 Global Kernel Functions
3.8 Kernel Concept

4   2D Circular Kernel
     User Manual
   4.1 Introduction
   4.2 Software Design
   4.3 Examples
   4.4 Design and Implementation History

 
  Reference Manual
4.5 Geometric Concepts
4.6 Algebraic Concepts
4.7 Geometric Kernels and Classes
4.8 Algebraic Kernel and Classes
4.9 Traits Classes for CGAL Arrangements
4.10 Alphabetical List of Reference Pages


III   Convex Hull Algorithms

5   2D Convex Hulls and Extreme Points
     User Manual
   5.1 Introduction
   5.2 Convex Hull
   5.3 Example using Graham-Andrew's Algorithm
   5.4 Extreme Points and Hull Subsequences
   5.5 Traits Classes
   5.6 Convexity Checking

 
  Reference Manual
5.7 Classified Reference Pages
5.8 Alphabetical List of Reference Pages

6   3D Convex Hulls
     User Manual
   6.1 Introduction
   6.2 Static Convex Hull Construction
   6.3 Incremental Convex Hull Construction
   6.4 Dynamic Convex Hull Construction

 
  Reference Manual
6.5 Classified Reference Pages
6.6 Alphabetical List of Reference Pages

7   dD Convex Hulls and Delaunay Triangulations
     User Manual
   7.1 Introduction
   7.2 dD Convex Hull
   7.3 Delaunay Triangulation

 
  Reference Manual
7.4 Classified Reference Pages
7.5 Alphabetical List of Reference Pages


IV   Polygons and Polyhedra

8   2D Polygons
     User Manual
   8.1 Introduction
   8.2 Example

 
  Reference Manual
8.3 Classified Reference Pages
8.4 Alphabetical List of Reference Pages

9   2D Polygon Partitioning
     User Manual
   9.1 Introduction
   9.2 Monotone Partitioning
   9.3 Convex Partitioning

 
  Reference Manual
9.4 Classified Reference Pages
9.5 Alphabetical List of Reference Pages

10   3D Polyhedral Surfaces
     User Manual
   10.1 Introduction
   10.2 Definition
   10.3 Example Programs
   10.4 File I/O
   10.5 Extending Vertices, Halfedges, and Facets
   10.6 Advanced Example Programs

 
  Reference Manual
10.7 Classified Reference Pages
10.8 Alphabetical List of Reference Pages

11   Halfedge Data Structures
     User Manual
   11.1 Introduction
   11.2 Software Design
   11.3 Example Programs

 
  Reference Manual
11.4 Classified Reference Pages
11.5 Alphabetical List of Reference Pages


V   Polygon and Polyhedron Operations

12   2D Regularized Boolean Set-Operations
     User Manual
   12.1 Introduction
   12.2 Boolean Set-Operations on Linear Polygons
   12.3 Boolean Set-Operations on General Polygons

 
  Reference Manual
12.4 Classified Reference Pages
12.5 Alphabetical List of Reference Pages

13   2D Boolean Operations on Nef Polygons
     User Manual
   13.1 Introduction
   13.2 Construction and Composition
   13.3 Exploration
   13.4 Traits Classes
   13.5 Implementation

 
  Reference Manual
13.6 Classified Reference Pages
13.7 Alphabetical List of Reference Pages

14   2D Boolean Operations on Nef Polygons Embedded on the Sphere
     User Manual
   14.1 Introduction
   14.2 Restricted Spherical Geometry
   14.3 Example Programs

 
  Reference Manual
14.4 Classified Reference Pages
14.5 Alphabetical List of Reference Pages

15   3D Boolean Operations on Nef Polyhedra
     User Manual
   15.1 Introduction
   15.2 Definition
   15.3 Infimaximal Box
   15.4 Regularized Set Operations
   15.5 Example Programs
   15.6 File I/O
   15.7 Further Example Programs
   15.8 Visualization

 
  Reference Manual
15.9 Classified Reference Pages
15.10 Alphabetical List of Reference Pages

16   2D Straight Skeleton and Polygon Offsetting
     User Manual
   16.1 Definitions
   16.2 Representation
   16.3 API
   16.4 Straight Skeletons, Medial Axis and Voronoi Diagrams
   16.5 Usages of the Straight Skeletons
   16.6 Straight Skeleton of a General Figure in the Plane

 
  Reference Manual
16.7 Classified Reference Pages
16.8 Alphabetical List of Reference Pages


VI   Arrangements

17   2D Arrangements
     User Manual
   17.1 Introduction
   17.2 The Main Arrangement Class
   17.3 Issuing Queries on an Arrangement
   17.4 Free Functions in the Arrangement Package
   17.5 Traits Classes
   17.6 The Notification Mechanism
   17.7 Extending the DCEL
   17.8 Overlaying Arrangements
   17.9 Storing the Curve History
   17.10 Input/Output Functions
   17.11 Adapting to BOOST Graphs
   17.12 How To Speed Up Your Computation

 
  Reference Manual
17.13 Classified Reference Pages
17.14 Alphabetical List of Reference Pages

18   2D Intersection of Curves
     User Manual
   18.1 Introduction

 
  Reference Manual
18.2 Alphabetical List of Reference Pages

19   2D Snap Rounding
     User Manual
   19.1 Introduction
   19.2 What is Snap Rounding/Iterated Snap Rounding
   19.3 Terms and Software Design
   19.4 Four Line Segment Example

 
  Reference Manual
19.5 Alphabetical List of Reference Pages


VII   Triangulations and Delaunay Triangulations

20   2D Triangulations
     User Manual
   20.1 Definitions
   20.2 Representation
   20.3 Software Design
   20.4 Basic Triangulations
   20.5 Delaunay Triangulations
   20.6 Regular Triangulations
   20.7 Constrained Triangulations
   20.8 Constrained Delaunay Triangulations
   20.9 Constrained Triangulations Plus
   20.10 The Triangulation Hierarchy
   20.11 Flexibility: Using Customized Vertices and Faces
   20.12 Design and Implementation History

 
  Reference Manual
20.13 Classified Reference Pages
20.14 Alphabetical List of Reference Pages

21   2D Triangulation Data Structure
     User Manual
   21.1 Definition
   21.2 The Concept of Triangulation Data Structure
   21.3 The Default Triangulation Data Structure

 
  Reference Manual
21.4 Classified Reference Pages
21.5 Alphabetical List of Reference Pages

22   3D Triangulations
     User Manual
   22.1 Representation
   22.2 Delaunay Triangulation
   22.3 Regular Triangulation
   22.4 Triangulation Hierarchy
   22.5 Software Design
   22.6 Examples
   22.7 Design and Implementation History

 
  Reference Manual
22.8 Classified Reference Pages
22.9 Alphabetical List of Reference Pages

23   3D Triangulation Data Structure
     User Manual
   23.1 Representation
   23.2 Software Design
   23.3 Examples
   23.4 Design and Implementation History

 
  Reference Manual
23.5 Classified Reference Pages
23.6 Alphabetical List of Reference Pages

24   2D Alpha Shapes
     User Manual
   24.1 Definitions
   24.2 Functionality
   24.3 Concepts and Models
   24.4 Examples

 
  Reference Manual
24.5 Classified Reference Pages
24.6 Alphabetical List of Reference Pages

25   3D Alpha Shapes
     User Manual
   25.1 Definitions
   25.2 Functionality
   25.3 Concepts and Models
   25.4 Examples

 
  Reference Manual
25.5 Classified Reference Pages
25.6 Alphabetical List of Reference Pages


VIII   Voronoi Diagrams

26   2D Segment Delaunay Graphs
     User Manual
   26.1 Definitions
   26.2 Software Design
   26.3 The Geometric Traits
   26.4 The Segment Delaunay Graph Hierarchy
   26.5 Examples

 
  Reference Manual
26.6 Classified Reference Pages
26.7 Alphabetical List of Reference Pages

27   2D Apollonius Graphs (Delaunay Graphs of Disks)
     User Manual
   27.1 Definitions
   27.2 Software Design
   27.3 The Geometric Traits
   27.4 The Apollonius Graph Hierarchy
   27.5 Examples

 
  Reference Manual
27.6 Classified Reference Pages
27.7 Alphabetical List of Reference Pages

28   2D Voronoi Diagram Adaptor
     User Manual
   28.1 Introduction
   28.2 Software Design
   28.3 The Adaptation Traits
   28.4 The Adaptation Policy
   28.5 Examples

 
  Reference Manual
28.6 Classified Reference Pages
28.7 Alphabetical List of Reference Pages


IX   Meshing

29   2D Conforming Triangulations and Meshes
     User Manual
   29.1 Conforming Triangulations
   29.2 Meshes

 
  Reference Manual
29.3 Classified Reference Pages
29.4 Alphabetical List of Reference Pages

30   3D Surface Mesher
     User Manual
   30.1 Introduction
   30.2 The Surface Mesher Interface
   30.3 Examples
   30.4 Meshing Criteria, Guarantees and Variations
   30.5 Design and Implementation History

 
  Reference Manual
30.6 Classified Reference Pages
30.7 Alphabetical List of Reference Pages

31   3D Surface Subdivision Methods
     User Manual
   31.1 Introduction
   31.2 Subdivision Method
   31.3 A Quick Example: Catmull-Clark Subdivision
   31.4 Catmull-Clark Subdivision
   31.5 Refinement Host
   31.6 Geometry Policy
   31.7 The Four Subdivision Methods
   31.8 Other Subdivision Methods

 
  Reference Manual
31.9 Classified Reference Pages
31.10 Alphabetical List of Reference Pages

32   Planar Parameterization of Triangulated Surface Meshes
     User Manual
   32.1 Introduction
   32.2 Basics
   32.3 Surface Parameterization Methods
   32.4 Sparse Linear Algebra
   32.5 Cutting a Mesh
   32.6 Output
   32.7 Complexity and Guarantees
   32.8 Software Design
   32.9 Extending the Package and Reusing Code

 
  Reference Manual
32.10 Classified Reference Pages
32.11 Alphabetical List of Reference Pages


X   Search Structures

33   2D Search Structures
     User Manual
   33.1 Introduction
   33.2 Examples

 
  Reference Manual
33.3 Classified Reference Pages
33.4 Alphabetical List of Reference Pages

34   Interval Skip List
     User Manual
   34.1 Definition
   34.2 Example Programs

 
  Reference Manual
34.3 Classified Reference Pages
34.4 Alphabetical List of Reference Pages

35   dD Spatial Searching
     User Manual
   35.1 Introduction
   35.2 Splitting Rules
   35.3 Example Programs
   35.4 Software Design

 
  Reference Manual
35.5 Classified Reference Pages
35.6 Alphabetical List of Reference Pages

36   dD Range and Segment Trees
     User Manual
   36.1 Introduction
   36.2 Definitions
   36.3 Software Design
   36.4 Creating an Arbitrary Multilayer Tree
   36.5 Range Trees
   36.6 Segment Trees

 
  Reference Manual
36.7 Classified Reference Pages
36.8 Alphabetical List of Reference Pages

37   Intersecting Sequences of dD Iso-oriented Boxes
     User Manual
   37.1 Introduction
   37.2 Definition
   37.3 Software Design
   37.4 Minimal Example for Intersecting Boxes
   37.5 Example for Finding Intersecting 3D Triangles
   37.6 Example for Using Pointers to Boxes
   37.7 Example Using the topology and the cutoff Parameters
   37.8 Runtime Performance
   37.9 Example Using a Custom Box Implementation
   37.10 Example for Point Proximity Search with a Custom Traits Class
   37.11 Design and Implementation History

 
  Reference Manual
37.12 Classified Reference Pages
37.13 Alphabetical List of Reference Pages


XI   Geometric Optimization

38   Geometric Optimization
     User Manual
   38.1 Bounding and Inscribed Volumes
   38.2 Optimal Distances
   38.3 Monotone and Sorted Matrix Search

 
  Reference Manual
38.4 Classified References Pages
38.5 Alphabetical List of Reference Pages

39   Principal Component Analysis
     User Manual
   39.1 Examples

 
  Reference Manual
39.2 Classified Reference Pages
39.3 Alphabetical List of Reference Pages


XII   Interpolation

40   Interpolation
     User Manual
   40.1 Natural Neighbor Coordinates
   40.2 Surface Natural Neighbor Coordinates and Surface Neighbors
   40.3 Interpolation Methods

 
  Reference Manual
40.4 Classified Reference Pages
40.5 Alphabetical List of Reference Pages

41   2D Placement of Streamlines
     User Manual
   41.1 Definitions
   41.2 Fundamental Notions
   41.3 Farthest Point Seeding Strategy
   41.4 Implementation
   41.5 Examples

 
  Reference Manual
41.6 Classified Reference Pages
41.7 Alphabetical List of Reference Pages


XIII   Kinetic Data Structures

42   Kinetic Data Structures
     User Manual
   42.1 An Overview of Kinetic Data Structures and Sweep Algorithms
   42.2 An Overview of the Kinetic Framework
   42.3 Using Kinetic Data Structures

 
  Reference Manual
42.4 Classified Reference Pages
42.5 Alphabetical List of Reference Pages

43   Kinetic Framework
     User Manual
   43.1 Architecture
   43.2 Algebraic Kernel
   43.3 Examples

 
  Reference Manual
43.4 Classified Reference Pages
43.5 Alphabetical List of Reference Pages


XIV   Support Library

44   Number Type Support
     User Manual
   44.1 Required Functionality of Number Types
   44.2 Utility Routines
   44.3 Built-in Number Types
   44.4 Number Types Provided by CGAL
   44.5 Number Type Provided by CORE
   44.6 Number Types Provided by GMP
   44.7 Number Types Provided by LEDA
   44.8 User-supplied Number Types

 
  Reference Manual
44.9 Classified Reference Pages
44.10 Alphabetical List of Reference Pages

45   STL Extensions for CGAL
     User Manual
   45.1 Doubly-Connected List Managing Items in Place
   45.2 Compact Container
   45.3 Multiset with Extended Functionality

 
  Reference Manual
45.4 Classified Reference Pages
45.5 Alphabetical List of Reference Pages

46   Handles and Circulators
     User Manual
   46.1 Handles
   46.2 Circulators

 
  Reference Manual
46.3 Classified Reference Pages
46.4 Alphabetical List of Reference Pages

47   Geometric Object Generators
     User Manual
   47.1 Example Generating Degenerate Point Sets
   47.2 Example Generating Grid Points
   47.3 Examples Generating Segments

 
  Reference Manual
47.4 Classified Reference Pages
47.5 Alphabetical List of Reference Pages

48   Timers, Hash Map, Union-find, Modifiers
     User Manual
   48.1 Timers
   48.2 Memory Size
   48.3 Unique Hash Map
   48.4 Union-find
   48.5 Protected Access to Internal Representations

 
  Reference Manual
48.6 Classified Reference Pages
48.7 Alphabetical List of Reference Pages

49   IO Streams
     User Manual
   49.1 Output Operator
   49.2 Input Operator
   49.3 Stream Support

 
  Reference Manual
49.4 Classified Reference Pages
49.5 Alphabetical List of Reference Pages

50   IO Streams Colors
     User Manual
   50.1 Colors

 
  Reference Manual
50.2 Colors

51   Geomview
     User Manual
   51.1 Definition
   51.2 Implementation
   51.3 Example

 
  Reference Manual
51.4 Alphabetical List of Reference Pages

52   Qt_widget
     User Manual
   52.1 Introduction
   52.2 Qt_widget
   52.3 Layers
   52.4 The Standard Toolbar
   52.5 The Help Window
   52.6 Some Predefined Icons
   52.7 What Shall I Use?

 
  Reference Manual
52.8 Classified Reference Pages
52.9 Alphabetical List of Reference Pages