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

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2009-03-07 08:04:52

--------------------------------------------------
From: "Simonson, Lucanus J" <lucanus.j.simonson_at_[hidden]>
Sent: Friday, March 06, 2009 5:22 PM
To: <boost_at_[hidden]>
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