CGAL Basic Library Reference Manual
Table of Contents

1. Title Page
2. Table of Contents
3. Preface
4. Introduction
5. Polygon
   • Class declaration of Polygon_2<Traits,Container>
   • Algorithms on sequences of 2D points
   • Polygon Traits class requirements
   • Class declaration of Polygon_traits
   • Class declaration of 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 Halfedge_data_structure_default<Point>
   • Class declaration of Halfedge_data_structure_using_list<V,H,F>
   • Class declaration of 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 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 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 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 Pm_dcel<V,H,F>
   • Class declaration of Tpm_vertex_base
   • Class declaration of Tpm_halfedge_base
   • Class declaration of Pm_face_base
   • Example Programs
9. Planar Map
   • Introduction
   • Planar Map
   • Class declaration of Planar_map_2<Dcel,Traits>
   • Class declaration of Vertex
   • Class declaration of Halfedge
   • Class declaration of Face
   • Point Location Strategies
   • Class declaration of Pm_point_location_base<Planar_map>
   • Requirements for Planar Map Dcel Classes
   • Class declaration of Dcel::Vertex
   • Class declaration of Dcel::Halfedge
   • Model for a Planar Map Dcel Class
   • Requirements for Planar Map Traits Classes
   • Class declaration of Pm_traits
   • Predefined Traits Classes
   • Class declaration of Pm_segment_exact_traits<R>
   • Class declaration of Pm_segment_epsilon_traits<R>
   • Class declaration of Pm_leda_segment_exact_traits
   • Example Program
10. 2D Arrangements
    • Introduction
    • Example Programs
    • Arrangements
    • Class declaration of Arrangement_2<Dcel,Traits,Base_node>
    • Class declaration of Subcurve_node
    • Class declaration of Curve_node
    • Class declaration of Edge_node
    • Class declaration of Vertex
    • Class declaration of Halfedge
    • Class declaration of Face
    • Requirements for Arrangement Dcel Classes
    • Class declaration of Halfedge
    • Model for an Arrangement Dcel Class
    • Requirements for Arrangement Traits Classes
    • Class declaration of Arr_traits
    • Models for an Arrangement Traits Class
    • Class declaration of Arr_leda_segment_exact_traits
    • Class declaration of Circ_curve
    • Requirement for Arrangement Base_node Class
    • Class declaration of Base_node
    • Model for an Arrangement Base_node Class
11. Triangulations
    • Introduction
    • Triangulation of points in the plane
    • Class declaration of Triangulation_2<Gt,Tds>
    • Class declaration of Vertex
    • Class declaration of Face
    • The Geometric Traits Class
    • Class declaration of Geom_traits
    • Class declaration of Triangulation_euclidean_traits_2<R>
    • Class declaration of 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 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 Delaunay_triangulation_2<Gt,Tds>
    • Class declaration of Delaunay_geom_traits
    • Class declaration of Line
    • Class declaration of Ray
    • Class declaration of Distance<Gt>
    • Regular triangulations
    • Class declaration of Regular_triangulation_2<Gt, Tds>
    • Class declaration of Regular_face_base
    • Class declaration of Regular_geom_traits
    • Class declaration of Regular_triangulation_traits_2<Rep,Weight>
    • Class declaration of Weighted_point
    • Constrained Triangulations
    • Class declaration of Constrained_triangulation_2<Gt,Tds>
    • Class declaration of Constrained_face_base
    • Class declaration of Constrained_triangulation_demo_2<Gt,Tds>
    • Constrained Delaunay Triangulations
    • Class declaration of Constrained_Delaunay_triangulation_2<Gt,Tds>
12. Triangulation in 3D
    • Introduction
    • Software Design
    • Examples
    • A Class of Tools
    • Class declaration of Triangulation_utils_3
    • Basic Triangulation
    • Class declaration of Triangulation_3<Traits,Tds>
    • The Vertex of a Triangulation
    • Class declaration of Triangulation_vertex_3<Traits,Tds>
    • The Cell of a Triangulation
    • Class declaration of Triangulation_cell_3<Traits,Tds>
    • Delaunay Triangulation
    • Class declaration of Delaunay_triangulation_3<Traits,Tds>
    • Hierarchic Delaunay Triangulation
    • Class declaration of Delaunay_hierarchic_triangulation_3<Traits,Tds>
    • Regular Triangulation
    • Class declaration of Regular_triangulation_3<Traits,Tds>
    • The Geometric Traits
    • Class declaration of Triangulation_Traits_3
    • Class declaration of Triangulation_geom_traits_3<R>
    • Class declaration of Regular_triangulation_euclidean_traits_3<R,Weight>
    • Class declaration of Weighted_point<Point,Weight>
    • The Triangulation Data Structure Parameter
