Robust filtered predicates (Filtered_exact)

The class Filtered_exact<CT,ET> is a wrapper type for the number type CT, with the difference that all predicates are specialized such that they are guaranteed to be exact. Speed is achieved via a filtering scheme using interval arithmetic (see Section ). Here are the necessary requirements:

• CT is the construction and storage type. The only data member of the class Filtered_exact<CT,ET> is the value of type CT. All arithmetic operations performed outside of the predicates will be executed with this number type. You can disallow these operations compiling with the flag CGAL_DENY_INEXACT_OPERATIONS_ON_FILTER (it allows you to spot the inexact operations that should be incorporated in the predicates). The arithmetic operations called from inside the predicates are always computed exactly.
• The ET type must be able to compute exactly the operations involved in the predicates called.
• A convert_to<Interval_nt_advanced>(CT) function must be provided, that returns an interval containing the value of the argument of type CT, see Section .
• A convert_to<ET>(CT) function must also be provided, that returns a number of type ET representing exactly the argument of type CT. It's a conversion function that is used for the exact computation, when the filter fails. This conversion has to be done exactly to ensure robustness.

The following member functions are used to access the numerical value for the different number types:

CT	*this.value ()	returns the wrapped value.
ET	*this.exact ()	returns the converted value to ET.
Interval_nt_advanced
	*this.interval ()	returns the converted value to Interval_nt_advanced.

This type actually has additional parameters for experimental features. They will be documented when they will be considered stable, in a next release.

Example

You might use at the beginning of your program a typedef as follows:

    #include<CGAL/Arithmetic_filter.h>
    #include<CGAL/leda_real.h>
    #include<CGAL/double.h>
    typedef Filtered_exact<double, leda_real> NT;

Or if you are sure that the predicates involved do not use divisions nor square roots:

    #include<CGAL/Arithmetic_filter.h>
    #include<CGAL/Gmpz.h>
    #include<CGAL/int.h>
    typedef Filtered_exact<int, Gmpz> NT;

And if you know that the double variables contain integer values, you can use:

    #include<CGAL/Arithmetic_filter.h>
    #include<CGAL/Gmpz.h>
    #include<CGAL/double.h>
    typedef Filtered_exact<double, Gmpz> NT;

As a general rule, we advise the use of Filtered_exact<double, leda_real>.

Implementation

The template definition of the low level predicates of CGAL are overloaded for the type Filtered_exact<CT,ET>. It is a partial specialisation, which implies that this is not supported by the compilers that do not support correctly this C++ feature (for which we set CGAL_CFG_MATCHING_BUG_2). A workaround is in place that allows you to use one such filtered number type at once, by explicitely fully specializing the predicates for it. To do so, just define the macros CGAL_IA_CT and CGAL_IA_ET to the corresponding number types before any inclusion of CGAL files, as well as CGAL_IA_CACHE. For example :

 
#define CGAL_IA_CT double
#define CGAL_IA_ET leda_real
#define CGAL_IA_CACHE No_Filter_Cache

For each predicate file, the overloaded code is generated automatically by a PERL script (scripts/filtered_predicates_generator.pl) that you can use for your own predicates. This script parses the template functions and generates the overloaded code the following way:

• convert the entries to intervals using convert_to<Interval_nt_advanced>(CT), using the interval() member function,
• call the original template function with the type Interval_nt_advanced,
• if no exception is thrown, return the value,
• if an exception is thrown (the filter failed), convert the original entries using convert_to<ET>(CT), using the exact() member function,
• and call the original template function with the type ET.

Example

The low level template predicates of CGAL are in files named CGAL/predicates/kernel_ftC2.h (resp. ftC3), the script is used to produce the files CGAL/Arithmetic_filter/predicates/kernel_ftC2.h (resp. ftC3).

For the moment, only the cartesian predicates of the kernel are supported, as well as the power tests used by the regular triangulation.