Boost logo

Boost :

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at