Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-15 21:01:06

Hi Steve,

> On Sat, Mar 14, 2009 at 04:26:35PM -0200, Fernando Cacciola wrote:
> 
>> IMO, any geometric library should provide a toolbox of exact predicates  
>> (which shoud be exact independetly of the input type) 
> 
> I agree.
> 
> I've always thought that the adaptive floating-point arithmetic of
> Douglas Priest [1] and Jonathan Shewchuk [2] would be a good way to do
> this for floats and doubles.

These techniques are excelent tools for providing (adaptive) extended 
precision number types. OTOH, it would hurt performance unneccesarily 
too much if these are not coupled with interval arithmentic to detect 
the need for the extra precision in the first place. I know that as a 
fact because I've implemented Priest's expansions once, many years ago.

IOW, following the simple foating-point filter I sketeched before, 
Priest's expasions would be the exact number type in there.

 > Any interest in developing a boost
> version of this code?
> 
> [1]http://www.cs.cmu.edu/afs/cs/project/quake/public/papers/related/Priest.ps
 > [2] http://www.cs.cmu.edu/~quake/robust.html

I would love to see a boost implementation of Priest's expansions. For 
algebraic operations is, AFAICT, faster than conventional big-floats.

A down side though is that you can't have exact roots with that, and 
there are some algorithm that can't go without them.

Best

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com