Prev Up
Go backward to What Kind of Standards Should There Be
for Generic Algorithm Performance?
David Musser

Go up to Libraries and Standardization

Generic Programming in CGAL
Stefan Schirra

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.


 

Prev Up