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

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-06 17:22:49

Barend Gehrels wrote:
>> I'm confused, are you trying to inflate the polygon, find
>> intersections it causes and remove interior edges with some kind of
>> graph traversal of an edge graph data structure that you build from
>> the output of generalized line intersection?  This is one common way
>> to implement booleans, but it is a horribly more complicated and
>> memory intensive than a scanline based approach.
> You're working with integer's Luke. Therefore the scanline approache
> is appropriate for you. As far as I know scanlines is not used for
> floating point. Didn't plan graph traversal for this one, by the way.
> That was the other problem :-)

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?  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.

Regards,
Luke