Chapter 2
Kernel Representations

Our object of study is the $$d-dimensional affine Euclidean space, where $$d is a parameter of our geometry. Objects in that space are sets of points. A common way to represent the points is the use of Cartesian coordinates, which assumes a reference frame (an origin and $$d orthogonal axes). In that framework, a point is represented by a $$d-tuple $(c$₀,c₁,...,c_d-1), and so are vectors in the underlying linear space. Each point is represented uniquely by such Cartesian coordinates.

Another way to represent points is by homogeneous coordinates. In that framework, a point is represented by a $$(d+1)-tuple $(h$₀,h₁,...,h_d). Via the formulae $c$_i=h_i/h_d, the corresponding point with Cartesian coordinates $(c$₀,c₁,...,c_d-1) can be computed. Note that homogeneous coordinates are not unique. For $lambda\; !=\; 0$, the tuples $(h$₀,h₁ ,...,h_d) and $(lambda\; h$₀,lambda h₁,...,lambda h_d) represent the same point. For a point with Cartesian coordinates $(c$₀,c₁,...,c_d-1) a possible homogeneous representation is $(c$₀,c₁,...,c_d-1,1). Homogeneous coordinates in fact allow to represent objects in a more general space, the projective space $P$_d. In CGAL, we do not compute in projective geometry. Rather, we use homogeneous coordinates to avoid division operations, since the additional coordinate can serve as a common denominator.

2.1   Genericity through Parameterization

CGAL offers two families of concrete models for the concept representation class, one based on the Cartesian representation of points and one based on the homogeneous representation of points. The interface of the kernel objects is designed such that it works well with both Cartesian and homogeneous representation, for example, points have a constructor with a range of coordinates plus a common denominator (the $$d+1 homogeneous coordinates of the point). The common interfaces parameterized with a representation class allow one to develop code independent of the chosen representation. We said ``families'' of models, because both families are parameterized too. A user can choose the number type used to represent the coordinates and the linear algebra module used to calculate the result of predicates and constructions.

For reasons that will become evident later, a representation class provides two typenames for number types, namely R::FT and R::RT and one typename for the linear algebra module R::LA. The type R::FT must fulfill the requirements on what is called a field type in CGAL. This roughly means that R::FT is a type for which operations $$+, $$-, $$* and $$/ are defined with semantics (approximately) corresponding to those of a field in a mathematical sense. Note that, strictly speaking, the built-in type int does not fullfil the requirements on a field type, since ints correspond to elements of a ring rather than a field, especially operation $$/ is not the inverse of $$*. The requirements on the type R::RT are weaker. This type must fulfill the requirements on what is called an Euclidean ring type in CGAL. This roughly means that R::RT is a type for which operations $$+, $$-, $$* are defined with semantics (approximately) corresponding to those of a ring in a mathematical sense. A very limited division operation $$/ must be available as well. It must work for exact (i.e., no remainder) integer divisions only. Furthermore, both number types should fulfill CGAL's requirements on a number type.

2.2   Cartesian Kernel

When you choose Cartesian representation you have to declare at least the type of the coordinates. A number type used with the Cartesian_d representation class should be a field type as described above. Both Cartesian<FieldNumberType>::FT and Cartesian<FieldNumberType>::RT are mapped to number type FieldNumberType. Cartesian_d<FieldNumberType,LinearAlgebra>::LA is mapped to the type LinearAlgebra. Cartesian<FieldNumberType> uses reference counting internally to save copying costs.

2.3   Homogeneous Kernel

The type LinearAlgebra must me a linear algebra module working on numbers of type RingNumberType. Again the second parameter defaults to module delivered with the kernel so for short one can just write Homogeneous_d<RingNumberType> when replacing the default is no issue.

However, some operations provided by this kernel involve division operations, for example computing squared distances or returning a Cartesian coordinate. To keep the requirements on the number type parameter of Homogeneous low, the number type Quotient<RingNumberType> is used instead. This number type turns a ring type into a field type. It maintains numbers as quotients, i.e. a numerator and a denominator. Thereby, divisions are circumvented. With Homogeneous_d<RingNumberType>, Homogeneous_d<RingNumberType>::FT is equal to Quotient<RingNumberType> while Homogeneous_d<RingNumberType>::RT is equal to RingNumberType. Homogeneous_d<RingNumberType,LinearAlgebra>::LA is mapped to the type LinearAlgebra.

2.4   Naming conventions

The use of representation classes not only avoids problems, it also makes all CGAL classes very uniform. They always consist of:

1. The capitalized base name of the geometric object, such as Point, Segment, Triangle.

2. Followed by _d.

3. A representation class as parameter, which itself is parameterized with a number type, such as Cartesian_d<double> or Homogeneous_d<leda_integer>.

2.5   Kernel as a Traits Class

Algorithms and data structures in the basic library of CGAL are parameterized by a traits class that subsumes the objects on which the algorithm or data structure operates as well as the operations to do so. For most of the algorithms and data structures in the basic library you can use a kernel as a traits class. For some algorithms you even do not have to specify the kernel; it is detected automatically using the types of the geometric objects passed to the algorithm. In some other cases, the algorithms or data structures needs more than is provided by a kernel. In these cases, a kernel can not be used as a traits class.

2.6   Choosing a Kernel

If you start with integral Cartesian coordinates, many geometric computations will involve integral numerical values only. Especially, this is true for geometric computations that evaluate only predicates, which are tantamount to determinant computations. Examples are triangulation of point sets and convex hull computation.

The dimension $$d of our affine space determines the dimension of the matrix computions in the mathematical evaluation of predicates. As rounding errors accumulate fast the homogeneous represenation used with multi-precision integers is the kernel of choice for well-behaved algorithms. Note, that unless you use an arbitrary precision integer type, incorrect results might arise due to overflow.

If new points are to be constructed, for example the intersection point of two lines, computation of Cartesian coordinates usually involves divisions, so you need to use a field type with Cartesian representation or have to switch to homogeneous representation. double is a possible, but imprecise field type. You can also put any ring type into Quotient to get a field type and put it into Cartesian, but you better put the ring type into Homogeneous. leda_rational and leda_real are valid field types, too.

Still other people will prefer the built-in type double, because they need speed and can live with approximate results, or even algorithms that, from time to time, crash or compute incorrect results due to accumulated rounding errors.

2.7   Inclusion of Header Files

You need just to include a representation class to obtain the the geometric objects of the kernel that you would like to use with the representation class, i.e., CGAL/Cartesian_d.h or CGAL/Homogeneous_d.h