Polygon offsetting using a Voronoi diagram and two stacks
Authors:
Deok-Soo Kim [Author vitae]
Affiliation:
Department of Industrial Engineering, Banyang University, 17 Haengdang-Dong, Sungdong-Ku, Seoul 133-791, South Korea
Abstract:
The generation of the trimmed offset of a simple polygon is a conceptually simple but important and computationally non-trivial geometric problem for many applications. This article presents a linear time algorithm to compute a trimmed offset of a simple polygon consisting of arcs as well as line segments in a plane. Assuming that a Voronoi diagram of the polygon is available, the algorithm uses two stacks: T-stack and C-stack. The T-stack contains intersections between an offset and Voronoi edges, and the C-stack contains an offset chain which is a part of the trimmed offset. The contents of both stacks are pushed into and popped from the stacks in a synchronized fashion depending on the events that occur during the offsetting process.