Re: polygon buffering algorithms

And a buffer for a point would be nothing but a circle.

Yes, but that's not a polygon. If you take a line segment, and you take the set of points that at distance d, you get two half circles joined by two line segments - not a polygon either.

Anyway, the problem shouldn't be too hard. Just walk along the original polygon, and create the new 'polygon' piece by piece. For each line segment, it's easy to find the corresponding line segment. Consecutive line segments are joined by arcs, whose origin lies on the vertex of the original polygon. For convex polygons, this is all you need to do. For concave polygon, you might get self-intersections this way. But they are reasonably easy to fix by maintaining a stack of 'polygon' pieces (line segments and arcs), and either deleting the top piece(s), or intersecting with it.

Comment on Re: polygon buffering algorithms

Replies are listed 'Best First'.
Re^2: polygon buffering algorithms by punkish (Priest) on Feb 09, 2005 at 17:02 UTC
>>And a buffer for a point would be nothing but a circle. >Yes, but that's not a polygon. If you take a line >segment, and you take the set of points that at >distance d, you get two half circles joined by two >line segments - not a polygon either. Interesting. Why is that, may I ask? As far as I can see (and I've been working in the GIS field for about 20 yrs believing it to be so), a circle is indeed a polygon as much as a buffer of line is. Btw, in your description above, the buffer is of a single straight-line segment. Of course, a line can be made of any number of line segments, or arcs. A line is nothing but a series of x,y pairs that don't end up where they started. While a polygon is the same as above except the first and the last pair are the same. In any case, the problem actually is surprisingly hard. That is because of all the different manners in which a polygon or a line can be configured. One has to determine the inside vs. the outside worlds wrt the polygon (of course, for buffering, one would want to remain on the outside), which can differ based on the slope of that particular line segment and the direction of one's travel (clockwise vs. counter-clockwise). Then there is the thorny issue of vertices, as brought up above. When all is said and done, it has to be fast. Now, I know there are algorithms out there... well established, because the solution exists in commercial software. I am simply unable to find references to the darn algorithms in published literature so I can start exploring the possibility of building one as an open source solution.	[reply]
Re^3: polygon buffering algorithms by Anonymous Monk on Feb 09, 2005 at 18:17 UTC
My definition of a polygon seems to be equal to the one at math world. And your definition of a polygon seems to be closer to the one of a closed planar curve. I agree that finding all the points of a certain distance away from an arbitrary curve is harder than from a polygon.	[reply]