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

From: Barend Gehrels (barend_at_[hidden])
Date: 2008-01-16 11:15:01

Hi Fernando,

Fernando Cacciola wrote:
> 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
>   
Thanks for the clarification. The library uses the epsilon for floating 
point comparisons. Your will see it next week, but it is like this:
            inline bool operator==(const point& other) const {
                if (std::numeric_limits<T>::is_exact) return m_x == 
other.m_x && m_y == other.m_y;
                else return abs(m_x - other.m_x) < 
std::numeric_limits<T>::epsilon() && abs(m_y - other.m_y) < 
std::numeric_limits<T>::epsilon();
            }

If this approach is not enough, you can please help us to make it more 
robust because I agree, the library should handle these issues and not 
the user because that is not possible.
>>> 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?
>   
OGC defines the method isSimple for this, there will be an algorithm 
is_simple.
>>> 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'.
>   
OK, tell me next week if it is bright and simple or just simplistic, I'm 
curious.
> 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
>
>   
Best regards,
Barend Gehrels, Geodan Holding B.V., Amsterdam, the Netherlands