Preliminaries

Our object of study is the $d$-dimensional affine Euclidean space. Here we are concerned with cases $d=2$ and $d=3$. 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.

• Class declaration of R.

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 concept which is called a representation class in CGAL and denoted by R throughout this manual. The complete list of requirements is beyond the scope of this introduction. It is important only if you want to define your own representation class. It is sufficient to know that a representation class provides the actual implementations of the kernel objects.

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 in 2D have a constructor with three arguments as well. 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.

For reasons that will become evident later, a representation class provides two typenames for number types, namely R::FT and R::RT. 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 a 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. Note that a ring type is always a field type but not the other way round.

We describe below the two representations provided for CGAL kernel objects, namely CGAL_Cartesian and CGAL_Homogeneous.

• Class declaration of CGAL_Cartesian<FT>.

#include <CGAL/Cartesian.h>

With CGAL_Cartesian<FT> you can choose Cartesian representation of coordinates. When you choose Cartesian representation you have to declare at the same time the type of the coordinates. A number type used with the CGAL_Cartesian representation class should be a field type as described above. As mentioned above, the built-in type int is not a field type. However, for some computations with Cartesian representation, no division operation is needed, i.e., a ring type is sufficient in this case.)

The declaration for a point with FT = double and with coordinates $(1/3,\; 5/3)$ looks as follows:

  CGAL_Point_2< CGAL_Cartesian<double> > p(1.0/3.0, 5.0/3.0);

The keyword double makes that the program allocates memory for storing the $x$ and $y$ coordinate in double precision format.

With CGAL_Cartesian<NT>, both CGAL_Cartesian<NT>::FT and CGAL_Cartesian<NT>::RT are mapped to number type NT.

• Class declaration of CGAL_Homogeneous<RT>.

#include <CGAL/Homogeneous.h>

As we mentioned before, homogeneous coordinates permit to avoid division operations in numerical computations, since the additional coordinate can serve as a common denominator. Avoiding divisions can be useful for exact geometric computation. With CGAL_Homogeneous<RT> you can choose homogeneous representation of coordinates with the kernel objects. As for Cartesian representation you have to declare at the same time the type used to store the homogeneous coordinates. Since the homogeneous representation allows one to avoid the divisions, the number type associated with a homogeneous representation class must be a model for the weaker concept ring type only. 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 CGAL_Homogeneous low, the number type CGAL_Quotient<RT> 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.

A variable declaration for a point at Cartesian coordinates $(1/3,\; 5/3)$ represented with homogeneous coordinates with ring type double then looks as follows:

  CGAL_Point_2< CGAL_Homogeneous<double> > p(1.0, 5.0, 3.0);

With CGAL_Homogeneous<NT>, CGAL_Homogeneous<NT>::FT is equal to CGAL_Quotient<NT> while CGAL_Homogeneous<NT>::RT is equal to NT.

Choosing a Representation Class

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. In this case, the Cartesian representation is probably the first choice, even with a ring type. You might use limited precision integer types like int or long, use double to present your integers (they have more bits in their mantissa than an int and overflow nicely), or an arbitrary precision integer type like the wrapper CGAL_Gmpz for the GMP integers or leda_integer. 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 CGAL_Quotient to get a field type and put it into CGAL_Cartesian, but you better put the ring type into CGAL_Homogeneous. leda_rational and leda_real are valid field types, too.

If it is crucial for you that the computation is reliable, the right choice are probably number types that guarantee exact computation. The number type leda_real guarantees that all decisions and hence all branchings in a computation are correct. They also allow you to compute approximations to whatever precision you need. Furthermore computation with leda_real is faster than computation with arbitrary precision arithmetic. So if you would like to avoid surprises caused by imprecise computation, this is a good choice. In fact, it is a good choice with both representations, since divisions slow down the computation of the reals and hence it might pay-off to avoid them.

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.

Footnotes

1. The double colon :: is the C++ scope operator.