Interval Arithmetic (CGAL_Interval_nt)

This chapter describes briefly what interval arithmetic is, its implementation in CGAL, and its possible use by geometric programs. The main reason for having interval arithmetic in CGAL is its integration into the filtered robust and fast predicates scheme, but we also provide a number type so that you can use it separately if you find any use for it.

The purpose of interval arithmetic is to provide an efficient way to bound the roundoff errors made by floating point computations. You can choose the behaviour of your program depending on these errors; that is what is done for the filtered robust predicates (see Section ). You can find more theoretical information on this topic in [BBP98].

Definition

$$ \forall x \in X, \forall y \in Y, (x OP y) \in (X OP Y) $$

For example, if the final result of a sequence of arithmetic operations is an interval that does not contain zero, then you can safely determine its sign.

#include <CGAL/Interval_arithmetic.h>

Creation

CGAL_Interval_nt *this ( double d);
	introduces the interval [d;d].
CGAL_Interval_nt *this ( double i, double s);
	introduces the interval [i;s].

Several functions CGAL_convert_to<CGAL_Interval_nt>(NT) provide a cast from all supported numerical types, to an interval CGAL_Interval_nt containing the value. The following types are supported: leda_real, leda_rational, leda_integer, leda_bigfloat, CGAL_Gmpz, CGAL_Fixed_precision_nt, and all built-in types. The user can add such functions for his own number types.

Operations

All functions required by a class to be considered as a CGAL number type (see ) are present, as well as the utility functions, sometimes with a particular semantic which is described below. There are also access functions to the bounds of the intervals.

CGAL_Interval_nt	I / J	returns [$-infinity$;$+infinity$] when the denominator contains 0.
CGAL_Interval_nt	sqrt ( I)	returns [0;sqrt(upper_bound(I))] when only the lower bound is negative (expectable case with roundoff errors), and is unspecified when the upper bound also is negative (unexpected case).
double	CGAL_to_double ( I)
		returns the middle of the interval, as a double approximation of the interval.
double	I.lower_bound ()	returns the lower bound of the interval.
double	I.upper_bound ()	returns the upper bound of the interval.

The comparison operators (, $>$, , $>=$, $==$, $!=$, CGAL_sign() and CGAL_compare()) have the following semantic: it is the intuitive one when for all couples of values in both intervals, the comparison is identical (case of non-overlapping intervals). This can be expressed by the following formula ($x$ and $y$ are reals, $X$ and $Y$ are intervals, $$OP is a comparison operator):

$$ (\forall x \in X, \forall y \in Y, (x OP y) = true) \Rightarrow (X OP Y) = true $$ and $$ (\forall x \in X, \forall y \in Y, (x OP y) = false) \Rightarrow (X OP Y) =false $$

Otherwise, the comparison is not safe. Then the behaviour is the following:

• By default, the exception CGAL_Interval_nt_advanced::unsafe_comparison is thrown.
• If you compile with the flag -DCGAL_IA_NO_EXCEPTION, the exception is not thrown, but you get a warning instead. The return value is unspecified.
• Moreover, you can also get rid of the warning by adding -DCGAL_IA_NO_WARNINGS or -DCGAL_NO_WARNINGS. The return value is unspecified too.

Implementation