Re: [boost] GGL Review

Subject: Re: [boost] GGL Review
From: Jonathan Franklin (franklin.jonathan_at_[hidden])
Date: 2009-11-17 11:53:37

On Tue, Nov 17, 2009 at 6:35 AM, Brandon Kohn <blkohn_at_[hidden]> wrote:
> The point I was trying to make was that I
> believe that GGL would be the first library of its kind in Boost that walks
> the line of being provably correct (WRT boolean operations with FP
> coordinates) and that this perhaps means that more care needs to be taken in
> reviewing it.

And if we can provide a strategy (in addition to "normal" FP-based
operations) that fulfills this, then that's totally awesome!  I
*might* actually need it some day.  You need it now.

> Jonathan  replied that for his needs it didn't matter if the
> algorithms were correct, only that they worked most of the time.

WRT FP-induced instability.

> My own view
> is that something that only works part of the time really doesn't work.

I'm sure that's great for whatever you do.  It is valid in many use cases.

The visualization software that I work on, on the other hand, prefers
speed over making sure that point p1 is provably inside or outside the
box.  If it's *that* close, then it doesn't matter.

Or more aptly, when computing the union of many polygons to simply
display an area of coverage, it is much more important to be fast than
to use the provably correct point p1 or p2, which happen to be so
close together, that uncertainty/error in measurement is more
significant than the FP precision.  And it turns out that for my use
case, the points are so close together, either one will do fine.

I posit that the majority of users of a geometry library have similar
needs to my own.

> Why would we really want an algorithm that only works some/most of the
> time in Boost?

I stand by my use case, and I accept yours.

> ... the author of the library needs to
> address these concerns by providing tests proving any (implied) claims of an
> algorithm's correctness.

I agree.

> If this cannot be done at the start, perhaps the
> boolean operations should be omitted until such a time as they can be
> properly proven.

If the operations cannot be shown correct *without* consideration of
FP-precision, then they should be omitted.  In that case, they clearly
would not be ready.

If they can be shown correct, up to FP-precision, then include them,
and document the fact that they are unstable WRT FP-precision.

Once we have provably stable and correct versions, with an easy and
intuitive way to choose the version we want, then we'll rule the pool.
;-)

> Luke seems to have much expertise in the area of boolean
> operations, and has already suggested a battery of tests. I think this would
> be an excellent place to start.

I agree.

Thanks,

Jon