摘要
This paper studies the practical generation of Voronoi diagrams for multiply-connected planar areas bounded by line segments. The core of the algorithm was calculating Voronoi polygon of every Voronoi object in planar areas independently. The main approach had two steps. The first step was calculating all relevant bisectors of every Voronoi object. The second was combining obtained bisectors into completed Voronoi polygons individually. All code was implemented in Visual C++ platform. The resulting code was extensively tested in real-world data and its practical running time grew only linearly. Three statistical CPU-consumption charts had been drawn with the Voronoi diagrams computation data, and compared with other published codes for computing Voronoi diagrams. The algorithm was applied to compute offsetting of slice area consisting of large-scale line segments for the selective laser melting (SLM) trajectory scanning technology which is a kind of rapid prototyping (RP). The experimental results of offsetting for slice area based on Voronoi diagrams show that the approach is effective and simple for polygon offsetting problems. The method is helpful to those offsetting work and can provide more effective offsetting solution.
This paper studies the practical generation of Voronoi diagrams for multiply-connected planar areas bounded by line segments. The core of the algorithm was calculating Voronoi polygon of every Voronoi object in planar areas independently. The main approach had two steps. The first step was calculating all relevant bisectors of every Voronoi object. The second was combining obtained bisectors into completed Voronoi polygons individually. All code was implemented in Visual C++ platform. The resulting code was extensively tested in real-world data and its practical running time grew only linearly. Three statistical CPU-consumption charts had been drawn with the Voronoi diagrams computation data, and compared with other published codes for computing Voronoi diagrams. The algorithm was applied to compute offsetting of slice area consisting of large-scale line segments for the selective laser melting (SLM) trajectory scanning technology which is a kind of rapid prototyping (RP). The experimental results of offsetting for slice area based on Voronoi diagrams show that the approach is effective and simple for polygon offsetting problems. The method is helpful to those offsetting work and can provide more effective offsetting solution.
基金
Supported by the National SME Technology Innovation Fund Projects (No. 05C26214201059)
