Re: [boost] GGL Review

Subject: Re: [boost] GGL Review
From: Steve M. Robbins (steve_at_[hidden])
Date: 2009-11-18 22:52:49

On Tue, Nov 17, 2009 at 12:36:46PM -0500, Michael Fawcett wrote:

> This discussion raises some important implementation considerations,
> but for the purposes of this review, the discussion should simply be
> "Are we requiring that the implementation be provably 100% robust and
> 100% numerically stable before acceptance?".
> 
> If the answer to that is yes, then I think we are holding GGL at a
> *much* higher standard than previously accepted libraries (I'm not
> talking about any specific library).  Note that even CGAL, a highly
> regarded library failed that paper's tests.

I don't think that is what the paper says.  

CGAL uses a traits mechanism to allow the user to select the geometric
kernel, which includes the coordinate number type and the kind of
predicates and constructions used.  You are allowed to use floating
point numbers and naive predicates.  The algorithms will certainly
fail.  The point of the paper is precisely this.

But CGAL does not stop there: you can use the *same* algorithms but
with exact number types for coordinates.  This will work, but
generally be very slow.  One of the features of CGAL, however, is that
you can get the best of both worlds: use floating point coordinates
but still perform exact predicates.  Using floating-point filters the
speed can be competitive with the naive algorithm, but without the
crashes.

-Steve