Re: [boost] Is there any interest in a template geometry library?

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).

See:

http://www.cgal.org/philosophy.html

>> 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

http://tinyurl.com/2os9co

Best

-- 
Fernando Cacciola
SciSoft
http://fcacciola.50webs.com