Reference Manual
Table of Contents

1. Title Page
2. Table of Contents
3. Preface
   • Editors
   • Authors
   • Acknowledgement
4. Introduction
   • Organisation of the manual
5. Polygon
   • Class declaration of CGAL_Polygon_2<Traits,Container>
   • Algorithms on sequences of 2D points
   • Polygon Traits class requirements
   • Class declaration of Traits
   • Class declaration of CGAL_Polygon_traits_2<R>
6. Halfedge Data Structures
   • Introduction
   • Requirements for a Halfedge_data_structure
   • Class declaration of Vertex
   • Class declaration of Halfedge
   • Class declaration of Facet
   • Models of Halfedge_data_structure
   • Class declaration of CGAL_Halfedge_data_structure_default<Point>
   • Class declaration of CGAL_Halfedge_data_structure_using_list<V,H,F>
   • Class declaration of CGAL_Halfedge_data_structure_using_vector<V,H,F>
   • Requirements for Vertex_base, Halfedge_base and Facet_base
   • Class declaration of Vertex_base
   • Class declaration of Halfedge_base
   • Class declaration of Facet_base
   • Models of Vertex_base, Halfedge_base and Facet_base
   • Decorator for Halfedge Data Structures
   • Examples of Halfedge Data Structures
7. 3D-Polyhedral Surfaces
   • Introduction
   • Class declaration of CGAL_Polyhedron_3<Traits,HDS>
   • Class declaration of Vertex
   • Class declaration of Halfedge
   • Class declaration of Facet
   • Requirements for a Polyhedron_traits
   • Models of Polyhedron_traits
   • Additional Requirements and a Default Model for a Halfedge_data_structure
   • Class declaration of CGAL_Halfedge_data_structure_polyhedron_default_3<R>
   • An Incremental Builder for Polyhedral Surfaces
   • Examples Using Polyhedral Surfaces
8. Topological Map
   • Introduction
   • Topological Map
   • Class declaration of CGAL_Topological_map<Dcel>
   • Class declaration of Vertex
   • Class declaration of Halfedge
   • Class declaration of Face
   • Class declaration of Ccb_halfedge_circulator
   • Class declaration of Halfedge_around_vertex_circulator
   • Requirements for the Topological Map's DCEL class
   • Class declaration of Dcel
   • Class declaration of Dcel::Vertex
   • Class declaration of Dcel::Halfedge
   • Class declaration of Dcel::Face
   • Predefined Interface Class
   • Class declaration of CGAL_Pm_dcel<V,H,F>
   • Class declaration of CGAL_Tpm_vertex_base
   • Class declaration of CGAL_Tpm_halfedge_base
   • Class declaration of CGAL_Pm_face_base
   • Example Programs
9. Planar Map
   • Introduction
   • Planar Map
   • Class declaration of CGAL_Planar_map_2<Dcel,Traits>
   • Class declaration of Vertex
   • Class declaration of Halfedge
   • Class declaration of Face
   • Point Location Strategies
   • Class declaration of CGAL_Pm_point_location_base<Planar_map>
10. Planar Map Overlay
    • Introduction
    • Overlaying two planar maps
11. Triangulations
    • Introduction
    • Triangulation of points in the plane
    • Class declaration of CGAL_Triangulation_2<Gt,Tds>
    • Class declaration of Vertex
    • Class declaration of Face
    • The geometric traits class
    • Class declaration of Geom_traits
    • Class declaration of CGAL_Triangulation_euclidean_traits_2<R>
    • Class declaration of CGAL_Triangulation_euclidean_traits_xy_3<R>
    • The Triangulation Data Structure
    • Class declaration of Tds<Vb,Fb>
    • Class declaration of Tds::Vertex
    • Class declaration of Tds::Face
    • Class declaration of CGAL_Triangulation_default_data_structure_2<Tds_gt,Vb,Fb>
    • The Base Classes Vertex_base and Face_base
    • Class declaration of Vertex_base
    • Class declaration of Face_base
    • Delaunay Triangulations
    • Class declaration of CGAL_Delaunay_triangulation_2<Gt,Tds>
    • Class declaration of Geom_traits
    • Class declaration of Distance<Gt>
    • Regular triangulations
    • Class declaration of CGAL_Regular_triangulation_2<Gt, Tds>
    • Class declaration of Geom_traits
    • Class declaration of CGAL_Regular_triangulation_traits_2<Rep,Weight>
    • Class declaration of Weighted_point
    • Constrained triangulations
    • Class declaration of CGAL_Constrained_triangulation_2<Gt,Tds>
    • Class declaration of Face_base
    • Class declaration of CGAL_Constrained_triangulation_2_demo<T>
12. Boolean Operations in 2D
    • Introduction
    • Boolean Operations on Polygons
    • Boolean Operations Traits Class Implementations
    • Class declaration of CGAL_bops_traits_2<R>
    • Class declaration of Traits<R>
13. Convex Hulls and Extreme Points
    • Planar Convex Hull and Extreme Points
    • Convex Hull Traits Class Implementations
    • Class declaration of CGAL_convex_hull_traits_2<R>
    • Class declaration of CGAL_convex_hull_constructive_traits_2<R>
    • Class declaration of CGAL_convex_hull_rat_leda_traits_2
    • Class declaration of CGAL_convex_hull_leda_traits_2
    • Class declaration of Traits
    • 3D Convex Hull
    • Chull Traits Classes
    • Class declaration of CGAL_chull_traits_2<R>
    • Class declaration of CGAL_chull_traits_3<R>
    • Conversion to Polyhedron
    • Class declaration of CGAL_Build_polyhedron_from_GRAPH<HDS>
    • Class declaration of CGAL_Build_polyhedron_from_chull<HDS, ChullType>
14. Geometric Optimisation
    • Smallest Enclosing Circles
    • Smallest Enclosing Ellipses
    • Smallest Enclosing Spheres
    • Computing Extremal Polygons
    • All Furthest Neighbors
    • Rectangular $p$-Centers
    • Monotone Matrix Search
    • Sorted Matrix Search
15. Search Structures
    • Introduction
    • Range and Segment Trees
    • k-dimensional Range Trees
    • Class declaration of CGAL_Range_tree_k<Traits>
    • k-dimensional Segment Trees
    • Class declaration of CGAL_Segment_tree_k<Traits>
    • Tree Traits Class Implementations
    • Class declaration of CGAL_Range_segment_tree_traits_set_2<R>
    • Class declaration of CGAL_Range_segment_tree_traits_set_3<R>
    • Class declaration of CGAL_Range_tree_traits_map_2<R,T>
    • Class declaration of CGAL_Range_tree_traits_map_3<R>
    • Class declaration of CGAL_Segment_tree_traits_map_2<R,T>
    • Class declaration of CGAL_Segment_tree_traits_map_3<R>
    • Tree Traits Class Requirements
    • Class declaration of Range_segment_tree_traits_k
    • Creating an arbitrary multilayer tree
    • Class declaration of Point_traits
    • Class declaration of Interval_traits
    • Class declaration of CGAL_Range_tree_d<Data, Window, Traits>
    • Class declaration of CGAL_Segment_tree_d<Data, Window, Traits>
    • Class declaration of CGAL_Tree_anchor<Data, Window>
    • KD-trees
    • Class declaration of CGAL_Kdtree_d<I>
    • Class declaration of CGAL_Kdtree_d<I>::Box
    • KD-tree Default Interface Class
    • KD-tree Interface Class Specification
    • Class declaration of I
16. Bibliography
17. Index