CGAL (Computational Geometry Algorithms Library) is a C++
software library of geometric algorithms and data structures. It
is developed by several European research institutes and universities,
see http://www.cs.ruu.nl/CGAL
for further information.
We give three examples of genericity in CGAL. In the first two examples
genericity is achieved by parameterization. Thus they are examples
for generic programming via parameterized programming.
The first example is parameterization of the classes in the kernel of
CGAL. All constant-size geometric types in the kernel are parameterized
by a "representation class." Essentially, this parameter must provide
an implementation for the kernel types. CGAL currently offers two concrete
models for the concept representation class, a model which uses Cartesian
coordinates for the implementation and a model using homogeneous coordinates.
Both models are parameterized by the number type used for the coordinates.
We use computation of minimum diameter of a set of moving points to
illustrate the use of the number type real from LEDA (see
http://www.mpi-sb.mpg.de/LEDA
) in the CGAL kernel classes to abolish
precision problems.
The second example is data types and algorithms in the basic library part of CGAL. They are parameterized by the types on which they operate and the components that are used to operate on these types. Instead of having a long parameter list, parameters are collected into a single class called "traits class" in CGAL. The name was chosen because of the conceptual similarity to the traits classes used in the C++ standard library. By the parameterization CGAL gains a lot of flexibility and adaptability.
The third example is the circulator concept. It has been contributed to CGAL by Lutz Kettner (ETH Zürich). A circulator is a variation of the iterator concept for circular sequences. Circular sequences arise frequently in geometry. CGAL data types provide access to such circular sequences through circulators. Circulators turned out to be very useful in CGAL.