Introduction

CGAL, the Computational Geometry Algorithms Library, is written in C++ and consists of three major parts. The first part is the kernel, which consists of constant-size non-modifiable geometric primitive objects and operations on these objects. The objects are represented both as stand-alone classes that are parameterized by a representation class, which specifies the underlying number types used for calculations and as members of the kernel classes, which allows for more flexibility and adaptability of the kernel. The second part is a collection of basic geometric data structures and algorithms, which are parameterized by traits classes that define the interface between the data structure or algorithm and the primitives they use. In many cases, the kernel classes provided in CGAL can be used as traits classes for these data structures and algorithms. The third part of the library consists of non-geometric support facilities, such as circulators, random sources, I/O support for debugging and for interfacing CGAL to various visualization tools.

This part of the reference manual covers the basic library. The collection of basic geometric algorithms and data structures currently includes polygons, half-edge data structures, polyhedral surfaces, topological maps, planar maps, arrangements of curves, triangulations, convex hulls, alpha shapes, optimisation algorithms, dynamic point sets for geometric queries, and multidimensional search trees.

Some functionality is considered more advanced. Such functionality is described in sections such as this one that are bounded by horizontal brackets.