Re: [boost] GGL Review

Subject: Re: [boost] GGL Review
From: Mateusz Loskot (mateusz_at_[hidden])
Date: 2009-11-16 17:05:04

Brandon Kohn wrote:
> 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.

Certainly, I'm not going to argue with the float-point issues you point
on. They exist, of course. I've been working in GIS for a while and I
understand the problem we're discussing here.

However, I'd like to make, perhaps, an interesting observation.
There is a Open Source computational geometry library [1] that is
dedicated to GIS domain and is widely used in GIS products.
I've been involved in its development for a couple years, and I may
only confirm, again, that FP vs robustness problems loomed large in
our minds.

In spite of the fact this library is configurable regarding precision
model user wants to use, what's interesting, in most use cases of the
library I've seen, in geographical data processing libraries, geospatial
databases as well as in regression tests cases of this particular
library, float-point model is used at most.

BTW, GGL has been tested in comparison to this library.

[1] http://trac.osgeo.org/geos/
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org