On Tue, Nov 17, 2009 at 6:35 AM, Brandon Kohn <blkohn@hotmail.com> 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