A HYBRID APPROACH TO POLYGON OFFSETTING USING WINDING NUMBERS AND PARTIAL COMPUTATION OF THE VORONOI DIAGRAM

In this paper we present a new, efficient algorithm for computing the raw offset curves of 2D polygons with holes. Prior approaches focus on (a) complete computation of the Voronoi Diagram, or (b) pair-wise techniques for generating a raw offset followed by removal of invalid loops using a sweepline algorithm. Both have drawbacks in practice. Robust implementation of Voronoi Diagram algorithms has proven complex. Sweeplines take O((n+k) logn) time and O(n+k) memory, where n is the number of vertices and k is the number of self-intersections of the raw offset curve. It has been shown that k can be O(n2) when the offset distance is greater than or equal to the local radius of curvature of the polygon, a regular occurrence in the creation of contour-parallel offset curves for NC pocket machining. Our O(nlogn) recursive algorithm, derived from Voronoi diagram algorithms, computes the velocities of polygon vertices as a function of overall offset rate. By construction, our algorithm prunes a large proportion of locally invalid loops from the raw offset curve, eliminating all self-intersections in raw offsets of convex polygons and the near-circular, k proportional to O(n2) worst-case scenarios in non-convex polygons.