Re: [boost] GGL Review

Subject: Re: [boost] GGL Review
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2009-11-16 09:06:54

Phil Endecott wrote:
> The other controversial implementation issue is floating-point 
> robustness.  I'm still not clear what the position of this library is on 
> that.  Are we just given assurances that it seems to be robust in 
> real-world use, or is it believed that it actually is certainly robust?  
> I expected to see this discussed in the library documentation, but I 
> don't see anything - maybe I've missed it.  If it is "believed to be 
> robust in real-world use", it would be helpful to describe the possible 
> failure modes (e.g. segfault, runs forever, or just outputs the wrong 
> answer.)
> 

This is an issue that troubles me as well. I think that a floating point 
computational geometry library is possibly a first for Boost in that you 
often have heuristics rather than algorithms due to the fuzzy effect of 
using floating types in comparison predicates. One of the more useful 
features of the library (GGL) would of course be the boolean operations. 
The problem however is clearly going to be robustness. I have never 
encountered a robust floating point boolean operation library in my 9 
years of working in the geometry domain. While this may not mean it's 
impossible, I think it does mean it's unlikely. This is the reason why 
Boost.Polygon uses integral types. So a good question is how should the 
community judge whether such an algorithm based on floating types is 
acceptable into Boost? I think we've all come to expect that when we 
adopt a Boost library into our work, it should be correct. I would 
suggest the requirement that the library authors demonstrate that their 
algorithm is both correct and robust. We as a community should help 
define how this is done.

Regards,

Brandon