Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-03-06 16:54:15
> 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 :-)
> If we get to the point where we can share code you could use directly my algorithms for removing interior edges and forming polygons as long as you provide a robust line intersection. Then buffering becomes a one day programming exercise.
Sounds good. But also feasable if you use boolean/scanline approach and
I use double's?
>> Buffering is special in that sense that buffering one polygon can
>> have a different output from buffering two polygons. So besides the
>> buffer(polygon) you'll probably also need a buffer algorithm on a
>> collection. Same for linestrings, points. As also described in the
>> PDF-link you gave. Other issues are buffer-outside, buffer-inside,
>> holes which might disappear. And multi geometries (of course related
>> to the collection).
> No, you need one algorithm that works on a collection and if the collection happens to have only one polygon you have also your algorithm that works on one polygon.
> result_of_inflate = inflatePolygons(&polygon, &polygon+1);
Sure. But the internal algorithm is different. Either self-intersection,
or that plus unions. They are related of course so indeed we might see
if they can be combined.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk