From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: polygon buffer - computer algorythm Date: 18 Mar 1998 05:39:35 GMT In article <6ec4rh$mck$1@nnrp1.dejanews.com>, wrote: >Given a polygon defined in 2-D space as a series vertices (cartesian >coordinates). How do I define a new polygon which is equal to the original >polygon plus a buffer of a specified width around perimeter of the polygon? What do you want for an answer when, say, the polygon is a triangle? I can describe another triangle whose sides are parallel to the original triangle's sides but are a perpendicular distance d away; but the new one's vertices are further than d units away from the original -- is that OK? Getting the new edges is trivial: every line in the plane may be written in the form a x + b y = c for a unique unit vector (a,b) pointing to the outside of the polygon. The line parallel to this but d units out is given by a x + b y = c + d. >I need it in a formula that can easily be reproduced in a program. Thanks for >your help. Given the ordered list P0, P1, ..., Pn = P0 of points traversing the polygon counterclockwise, compute in turn the vector (r,s) = P_(i+1) - P_i the outward normal (s,-r) the unit outward normal (a,b) the new-line L_i: a x + b y = (a x_i + b y_i) + d the intersection Q_i with the previous new-line L_(i-1) for each i. These points Q_i are the vertices of your new polygon (in what I assume is the preferred format for specifiying a polygon). Note that you said "easily", not "efficiently" or "stably". If I did this for a living I'd probably write a real algorithm, not just a naive translation of mathematics into code :-) In particular, for nonconvex polygons, you have to watch out for self-intersections etc. If you really need the set of points which are a perpendicular distance away from the original polygon, you need to replace the corners of the new polygon with circular arcs. This new curve is the _envelope_ of the original one; see e.g. index/14HXX.html dave ============================================================================== From: Jeff Erickson Newsgroups: sci.math Subject: Re: polygon buffer - computer algorithm Date: Wed, 18 Mar 1998 23:28:51 -0500 Dave Rusin wrote: > > wrote: > > Given a polygon defined in 2-D space as a series of vertices, > > How do I define ... a buffer of a specified width around > > the perimeter of the polygon? > > [describes how to compute a buffer for a convex polygon] > In particular, for nonconvex polygons, you have to watch out for > self-intersections etc. ...and this is hard! Programs that compute offset polygons, like Adobe Illustrator, simply punt and give you self-intersecting output. Even defining exactly what the offset polygon should look like is nontrivial if the original polygon is nonconvex. The "correct definition, in my opinion, is the the result of growing the offset polygon outward from the original polygon. Whenever an offset vertex runs into an offset edge, split the offset polygon into two pieces at the point of collision and continue. Whenever an offset edges shrinks down to a point, delete it, create a new offset vertex, and continue. The fastest practical algorithm for computing offset polygons runs in O(n^2) time where n is the number of edges in the original polygon. Perhaps counter to intuition, you can do slightly better if most of the vertices of the polygon are CONCAVE. The time bound becomes O(n log n + nr), where r is the number of CONVEX vertices. If the polygon is totally convex, you can compute any offset polygon in linear time using exactly the algorithm Dave described. For details, see the following web pages: http://www.cs.duke.edu/~jeffe/open/skeleton.html http://www.cs.duke.edu/~jeffe/pubs/cycles.html http://www.iicm.edu/jucs_1_12/a_novel_type_of > If you really need the set of points which are a perpendicular > distance away from the original polygon, you need to replace the > corners of the new polygon with circular arcs. This is not the right way to think about it, since you have to know what the polygon is first. Rounded offset curves are MUCH easier to compute than mitered offset polygons. See Martin Held's research web page for a good description of offset curves and how to compute them efficiently: http://www.cosy.sbg.ac.at/~held/projects/voronoi_2d/voronoi.html -- Jeff Erickson Center for Geometric Computing jeffe@cs.duke.edu Department of Computer Science http://www.cs.duke.edu/~jeffe Duke University