Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Steve M. Robbins (steve_at_[hidden])
Date: 2009-03-16 00:38:11

On Sun, Mar 15, 2009 at 11:01:06PM -0200, Fernando Cacciola wrote:
> 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.

Yes.  Roughly speaking, that's what Shewchuk's predicates do: a
floating point filter that, if the filter fails, is followed by an
exact calculation using Priest's expansions.  

It's been a while since I read the papers but IIRC, the filter
computations provide the initial expansions so you don't have to
re-start the exact computation from scratch.  This could be
an additional speed benefit.

-Steve