.
CGAL kernel 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 kernel class.
In homogeneous representation, two number types are involved, although only one of them appears as a template parameter in the homogeneous kernel classes. This type, for the 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 needed for this number type. Of course, also more general number types can be used as a ring type in a homogeneous kernel 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 Quotient. For the Cartesian kernels there is only one number type that is used for all calculations.
The kernel 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 kernel class K, ring type and field type can be accessed as K::RT and K::FT, respectively. The number type used in Cartesian kernels is considered as ring type or as field type depending on the context. If can be accessed as K::RT and K::FT, according to the use of number types used in the homogeneous counterpart.
Number types must fulfill certain requirements, such that they can be successfully used in CGAL code. The syntacitical requirements of number types are described in the concepts RingNumberType and FieldNumberType included in the kernel reference manual. Of course, number types also have evident semantic constraints. They should be meaningful in the sense that they approximate the integers or the rationals or some other subfield of the real numbers.
The number type concepts mentioned in the previous section list all the required functionality. For the user of a number type it is handy to have a larger set of operations available. CGAL defines a number of such operations, to compute, for example, the minimum or maximum of two numbers, and the absolute value, square, sign or square root of a number. These are available both as global functions and as functors. See the reference manual for more details.
Those routines are implemented using the required operations from the number type concepts. They are defined by means of templates, so you do not have to supply all those operations when you write a new number type. But if you have a better implementation for any of them, you can provide a corresponding overloading function with the same name for your number types, which will get preference over the template functions listed above.
For the number types int, and double there is also a random numbers generator CGAL::Random.
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.
CGAL provides several number types that are that can be used for exact computation. These include the Quotient class that can be used to create, for example, a number type that behaves like a rational number. When used in conjunction with the number type MP_Float that is able to represent multi-precision floating point values, you achieve an exact rational number representation. The templated number type Lazy_exact_nt<NT> is able to represent any number that NT is able to represent, but because it first tries to use an approximate value to perform computations it can be faster than the provided number type NT. CGAL also provides a fixed-precision number type, Fixed_precision_nt that provides 24-bit numbers in fixed point representation. This number type provides some specialized predicates that are exact and efficient for numbers known to be representable using 24 bits. Two number types for doing interval arithmetic, Interval_nt and Interval_nt_advanced, are also provided. These number types help in doing filtering of predicates.
CGAL defines the functions needed to use the number type CORE::Expr provided by CORE [KLPY99]. To use CORE with CGAL, just install CGAL with CORE support, and include the file CGAL/CORE_Expr.h. CORE version 1.5 or later is required.
CORE::Exprs are a subset of real algebraic numbers. Any integer is a CORE::Expr and CORE::Exprs are closed under the operations and . CORE::Exprs guarantee that all comparisons between expressions involving CORE::Exprs produce the exact result.
This number type provides an equivalent functionality to leda_real.
CGAL provides wrapper classes for number types defined in the GNU Multiple Precision arithmetic library [Gra]. The file CGAL/Gmpz.h provides the class Gmpz, a wrapper class for the integer type mpz_t, that is compliant with the CGAL number type requirements. The file CGAL/Gmpq.h provides the class Gmpq, a wrapper class for the rational type mpq_t, that is compliant with the CGAL number type requirements.
In addition, it is possible to directly use the C++ number types provided by GMP : mpz_class, mpq_class (note that support for mpf_class is incomplete). The file CGAL/gmpxx.h provides the necessary functions to make these classes compliant to the CGAL number type requirements.
To use this, GMP must be installed.
LEDA provides number types that can be used for exact computation with both Cartesian and homogeneous representations. 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 kernels 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 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.
You can also use your own number type with the CGAL kernel
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
corresponding requirements from Section .