Predicates and Constructions

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

Affine transformations (*Aff_transformation_2<Kernel>*,
*Aff_transformation_3<Kernel>*) allow to generate new object instances under
arbitrary affine transformations. These transformations include translations,
rotations (in 2D only) 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 of the 2D kernel, and many objects in the 3D kernel, 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.

{ Point_2< Cartesian<double> > point; Segment_2< Cartesian<double> > segment, segment_1, segment_2; std::cin >> segment_1 >> segment_2; Object obj = intersection(segment_1, segment_2); if (assign(point, obj)) { /* do something with point */ } else if ((assign(segment, obj)) { /* do something with segment*/ }

/* there was no intersection */ }

The
intersection
routine itself looks roughly as follows:

template < class Kernel > Object intersection(Segment_2<Kernel> s1, Segment_2<Kernel> s2) {

if (/* intersection in a point */ ) {

Point_2<Kernel> p = ... ; return make_object(p);

} else if (/* intersection in a segment */ ) {

Segment_2<Kernel> s = ... ; return make_object(s); } return Object(); }

In CGAL, we provide predicates in which such
geometric decisions are made directly with a reference to the input points
$$*p*, $$*q*, $$*r*, $$*s*, without an intermediary object like a plane.
For the above test, the recommended way to get the result is to use
*orientation(p,q,r,s)*. 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)*.

Next chapter: Extensible Kernel

The CGAL Project .
Tue, December 21, 2004 .