Exact and Approximate Construction of Offset Polygons
The offset of complex polygons. The boundary of each input polygon is
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
|The offset of complex polygons.