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

Speakers

Gregory Burton
Event

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.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

FIND OUT MORE
Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for Commercialization.

FIND OUT MORE
News

Our scientists and staffers are active members and contributors to the science and technology communities.

FIND OUT MORE