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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk