Polygon offsetting using a Voronoi diagram and two stacks

✍ Scribed by Deok-Soo Kim

• Book ID: 104110629
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 370 KB
• Volume: 30
• Category: Article
• ISSN: 0010-4485
• DOI: 10.1016/s0010-4485(98)00063-3

✦ Synopsis

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.