13. Triangulation Data Structure in 3D
    • Introduction
    • Software Design
    • Examples
    • Concepts
    • Class declaration of Tds<Vb,Fb>
    • Class declaration of Tds::Vertex
    • Class declaration of Tds::Cell
    • A model of Triangulation Data Structure
    • Class declaration of Triangulation_data_structure_3<Vb,Cb>
    • Concepts for the Base Vertices and Cells
    • Class declaration of Vertex_base
    • Class declaration of Cell_base
    • Models of Base Vertices and Cells
    • Class declaration of Triangulation_vertex_base_3<Traits>
    • Class declaration of Triangulation_vertex_base_pointer_3<Traits>
    • Class declaration of Triangulation_cell_base_3<Traits>
14. Convex Hulls and Extreme Points
    • Planar Convex Hull and Extreme Points
    • Convex Hull Traits Class Implementations
    • Class declaration of convex_hull_traits_2<R>
    • Class declaration of convex_hull_constructive_traits_2<R>
    • Class declaration of convex_hull_rat_leda_traits_2
    • Class declaration of convex_hull_leda_traits_2
    • Class declaration of Traits
    • 3D Convex Hull
    • Chull Traits Classes
    • Class declaration of chull_traits_2<R>
    • Class declaration of chull_traits_3<R>
    • Conversion to Polyhedron
    • Class declaration of Build_polyhedron_from_GRAPH<HDS>
    • Class declaration of Build_polyhedron_from_chull<HDS, ChullType>
15. Alpha-Shapes
    • Introduction
    • Generic Alpha-Shapes of Points in a Plane
    • Class declaration of Alpha_shape_2<Dt>
    • The Underlying Triangulation
    • Class declaration of Gt
    • Class declaration of Alpha_shape_vertex_base
    • Class declaration of Alpha_shape_face_base<Df>
    • Classic Version of Alpha-Shapes
    • Weighted Version of Alpha-Shapes
16. Geometric Optimisation
    • Smallest Enclosing Circles
    • Smallest Enclosing Ellipses
    • Smallest Enclosing Spheres
    • Minimum Enclosing Quadrilaterals
    • Computing Extremal Polygons
    • All Furthest Neighbors
    • Rectangular $$p-Centers
    • Monotone Matrix Search
    • Sorted Matrix Search
17. Point_set_2
    • Introduction
    • Definition
    • Class declaration of Point_set_2<Traits>
    • The Point_set Traits Class
    • Class declaration of Point_set_traits
    • Class declaration of point_set_traits_2<T>
    • Class declaration of point_set_leda_float_traits_2
    • Class declaration of point_set_leda_rat_traits_2
    • Examples
    • Implementation
18. Search Structures
    • Introduction
    • Range and Segment Trees
    • k-dimensional Range Trees
    • Class declaration of Range_tree_k <Traits>
    • k-dimensional Segment Trees
    • Class declaration of Segment_tree_k <Traits>
    • Tree Traits Class Implementations
    • Class declaration of Range_segment_tree_traits_set_2<R>
    • Class declaration of Range_segment_tree_traits_set_3<R>
    • Class declaration of Range_tree_traits_map_2<R,T>
    • Class declaration of Range_tree_traits_map_3<R>
    • Class declaration of Segment_tree_traits_map_2<R,T>
    • Class declaration of 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 Range_tree_d<Data, Window, Traits>
    • Class declaration of Segment_tree_d<Data, Window, Traits>
    • Class declaration of Tree_anchor<Data, Window>
    • KD-trees
    • Class declaration of Kdtree_d<Interface_traits>
    • Class declaration of Kdtree_d<Interface_traits>::Box
    • KD-tree Default Interface Class
    • KD-tree Interface Class Specification
    • Class declaration of Interface_traits
19. Bibliography
20. Index