Chapter 4
Predicates and Constructions

4.1   Predicates

Predicates are at the heart of a geometry kernel. They are basic units for the composition of geometric algorithms and encapsulate decisisons. Hence their correctness is crucial for the control flow and hence for the correctness of an implementation of a geometric algorithm. CGAL uses the term predicate in a generalized sense. Not only components returning a Boolean value are called predicates but also components returning an enumeration type like a Comparison_result or an Orientation. We say components, because predicates are implemented both as functions and function objects (also called functors and provided by a kernel class).

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.

4.2   Constructions

Functions and function objects that generate objects that are neither of type bool nor enum types are called constructions. Constructions involve computation of new numerical values and may be imprecise due to rounding errors unless a kernel with an exact number type is used.

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:

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 assign to unwrap the encapsulated class.


In the following example, the object type is used as a return value for the intersection computation, as there are possibly different return values.
  Point_d< Cartesian_d<double> > p;
  Segment_d< Cartesian_d<double> > s, s1, s2;
  std::cin >> s1 >> s2;
  Object obj = intersection(s1, s2);
  if ( assign(p, obj) ) {
    /* do something with p */
  } else if ( (assign(s, obj) ) {
    /* do something with s */
  /*  there was no intersection */

4.4   Constructive Predicates

For testing where a point p lies with respect to a hyperplane defined by an array P of points p1, ... , pd, one may be tempted to construct the hyperplane Hyperplane_d<R>(d,P,P+d) and use the method oriented_side(p). This may pay off if many tests with respect to the plane are made. Nevertheless, unless the number type is exact, the constructed plane is only approximated, and round-off errors may lead oriented_side(p) to return an orientation which is different from the orientation of p1, ... , pd, p.

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 p1, ... , pd, 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).