An adaptive approach for generating Voronoi diagrams for residential areas containing adjacent polygons

This study proposes AVARA, an innovative adaptive Voronoi diagram algorithm explicitly designed for residential areas containing adjacent polygons. AVARA addresses the complex task of balancing computational efficiency and boundary position accuracy in existing Voronoi algorithms based on occurrence element discretization and difficulties constructing Voronoi diagrams for topologically adjacent polygonal objects. AVARA leverages interpolation strategies established on the classification result of neighbor pairs using co-edge relationships of residential area centroids. Additionally, AVARA incorporates graphical Boolean operations and node merging. The experiments used residential area datasets at 1:50,000, 1:10,000, and 1:2,000 map scales. The results showed that AVARA outperformed the Voronoi diagram algorithms based on intervisible points (VBIVP) and the equal-interval dense point method (VBEDP). AVARA achieved the highest accuracy rate in constructing Voronoi diagrams, with a 50% improvement. It also exhibited superior local position accuracy, demonstrating significant time performance improvements of 349.12% and 90.7% using datasets at map scales of 1:50,000 and 1:10,000, respectively. In the experiment using a dataset at a map scale of 1:2,000, AVARA consumed slightly less time than VBEDP with a 0.6 m interval. These findings highlight the significant overall advantage of AVARA. Additionally, the effectiveness of the algorithm was further validated using a large-scale building dataset.