Chapter 8
dD Geometry Kernel

Table of Contents

8.1   Introduction

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.

8.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 dedicated chapter for more details on number types and their capabilities and performance.

8.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 modeling 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] = *++⁽ⁱ⁾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.

8.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.

8.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 fulfill 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.

8.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.

8.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.

8.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>.

8.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.

8.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 computations in the mathematical evaluation of predicates. As rounding errors accumulate fast the homogeneous representation 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.

8.2.7   Inclusion of Header Files

You need just to include a representation class to obtain 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

8.3   Kernel Geometry

8.3.1   Points and Vectors

^d

^d

CGAL defines a symbolic constant ORIGIN of type Origin which denotes the point at the origin. This constant is used in the conversion between points and vectors. Subtracting it from a point $$p results in the locus vector of $$p.

  double coord[] = {1.0, 1.0, 1.0, 1.0};
  Point_d< Cartesian_d<double> >  p(4,coord,coord+4), q(4);
  Vector_d< Cartesian_d<double> >  v(4);
  v = p - ORIGIN;
  q = ORIGIN + v;  
  assert( p == q );

In order to obtain the point corresponding to a vector $$v you simply have to add $$v to ORIGIN. If you want to determine the point $$q in the middle between two points $$p₁ and $$p₂, you can write¹

  q = p_1 + (p_2 - p_1) / 2.0;

Note that these constructions do not involve any performance overhead for the conversion with the currently available representation classes.

8.3.2   Kernel Objects

Besides points (Point_d<R>), vectors (Vector_d<R>), and directions (Direction_d<R>), CGAL provides lines, rays, segments, hyperplanes, and spheres.

Lines (Line_d<R>) in CGAL are oriented. A ray (Ray_d<R>) is a semi-infinite interval on a line, and this line is oriented from the finite endpoint of this interval towards any other point in this interval. A segment (Segment_d<R>) is a bounded interval on a directed line, and the endpoints are ordered so that they induce the same direction as that of the line.

Hyperplanes are affine subspaces of dimension $$d-1 in $$ ^d, passing through $$d points. Hyperplanes are oriented and partition space into a positive side and a negative side. In CGAL, there are no special classes for halfspaces. Halfspaces are supposed to be represented by oriented hyperplanes. All kernel objects are equality comparable via operator== and operator!=. For those oriented objects whose orientation can be reversed (segments, lines, hyperplanes, spheres) there is also a global function weak_equality that allows to test for point set equality disregarding the orientation.

8.3.3   Orientation and Relative Position

Geometric objects in CGAL have member functions that test the position of a point relative to the object. Full dimensional objects and their boundaries are represented by the same type, e.g. halfspaces and hyperplanes are not distinguished, neither are balls and spheres. Such objects split the ambient space into two full-dimensional parts, a bounded part and an unbounded part (e.g. spheres), or two unbounded parts (e.g. hyperplanes). By default these objects are oriented, i.e., one of the resulting parts is called the positive side, the other one is called the negative side. Both of these may be unbounded.

For these objects there is a function oriented_side() that determines whether a test point is on the positive side, the negative side, or on the oriented boundary. These function returns a value of type Oriented_side.

Those objects that split the space in a bounded and an unbounded part, have a member function bounded_side() with return type Bounded_side.

If an object is lower dimensional, e.g. a segment in $$d-dimensional space, there is only a test whether a point belongs to the object or not. This member function, which takes a point as an argument and returns a Boolean value, is called has_on()

8.4   Predicates and Constructions

8.4.1   Predicates

CGAL provides predicates for the orientation of point sets (orientation), for comparing points according to some given order, especially for comparing Cartesian coordinates (e.g. lexicographically_xy_smaller), in-sphere tests, and predicates to compare distances.

8.4.2   Constructions

Affine transformations (Aff_transformation_d<R>) allow to generate new object instances under arbitrary affine transformations. These transformations include translations, rotations (within planes) and scaling. Most of the geometric objects in a kernel have a member function transform(Aff_transformation t) which applies the transformation to the object instance.

CGAL also provides a set of functions that detect or compute the intersection between objects and functions to calculate their squared distance. Moreover, some member functions of kernel objects are constructions.

So there are routines that compute the square of the Euclidean distance, but no routines that compute the distance itself. Why? First of all, the two values can be derived from each other quite easily (by taking the square root or taking the square). So, supplying only the one and not the other is only a minor inconvenience for the user. Second, often either value can be used. This is for example the case when (squared) distances are compared. Third, the library wants to stimulate the use of the squared distance instead of the distance. The squared distance can be computed in more cases and the computation is cheaper. We do this by not providing the perhaps more natural routine, The problem of a distance routine is that it needs the sqrt operation. This has two drawbacks:

• The sqrt operation can be costly. Even if it is not very costly for a specific number type and platform, avoiding it is always cheaper.
• There are number types on which no sqrt operation is defined, especially integer types and rationals.

8.4.3   Intersection and Polymorphic Return Values

Intersections on kernel objects currently cover only those objects that are part of flats (Segment_d<R>, Ray_d<R>, Line_c<R>, and Hyperplane_d<R>). For any pair of objects $$o1, $$o2 of these types the operation intersection(o1,o2) returns a polymorphic object that wraps the result of the intersection operation.

The class Object provides the polymorphic abstraction. An object obj of type Object can represent an arbitrary class. The only operations it provides is to make copies and assignments, so that you can put them in lists or arrays. Note that Object is NOT a common base class for the elementary classes. Therefore, there is no automatic conversion from these classes to Object Rather this is done with the global function make_object(). This encapsulation mechanism requires the use of object_cast to unwrap the encapsulated class.

Example

  typedef Point_d< Cartesian_d<double> >    Point;
  typedef Segment_d< Cartesian_d<double> >  Segment;
  Segment s1, s2;
  std::cin >> s1 >> s2;
  Object obj = intersection(s1, s2);
  if (const Point *p = object_cast<Point>(&obj) ) {
    /* do something with *p */
  } else if (const Segment *s = object_cast<Segment>(&obj) ) {
    /* do something with *s */
  }
  /*  there was no intersection */

8.4.4   Constructive Predicates

In CGAL, we provide predicates in which such geometric decisions are made directly with a reference to the input points in $$P without an intermediary object like a plane. For the above test, the recommended way to get the result is to use orientation(P',P'+d), where $$P' is an array containing the points $$p₁, ... , $$p_d, $$p.

For exact number types like leda_real, the situation is different. If several tests are to be made with the same plane, it pays off to construct the plane and to use oriented_side(p).

8.5   Design and Implementation History

This higher-dimensional kernel is the result of a long evolving development. A first version of the kernel was offered as a LEDA extension package ddgeo by Kurt Mehlhorn and Michael Seel. The original design was driven by the realization of a d-dimensional convex hull data type developed at the Max-Planck Institut für Informatik .

The code base was discussed and reviewed within the CGAL kernel group (of the low-dimensional kernel). This led to the identification of the concept interfaces and in parallel to adaptations according to the evolution of the low-dimensional kernel. The kernel was revised based on suggestions by Hervé Brönnimann, Michael Hoffmann, and Stefan Schirra.

8.5.1   Acknowledgments

This work was supported by ESPRIT IV Long Term Research Projects No. 21957 (CGAL) and No. 28155 (GALIA).

Footnotes