Boost logo

Boost :

From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2008-01-16 08:15:53

Hi Barend,

>>> Is there any interest in a template geometry library?
>> Depends on the details ;)
> Details will follow next week, I'll post a sort of preview including
> sources, some examples and some documentation. I shortly answer your
> questions below.
OK. I'm looking forward to seeing the code then.

>> How does it handle robustness issues?
Since you haven't answered this question I pressume that it doesn't handle
robustness issues at all.

Or the question wasn't clear enough so let me reprhase it:

What if I'm using 'double' as the coordinate type and I test containment of
a point which happens to be a tiny epsilon away from a vertex?

That is, is the library sensitive to roundoff? If so, this can be a problem
considering that techniques to handle this exists and are implemented for
instance in CGAL.

AFAICT, there is the presumption that roundoff problems are imposible or
impractical to handle so a library should just ignore them. That's not
correct. In C++, they can be easily handled for a usable subset of the
typical geometric computations (the so called predicates).


>> What are the geometric requirements on the input polygon? (i.e. must be
>> simple? strictly simple?)
>> What if the point is exactly *over the boundary* of the polygon?
> Good questions, polygons are considered as in OGC, simple, their outer
> ring and inner rings (if any) should not be (self)intersecting.
Can a user determine the "validity" of a polygon?

>> What if the segments are collinear (hence their intersection is another
>> segment)?
>> How does it handle robustness issues?
> This is handled, the intersection_result gives information about how the
> segments intersect. If the intersection is another segment a multi-point
> containing two points are delivered, plus a "is_collinear" result.
> I've seen on your website that you co-develop CGAL. Don't expect
> something like CGAL here,

In scope, certainly, I wouldn't.

But I expect any geometric computing library, regardless of its extension,
to implement the fundamental techniques of the field. In particular, those
aimed to isolate users from numerical issues.

> compared to CGAL this library relatively basic, small and simple

If the library *unnecesarily* fails to produce correct results because of
numerical issues then it's not 'simple' but 'simplistic'.

Please don't get me wrong, I keep turning down libraries for this very
reason over and over not becasue I'm biased toward CGAL but because the
proper techniques
have been around for years, so I see little justification in ignoring them,
pushing the burden on end users, unnecesarily.

The following recent discussion illustrates the importance of properly
handling robustness issues in geometric computing


Fernando Cacciola

Boost list run by bdawes at, gregod at, cpdaniel at, john at