Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk