Chapter 1

1.1   Overview

CGAL, the Computational Geometry Algorithms Library, was founded and initially developed by a consortium consisting of ETH Zürich (Switzerland), Freie Universität Berlin (Germany), INRIA Sophia-Antipolis (France), Martin-Luther-Universität Halle-Wittenberg (Germany), Max-Planck Institut für Informatik, Saarbrücken (Germany), RISC Linz (Austria) Tel-Aviv University (Israel), and Utrecht University (The Netherlands). CGAL has become an Open Source Project with the release 3.0 in November 2003. New developers and sites are welcome to join the project and have done so already. You can find more information about the project on the CGAL home page .

The CGAL Editorial Board consists of:

Efi Fogel (Tel-Aviv University)
Bernd Gärtner (ETH Zürich)
Michael Hoffmann (ETH Zürich)
Menelaos Karavelas (University of Notre Dame)
Lutz Kettner ( Max-Planck Institut für Informatik )
Sylvain Pion (INRIA Sophia-Antipolis)
Monique Teillaud (INRIA Sophia-Antipolis)
Remco Veltkamp (Utrecht University)
Mariette Yvinec (INRIA Sophia-Antipolis)

CGAL 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 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.

The third part of the library consists of non-geometric support facilities, such as support for number types, STL extensions for CGAL, handles, circulators, protected access to internal representations, geometric object generators, timers, I/O stream operators and other stream support including PostScript, colors, windows, and visualization tools GeoWin, Geomview and a Qt widget for 2D CGAL objects.

Additional documents accompanying the CGAL distribution are the `Installation Guide' and `The Use of STL and STL Extensions in CGAL', which gives a manual style introduction to STL constructs such as iterators and containers, as well an extension, called circulator, used in many places in CGAL. We also recommend the standard text book by Austern [Aus98] for the STL and its notion of concepts and models.

Other resources for CGAL are the tutorials at and the user support page at

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

1.2   Namespace CGAL::

All names introduced by CGAL, especially those documented in these manuals, are in a namespace called CGAL, which is in global scope. A user can either qualify names from CGAL by adding CGAL::, e.g., CGAL::Point_2< CGAL::Homogeneous< int> >, make a single name from CGAL visible in a scope via a using statement, e.g., using CGAL::Cartesian;, and then use this name unqualified in this scope, or even make all names from namespace CGAL visible in a scope with using namespace CGAL;. The latter, however, is likely to give raise to name conflicts and is therefore not recommended.

1.3   Inclusion Order of Header files

Not all compilers fully support standard header names. CGAL provides workarounds for these problems in CGAL/basic.h. Consequently, as a golden rule, you should always inlcude CGAL/basic.h first in your programs (or CGAL/Cartesian.h, or CGAL/Homogeneous.h, since they include CGAL/basic.h first).

1.4   Acknowledgement

This work was partially supported by the ESPRIT IV Long Term Research Projects No. 21957 (CGAL) and No. 28155 (GALIA), and by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project No IST-2000-26473 (ECG - Effective Computational Geometry for Curves and Surfaces).