Exact and Approximate Construction of Offset Polygons
![]() |
||
The offset of complex polygons. The boundary of each input polygon is |
Abstract
We describe an efficient and robust implementation of the construction of the Minkowski sum of a polygon in R2 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 | ![]() |
![]() |