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.
http://www.math.niu.edu/~rusin/known-math/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