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 13:01:10

Barend wrote:
> Yes, we've planned a buffer algorithm in the near future. I'm
> currently 
> busy with self-intersections, which have to be addressed by the
> buffering. Then the buffer algorithm might be implemented for a
> geometry. 
> 
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.  Honestly, it should only take under a week to implement booleans once you have edge intersection.  The scanline that computes whether edges are interior can either be factored into the scanline that computes edge intersections or a second pass.  I use a second pass because it is simpler to implement and dramatically easier to validate each algorithm in isolation.  I use a third pass to form up and output polygons and associate their holes to the outer shells.  Once again, it could all be done in one pass, but forming polygons is something you don't want to do if the output is fed immediately into another boolean operation.  Before you cry foul about performance for three passes on scanline, let me state that the memory consumption of my algorithms is significantly lower than other algorithms I've benchmarked, and I've never found a faster implementation.  I'll make sure to have a detailed explanation of my approach to booleans in the boostcon paper and presentation.  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.

> 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);

Regards,
Luke