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