Re: [boost] GGL Review

Subject: Re: [boost] GGL Review
From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2009-11-18 23:24:06

On Wed, Nov 18, 2009 at 10:52 PM, Steve M. Robbins <steve_at_[hidden]> wrote:
> 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.

I don't know CGAL at all, so I won't argue any of your points, but the
paper does point out cases where it fails with the floating point
types, which I'm fairly sure GGL would fail as well.  The GGL authors
have advised to use exact number types if you require exactness, and
their interfaces are extensible to support this.  It would be great if
they could be extended to the point CGAL is at.  Maybe they already
can?  I have no clue.

Regardless, the point I was trying to make was that (to me) the
interface is more important than the implementation at this stage in
the library's life, and that I don't think it's fair to base
acceptance solely on whether the implementation is 100% robust and
numerically stable unless the documentation states says otherwise.

--Michael Fawcett