Personal tools
You are here: Home Projects In-house Projects Exact and Approximate Construction of Offset Polygons
« October 2017 »
October
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

Exact and Approximate Construction of Offset Polygons

ms_knife

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 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

ms_chain
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 http://www.cs.tau.ac.il/~efif wein@post.tau.ac.il
Dan Halperin http://www.cs.tau.ac.il/~danha danha@post.tau.ac.il
Document Actions