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
