Chapter 1

This part of the reference manual covers the higher-dimensional kernel. The kernel contains objects of constant size, such as point, vector, direction, line, ray, segment, circle. 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. Note that this section partly recapitulates facts already mentioned for the lower-dimensional kernel.

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 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   Genericity

To increase generic usage of objects and predicates the higher-dimensional kernel makes heavy use of iterator ranges as defined in the STL for modelling tuples. Iterators conceptualize C++ pointers.

For an iterator range [first,last) we define T = tuple [first,last) as the ordered tuple (T[0],T[1], ...T[d-1]) where S[i] = *++(i)first (the element obtained by i times forwarding the iterator by operator ++ and then dereferencing it to get the value to which it points). We write d = size [first,last) and S = set [first,last) to denote the unordered set of elements of the corresponding tuple.

This extends the syntax of random access iterators to input iterators. If we index the tuple as above then we require that ++(d+1)first = last.