CGAL representation classes are parameterized by number types. Depending on the problem and the input data that have to be handled, one has to make a trade-off between efficiency and accuracy in order to select an appropriate number type and representation class.
In homogeneous representation, two number types are involved, although only one of them appears as a template parameter in the homogeneous representation class. This type, for sake of simplicity and readability called ring type is used for the representation of homogeneous coordinates and all internal computations. If it is assured that the second operand divides the first one, these internal computations are basically division-free. The ring type is a placeholder for an integer type (or an integral domain type) rather than for elements of arbitrary rings. The name should remind you that the division operation is not really needed (with the exception mentioned above) for this number type. Of course, also more general number types can be used as a ring type in a homogeneous representation class. In some computations, e.g. accessing Cartesian coordinates, divisions cannot be avoided. In these computations a second number type, the field type, is used. CGAL automatically generates this number type as a CGAL_Quotient. For the Cartesian representation there is only one number type that is used for all calculations.
The representation classes provide access to the number types involved in the representation, although it is not expected that such access is needed at this level, since low-level geometric operations are wrapped in geometric primitives provided by CGAL. This access can be useful if appropriate primitives are missing. In a homogeneous representation class R ring type and field type can be accessed as R::RT and R::FT, respectively. The number type used in Cartesian representation is considered as ring type and as field type depending on the context. If can be accessed as R::RT and R::FT, according to the use of number types used in the homogeneous counterpart.
The requirements are described as a class interface of a class NT, with constructors, methods and the like. This is only a matter of presentation. In fact double and float also fulfill the requirements.
CGALprovides the following function object classes:
#include <CGAL/number_utils_classes.h>
class CGAL_Min<NT>;
class CGAL_Max<NT>;
class CGAL_Abs<NT>;
class CGAL_Sgn<NT>;
class CGAL_Is_negative<NT>;
class CGAL_Is_positive<NT>;
class CGAL_Is_zero<NT>;
class CGAL_Is_one<NT>;
class CGAL_Compare<NT>;
The built-in number types float and double have the required arithmetic and comparison operators. They lack some required routines though which are automatically included by CGAL.
All built-in number types of C++ can represent a discrete (bounded) subset of the rational numbers only. We assume that the floating-point arithmetic of your machine follows Ieee floating-point-standard. Since the floating-point culture has much more infrastructural support (hardware, language definition and compiler) than exact computation, it is very efficient. Like with all number types with finite precision representation which are used as approximations to the infinite ranges of integers or real numbers, the built-in number types are inherently potentially inexact. Be aware of this if you decide to use the efficient built-in number types: you have to cope with numerical problems. For example, you can compute the intersection point of two lines and then check whether this point lies on the two lines.
With floating point arithmetic, roundoff errors may cause the answer of the check to be false. With the built-in integer types overflow might occur.
LEDA provides number types that can be used for exact computation with both Cartesian and homogeneous representation. If you are using homogeneous representation with the built-in integer types short, int, and long as ring type, exactness of computations can be guaranteed only if your input data come from a sufficiently small integral range and the depth of the computations is sufficiently small. LEDA provides the number type leda_integer for integers of arbitrary length. (Of course the length is somehow bounded by the resources of your computer.) It can be used as ring type in homogeneous representation and leads to exact computation as long as all intermediate results are rational. For the same kind of problems Cartesian representation with number type leda_rational leads to exact computation as well. The number type leda_bigfloat in LEDA is a variable precision floating-point type. Rounding mode and precision (i.e. mantissa length) of leda_bigfloat can be set.
The most sophisticated number type in LEDA is the number type called leda_real. Like in Pascal, where the name leda_real is used for floating-point numbers, the name leda_real does not describe the number type precisely, but intentionally. leda_reals are a subset of real algebraic numbers. Any integer is leda_real and leda_reals are closed under the operations and -th root computation.
leda_reals guarantee that all comparisons between expressions involving leda_reals produce the exact result.
In the include files <CGAL/leda_integer.h>, <CGAL/leda_rational.h>,
<CGAL/leda_bigfloat.h>, and <CGAL/leda_real.h>,
the LEDA types leda_integer, leda_rational,
leda_bigfloat,
and leda_real are made conform to the requirements presented in
.
Also, in these files the LEDA number types are included.
For more details on the number types of LEDA we refer to the LEDA
manual [MNU97].
CGAL provides wrapper classes for number types defined in the Gnu Multiple Precision Arithmetic Library [Gra96]. The file CGAL/Gmpz.h provides the class CGAL_Gmpz, a wrapper class for the integer type mpz_t, that is compliant to the CGAL number type requirements. To use this, the Gnu Multiple Precision Arithmetic Library must be installed.
You can also use your own number type with the CGAL representation
classes, e.g. the BigNum package [SVH89].
Depending on the arithmetic operations carried out by the algorithms
that you are going to use the number types must fulfill the
requirements from .