Kernel Representations

Almost all the kernel objects (and the corresponding functions) are
templates with a parameter that allows the user to choose the
representation of the kernel objects. A type that is used as an
argument for this parameter must fulfill certain requirements on
syntax and semantics. The list of requirements defines an abstract
kernel concept. For all kernel objects
*Object*
, the types
*CGAL::Object<Kernel>*
and
*Kernel::Object*
are identical.

CGAL offers four families of concrete models for the concept Kernel, two based on the Cartesian representation of points and two 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 in 2D have a constructor with three arguments as well (the three homogeneous coordinates of the point). The common interfaces parameterized with a kernel 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.

For reasons that will become evident later, a kernel class provides
two typenames for number types,
namely *Kernel::FT* and *Kernel::RT*. The type *Kernel::FT* must fulfill the
requirements on what is called a *FieldNumberType* in CGAL. This
roughly means that *Kernel::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 *int*s correspond to elements
of a ring rather than a field, especially operation $$*/* is not the
inverse of $$***. The requirements on the type *Kernel::RT* are
weaker. This type must fulfill the requirements on what is called a
*RingNumberType* in CGAL. This roughly means that
*Kernel::RT* is a type for which operations $$*+*, $$*-*, $$*** are
defined with semantics (approximately) corresponding to those of a
ring in a mathematical sense.

*Cartesian<FieldNumberType>* uses reference counting internally to
save copying costs. CGAL also provides
*Simple_cartesian<FieldNumberType>*, a kernel that uses
Cartesian
representation but no reference
counting. Debugging is easier with
*Simple_cartesian<FieldNumberType>*, since the coordinates are
stored within the class and hence direct access to the coordinates is
possible. Depending on the algorithm, it can also be slightly more or
less efficient than *Cartesian<FieldNumberType>*. Again, in
*Simple_cartesian<FieldNumberType>* both
*Simple_cartesian<FieldNumberType>::FT* and
*Simple_cartesian<FieldNumberType>::RT* are mapped to
*FieldNumberType*.

*Homogeneous<RingNumberType>* uses reference counting internally
to save copying costs. CGAL also provides
*Simple_homogeneous<RingNumberType>*, a kernel that uses
homogeneous
representation but no reference
counting. Debugging is easier with
*Simple_homogeneous<RingNumberType>*, since the coordinates are
stored within the class and hence direct access to the coordinates is
possible. Depending on the algorithm, it can also be slightly more or
less efficient than *Homogeneous<RingNumberType>*. Again, in
*Simple_homogeneous<RingNumberType>* the type
*Simple_homogeneous<RingNumberType>::FT* is equal to
*Quotient<RingNumberType>* while
*Simple_homogeneous<RingNumberType>::RT* is equal to
*RingNumberType*.

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

- The
*capitalized base name*of the geometric object, such as*Point*,*Segment*, or*Triangle*. - An
*underscore*followed by the*dimension*of the object, for example $$*_2*, $$*_3*, or $$*_d*. - A
*kernel class*as parameter, which itself is parameterized with a number type, such as*Cartesian<double>*or*Homogeneous<leda_integer>*.

If new points are to be constructed, for example the
intersection
point of two lines, computation of
Cartesian
coordinates usually involves divisions.
Hence, one needs to use a FieldNumberType with
Cartesian
representation, or alternatively, switch
to homogeneous representation. The type *double* is a - though
imprecise - model for FieldNumberType. You can also put any
RingNumberType into the *Quotient* adaptor to get a field type
which then can be put into *Cartesian*. But using homogeneous
representation on the RingNumberType is usually the better option.
Other valid FieldNumberTypes are *leda_rational* and
*leda_real*.

If it is crucial for you that the computation is reliable, the right
choice is probably a number type that guarantees exact computation.
The *Filtered_kernel* provides a way to apply filtering techniques
[BBP01] to achieve a kernel with exact and efficient
predicates. 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.

**Predefined kernels.**
For the user's convenience, CGAL provides 3 typedefs to generally useful
kernels.

- They are all Cartesian kernels.
- They all support constructions of points from
`double`Cartesian coordinates. - All these 3 kernels provide exact geometric predicates.
- They handle geometric constructions differently:
*Exact_predicates_exact_constructions_kernel*: provides exact geometric constructions, in addition to exact geometric predicates.*Exact_predicates_exact_constructions_kernel_with_sqrt*: same as*Exact_predicates_exact_constructions_kernel*, but the number type it provides (*Exact_predicates_exact_constructions_kernel_with_sqrt::FT*) supports the square root operation exactly^{1}.*Exact_predicates_inexact_constructions_kernel*: provides exact geometric predicates, but geometric constructions may be inexact due to roundoff errors. It is however enough for most CGAL algorithms, and faster than both*Exact_predicates_exact_constructions_kernel*and*Exact_predicates_exact_constructions_kernel_with_sqrt*.

^{1} | Currently it requires having either LEDA or CORE installed |

Next chapter: Kernel Geometry

The CGAL Project .
Tue, December 21, 2004 .