
Boost : 
From: Barend Gehrels (barend_at_[hidden])
Date: 20080116 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 multipoint
>> containing two points are delivered, plus a "is_collinear" result.
>>
>> I've seen on your website that you codevelop 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk