Exact and Approximate Construction of Offset Polygons

The offset of complex polygons. The boundary of each input polygon is drawn in a thick black line, and the approximated offset is shaded.

Abstract

We describe an efficient and robust implementation of the construction of the Minkowski sum of a polygon in R² with a disc, an operation known as offsetting the polygon. Our software includes a procedure for computing the exact offset of a straight-edge polygon, based on the arrangement of conic arcs computed using exact algebraic number-types. We also present a conservative approximation algorithm for offset computation that uses only rational arithmetic and decreases the running times by an order of magnitude in some cases, while having a guarantee on the quality of the result. The algorithm is included in the 2D Minkowksi-sum package of CGAL. It also integrates well with other CGAL packages; in particular, it is possible to perform regularized Boolean set-operations on the polygons the offset
procedures generate.

Illustrations

The offset of complex polygons.

Links

Ron Wein.
Exact and approximate construction of offset polygons
Computer-Aided Design, 39(6): 518–527, 2007 [link] [bibtex]

Contact

Ron Wein
Dan Halperin