Search
Close this search box.

Exact and Approximate Construction of Offset Polygons

Abstract

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

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

Exact and Approximate Construction of Offset Polygons
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]

Contacts

Ron Wein
Dan Halperin
@article{w-eacop-07,
author = {Ron Wein},
title = {Exact and approximate construction of offset polygons},
journal = {Computer-Aided Design},
volume = {39},
number = {6},
year = {2007},
pages = {518--527},
doi = {10.1016/j.cad.2007.01.010}
}

Yair Oz - Webcreator

Contact

Skip to content