-------------------------------------------------- From: "Simonson, Lucanus J" <lucanus.j.simonson@intel.com> Sent: Friday, March 06, 2009 5:22 PM To: <boost@lists.boost.org> Subject: Re: [boost] [geometry] area, length, centroid, behavior
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. 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.)
If it can be used to identify the intersection points it can also be used to identify interior edges. It can be the same algorithm that does both in a single pass. How does your generalized line intersection work, if not line scan? I know that it is technically challenging to write a robust linescan on floating point geometry but what practical alternative is there? Even with floating point I can bound how far a segment might move at the current point due to a future intersection snapping to the floating point grid based upon its end points and collect nearby points that may need to intersect it. I haven't done it, but it is possible. Once that algorithm is in place everything else becomes easy.
If your union algorithm doesn't work by scanline and doesn't work by rule-based graph traversal how does it work? These are the only two methods I've heard of.
I have been working on a bsp-tree based version of the boolean ops. The other I know of is the scan-line version (which I gather is the best known.) I suspect that there is a grid based version out there, but I haven't researched it. I would be curious to learn about another as well. Cheers, Brandon