Recursive polygon offset computing for rapid prototyping applications based on Voronoi diagrams

摘要

The generating algorithm of the polygon offsetting is conceptually simple but important, however, geometric problems are very complex. Although some efficient algorithms have been developed to solve it, their computational dependency makes them efficient in only a limited number of line segments of cases. This article presents a recursive algorithm to compute a trimmed offset of a polygon consisting of large-scale line segments in a plane. Assuming that a Voronoi diagram of the polygon is obtained and available, the algorithm constructs topological structures of all Voronoi edges and Voronoi objects: every edge is associated with two Voronoi objects; one object of the Voronoi diagram constitutes the edges. Once the offsetting process starts and intersects with the Voronoi edge of one object, find the next Voronoi object using the topology relation and compute the pairwise intersection in edge. After the rapid prototyping scanning process method has been applied, the result shows that the algorithm is simple and efficient.