polygon buffering algorithms

punkish has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: polygon buffering algorithms by thor (Priest) on Feb 08, 2005 at 17:39 UTC
If you have a set of lines that represents a closed polygon, the following pseudo-code should work `foreach edge (edges in polygon, clockwise) construct parallel line distance d from edge, store it in an array done foreach parallel line find intersection with next line in array, allowing for wrap around store intersection in an array done #intersections are the vertexes of your new polygon` [download] If you need more, let us know. thor `Feel the white light, the light within Be your own disciple, fan the sparks of will For all of us waiting, your kingdom will come`	[reply] [d/l]
Re^2: polygon buffering algorithms by ikegami (Patriarch) on Feb 08, 2005 at 18:17 UTC
................................... ................................... ................................... ................................... .....!!!!!!!!!!!!!!!!!!!!!!!!!..... .....!!!!!!!!!!!!!!!!!!!!!!!!!..... .....!!!!!!!!!!!!!!!!!!!!!!!!!..... .....!!!!!!!!!!!!!!!!!!!!!!!!!..... ...............!!!!!!!!!!!!!!!..... ...............!!!!!!!!!!!!!!!..... .....!!!!!!!!!!!!!!!!!!!!!!!!!..... .....!!!!!!!!!!!!!!!!!!!!!!!!!..... .....!!!!!!!!!!!!!!!!!!!!!!!!!..... .....!!!!!!!!!!!!!!!!!!!!!!!!!..... ................................... ................................... ................................... ................................... [download] The above with $d == 3 gives a weird polygon, but that's ok as long you're expecting it. Read more... (854 Bytes)	[reply] [d/l] [select]
Re^3: polygon buffering algorithms by thor (Priest) on Feb 08, 2005 at 19:13 UTC
You're right...the algorithm that I outlined works for convex polygons. In order to deal with polygons with concavities, I believe that you need to allow for overlap and take the union of all points that lie in the interior. In the case of the polygon that you gave, it would then be a square. Just for my own edification, what is the $d that you're referring to? thor `Feel the white light, the light within Be your own disciple, fan the sparks of will For all of us waiting, your kingdom will come`	[reply]
Re^4: polygon buffering algorithms by ikegami (Patriarch) on Feb 08, 2005 at 19:53 UTC
Re: polygon buffering algorithms by TedPride (Priest) on Feb 08, 2005 at 16:50 UTC
How do you want corners handled? With curves? Does the distance only matter between two lines?	[reply]
Re^2: polygon buffering algorithms by punkish (Priest) on Feb 08, 2005 at 16:57 UTC
How do you want corners handled? With curves? Does the distance only matter between two lines? Frankly, I really don't know. In the case of certain corners (such as the vertex of a square or a triangle, it is intuitively quite simple. Ordinarily, every point on the outer polygon should be 'd' distance from the corresponding point in the inner polygon. Of course, a triangle's vertex creates an interesting problem. However, the vertex of the outer polygon can be 'd' distance from the vertex of the inner polygon in two different directions, with some kind of smoothing curve in between. This is geography, so accuracy is not as important as reliability. As long as we intuitively know that the resulting buffer is more or less correct, no one is going to quibble.	[reply]
Re^3: polygon buffering algorithms by Solo (Deacon) on Feb 08, 2005 at 17:01 UTC
accuracy is not as important as reliability I understand the difference between accuracy and precision, but could you please explain what you mean by accuracy vs. reliability? (Google is not as helpful here.) Update: added links to definition --Solo -- You said you wanted to be around when I made a mistake; well, this could be it, sweetheart.	[reply]
Re^4: polygon buffering algorithms by punkish (Priest) on Feb 08, 2005 at 17:06 UTC
Re: Accuracy vs. Reliability by Solo (Deacon) on Feb 08, 2005 at 17:13 UTC
Some notes below your chosen depth have not been shown here
Re: polygon buffering algorithms by tall_man (Parson) on Feb 08, 2005 at 21:15 UTC
Math::Geometry::Planar has some good polygon manipulation libraries, including an interface to GPC for polygon intersection and clipping. For your buffering problem, try Math::Geometry::Planar::Offset.	[reply]
Re: polygon buffering algorithms by Anonymous Monk on Feb 09, 2005 at 10:51 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. 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.	[reply]
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]
Re: polygon buffering algorithms by BrowserUk (Patriarch) on Feb 08, 2005 at 17:21 UTC
How is your polygon represented? A set of vertecies? A Bezier spline? Examine what is said, not who speaks. Silence betokens consent. Love the truth but pardon error.	[reply]
Re^2: polygon buffering algorithms by punkish (Priest) on Feb 08, 2005 at 18:17 UTC
How is your polygon represented? A set of vertecies? A Bezier spline? A set of verticies	[reply]