Chapter 3
Introduction

3.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:

Andreas Fabri (GEOMETRY FACTORY)
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 http://www.cgal.org/Tutorials/ and the user support page at www.cgal.org.


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

3.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.1 A user can either qualify names from CGAL by adding CGAL:: to the name, e.g., CGAL::Point_2< CGAL::Homogeneous< int> >; making 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 making all names from namespace CGAL visible in a scope with using namespace CGAL;. The latter, however, is likely to give rise to name conflicts and is therefore not recommended.

3.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 include CGAL/basic.h first in your programs (or CGAL/Cartesian.h, or CGAL/Homogeneous.h, since they include CGAL/basic.h first).

3.4   Preconditions, Postconditions, Assertions and Warnings

Much of the CGAL code contains checks. For example, all checks used in the kernel code are prefixed by CGAL_KERNEL. Other packages have their own prefixes, as documented in the corresponding chapters. Some are there to check if the kernel behaves correctly, others are there to check if the user calls kernel routines in an acceptable manner.

To assure that programs (and programmers) behave as expected, the following four types of checks are used through the CGAL code:

Preconditions
check if the caller of a routine has called it in a proper fashion. If such a check fails it is the responsibility of the caller (usually the user of the library). Preconditions for functions and data structures are documented in the corresponding reference pages.
Postconditions
check if a routine does what it promises to do. If such a check fails it is the fault of this routine. Postconditions are also documented in the relevant sections of the reference manual.
Assertions
are other checks that do not fit in the above two categories. These are generally used to assure invariants in the code and are not generally documented.
Warnings
are checks for which it is not so severe if they fail.

By default, all of these checks are performed. It is however possible to turn them off through the use of compile time switches. The names of these switches for each of the above checks are:

Here <package> stands for a string that is particular to each package. This string should be documented at the beginning of the chapter in this reference manual that includes the reference pages for the function or data structure you are using.

For example, for the convex hull functions, the word CH is used and thus the switches are: CGAL_CH_NO_PRECONDITIONS, CGAL_CH_NO_POSTCONDITIONS, CGAL_CH_NO_ASSERTIONS and CGAL_CH_NO_WARNINGS. So, in order to compile the file foo.C with the postcondition checks for these functions turned off, you should do:
CC -DCGAL_CH_NO_POSTCONDITIONS foo.C

Not all checks are on by default. All four types of checks can be marked as expensive or exactness checks (or both). These checks need to be turned on explicitly by supplying one or both of the compile time switches CGAL_<package>_CHECK_EXPENSIVE and CGAL_<package>_CHECK_EXACTNESS.

Expensive checks are, as the word says, checks that take a considerable time to compute. Considerable is an imprecise phrase. Checks that add less than 10 percent to the execution time of the routine they are in are not expensive. Checks that can double the execution time are. Somewhere in between lies the border line. Checks that increase the asymptotic running time of an algorithm are always considered expensive. Exactness checks are checks that rely on exact arithmetic. For example, if the intersection of two lines is computed, the postcondition of this routine may state that the intersection point lies on both lines. However, if the computation is done with doubles as number type, this may not be the case, due to round off errors. So, exactness checks should only be turned on if the computation is done with some exact number type.

3.5   Altering the failure behaviour

If a postcondition, precondition or assertion is violated, the program will abort (stop and produce a core dump). This behaviour can be changed by means of the following function.

#include <CGAL/assertions.h>

Failure_behaviour set_error_behaviour ( Failure_behaviour eb)

The parameter should have one of the following values.

enum Failure_behaviour { ABORT , EXIT , EXIT_WITH_SUCCESS , CONTINUE };
The first value is the default. If the EXIT value is set, the program will stop and return a value indicating failure, but not dump the core. The last value tells the checks to go on after diagnosing the error.


begin of advanced section  advanced  begin of advanced section
If the EXIT_WITH_SUCCESS value is set, the program will stop and return a value corresponding to successful execution and not dump the core.
end of advanced section  advanced  end of advanced section

The value that is returned by set_error_behaviour is the value that was in use before.

For warnings there is a separate routine, which works in the same way. The only difference is that for warnings the default value is CONTINUE.

Failure_behaviour set_warning_behaviour ( Failure_behaviour eb)


begin of advanced section  advanced  begin of advanced section

3.6   Customising how errors are reported

Normally, error messages are written to the standard error output. It is possible to do something different with them. To that end you can register your own handler. This function should be declared as follows.

void
my_failure_function (
const char *type,
const char *expression,
const char *file,
int line,
const char *explanation)

Your failure function will be called with the following parameters:

type
is a string that contains one of the words precondition, postcondition, assertion or warning.
expression
contains the expression that was violated.
file
is the file in which the check was made.
line
is the line number in that file on which the check was made.
explanation
contains an explanation of what was checked. It can be NULL, in which case the expression is thought to be descriptive enough.

There are several things that you can do with your own handler. You can display a diagnostic message in a different way, for instance in a pop-up window or to a log file (or a combination). You can also implement a different policy on what to do after an error. For instance, you can throw an exception or ask the user in a dialogue whether to abort or to continue. If you do this, it is best to set the error behaviour to CONTINUE, so that it does not interfere with your policy.

You can register two handlers, one for warnings and one for errors. Of course, you can use the same function for both if you want. When you set a handler, the previous handler is returned, so you can restore it if you want.

#include <CGAL/assertions.h>

Failure_function set_error_handler ( Failure_function handler)
Failure_function set_warning_handler ( Failure_function handler)

Example

#include <CGAL/assertions.h>

void my_failure_handler(
    const char *type,
    const char *expr,
    const char* file,
    int line,
    const char* msg)
{
    /* report the error in some way. */
}

void foo()
{
    CGAL::Failure_function prev;
    prev = CGAL::set_error_handler(my_failure_handler);
    /* call some routines. */
    CGAL::set_error_handler(prev);
}

end of advanced section  advanced  end of advanced section

3.7   Compile-time Flags to Control Inlining

Making funcitons inlined can, at times, improve the efficiency of your code. However this is not always the case and it can differ for a single function depending on the application in which it is used. Thus CGAL defines a set of compile-time macros that can be used to control whether certain functions are designated as inlined functions or not. The following table lists the macros and their default values, which are set in one of the CGAL include files.

macro name default

CGAL_KERNEL_INLINE inline
CGAL_KERNEL_MEDIUM_INLINE
CGAL_KERNEL_LARGE_INLINE
CGAL_MEDIUM_INLINE inline
CGAL_LARGE_INLINE
CGAL_HUGE_INLINE

If you wish to change the value of one or more of these macros, you can simply give it a new value when compiling. For example, to make functions that use the macro CGAL_KERNEL_MEDIUM_INLINE inline functions, you should set the value of this macro to inline instead of the default blank.

3.8   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).


Footnotes

 1  Removing prefix CGAL_ and introducing namespace CGAL is the major difference between releases 1.2 and 2.0.