A novel computation algorithm of Voronoi diagrams for multiply-connected planar areas
Abstract
This paper studies the practical generation of Voronoi diagrams of multiply-connected planar areas bounded by straight line segments. The key idea of the algorithm consists in calculating Voronoi polygon of every Voronoi object in planar areas independently. The main approach is divided into two steps. The first step is to calculate all relevant bisectors of the all Voronoi objects, and the second is to combine obtained bisectors into completed Voronoi polygons individually. The contents of steps are both very important and all codes are implemented in Visual C++ platform. The resulting codes are tested extensively on real-world data, and its practical running time seems to grow only linearly. Three statistical CPU-consumption charts have been drawn with the Voronoi diagrams computation data. The CPU-time consumptions records also gain the advantages over other published codes for computing Voronoi diagrams. The development of the algorithm is achieved by treating equidistant generation as a locus-tracing problem.
Related Papers
- The generalization and construction of Voronoi diagram and its application on delimitating city's affected coverage(2002)
- → Voronoi Diagrams Generated by the Archimedes Spiral(2023)5 cited
- TOOLPATH GENERATION FOR POCKETS BOUNDED BY FREEFORM CURVES BASED ON THE VORONOI DIAGRAM(1999)
- → A new generalized Voronoi diagram in the plane(1988)
- A parallel algorithm of constructing a Voronoi diagram on hypercube connected computer networks(1994)