Re: [boost] [geometry] area, length, centroid, behavior

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-03-08 06:49:46

Brandon Kohn wrote:
> Simonson, Lucanus J wrote:
> > I'm still confused.  Why isn't scanline suitable for floating point?
> > Isn't generalize line intersection with floating point generally
> > implemented as a scanline patterned after Bentley-Ottmann?
>
> I don't really know what algorithm is most often used for floating point (I
> would suspect bsp tree based for boolean ops due to the graphics
> applications). For generalized line intersection in FP my bet would be that
> the brute force is the most often used. The Bentley-Ottmann is a great
> algorithm, but it is a serious pain to implement in floating point due to
> problems maintaining a stable sorting of the segment intersections with the
> sweep-line. Precision really becomes a hairy issue with this.

Is it really just the problem of maintaining a stable sorting of the segment intersections with the sweep-line? This will surely require some care, but doesn't sound like a fundamental issue ruling out Bentley-Ottmann for floating point. What looks more nasty to me is that for nearly parallel segments, Bentley-Ottmann has to compute the intersection point of the corresponding lines, even if it is not an intersection point of the segments. But perhaps a simple modification of Bentley-Ottmann can avoid the need to depend on "false" intersection points. I'm just wondering whether there are more fundamental issues ruling out a Bentley-Ottmann type algorithm applied to floating point than "simple" stable sorting issues.

>  I have a
> faithful implementation of the algorithm from a text-book which still
> manages to fail on occasion (even with fuzzy comparisons though not so
> frequently as without.)

I don't think that fuzzy comparison is a good idea when you want to make Bentley-Ottmann robust for floating point. You will have to ensure that "important decisions" are only computed once, and enforce that no other intermediate/computed result can contradict these "decisions".

Assuming it is possible to make a Bentley-Ottmann type sweep-line algorithm robust against floating point issues, what other issues will have to be considered when deciding which algorithm to use?

Regards,
Thomas