Chapter 1
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 kernel.
The kernel contains objects of constant size, such as point, vector,
direction, line, ray, segment, triangle, iso-oriented rectangle and
tetrahedron.
With each type comes a set of functions which can be applied to an object
of this type.
You will typically find access functions (e.g. to the coordinates of a point),
tests of the position of a point relative to the object, a function returning
the bounding box, the length, or the area of an object, and so on.
The CGAL kernel further contains basic operations such as affine
transformations, detection and computation of intersections, and distance
computations.
1.1 Robustness
The correctness proof of nearly all geometric algorithms presented
in theory papers assumes exact computation with real numbers.
This leads to a fundamental problem with the implementation of geometric
algorithms.
Naively, often the exact real arithmetic is replaced by inexact floating-point
arithmetic in the implementation.
This often leads to acceptable results for many input data.
However, even for the implementation of the simplest geometric
algorithms this simplification occasionally does not work.
Rounding errors introduced by an inaccurate arithmetic may lead to
inconsistent decisions, causing unexpected failures for some correct
input data.
There are many approaches to this problem, one of them is to compute
exactly (compute so accurate that all decisions made by the algorithm
are exact) which is possible in many cases but more expensive
than standard floating-point arithmetic.
C. M. Hoffmann [Hof89a, Hof89b] illustrates some
of the problems arising in the implementation of geometric algorithms
and discusses some approaches to solve them.
A more recent overview is given in [Sch00].
The exact computation paradigm is discussed by Yap and Dubé
[YD95] and Yap [Yap97].
In CGAL you can choose the underlying number types and arithmetic.
You can use different types of arithmetic simultaneously and the choice can
be easily changed, e.g. for testing.
So you can choose between implementations with fast but occasionally inexact
arithmetic and implementations guaranteeing exact computation and exact
results.
Of course you have to pay for the exactness in terms of execution time
and storage space.
See the section on number types in the Support Library
for more details on number types and their capabilities and performance.
1.2 CGAL and LEDA
LEDA
is a Library of Efficient Data types and Algorithms partially developed
at the Max-Planck Institut für Informatik, Saarbrücken,
and the University of Trier, Germany.
CGAL is independent of LEDA, but the two work well together. In particular
the exact number types provided by LEDA are a way to deal with the robustness
issues of the geometric algorithms of CGAL.