A Raster Voronoi Diagram Generating Algorithm Using Edge Attribution and Bilateral Scanning

被引：0

作者：

Wang, Lei ^{[1
]}

Song, Zhixue ^{[1
]}

Yin, Nan ^{[1
]}

Cheng, Gang ^{[1
]}

机构：

[1] School of Surveying and Land Information Engineering, Henan Polytechnic University, Jiaozuo

来源：

Wuhan Daxue Xuebao (Xinxi Kexue Ban)/Geomatics and Information Science of Wuhan University | 2024年 / 49卷 / 12期

关键词：

bilateral scanning; edge attribution; Voronoi diagram;

D O I：

10.13203/j.whugis20220110

中图分类号：

学科分类号：

摘要：

Objectives: Voronoi diagram is an important research direction in the field of computational geometry, and the generation algorithm of Voronoi diagram is a key technology in this field. The deterministic attribution algorithm, which meets the discrete characteristics of computer, is one of the most accurate raster Voronoi diagram generation algorithms, but this algorithm is not efficient for processing large amounts of data. Methods: In this paper, a raster Voronoi generation algorithm based on the combination of edge attribution and bidirectional scanning is proposed to address the above problem. Based on an in-depth investigation of the reasons for the excellent accuracy and low efficiency of the deterministic attribution algorithm, the Voronoi attribution of neighboring raster is transferred by attribution of its neighboring raster. First, the boundary raster is given to Voronoi region attribution by deterministic attribution calculation, a 3×3 neighboring domain template is established, and the forward scanning is performed by using the domain template. Then, the correctness of Voronoi attribution of all the rasters is ensured by reverse error correction based on the forward scanning results. Results: Experimental comparison using data of different sizes shows that the proposed algorithm has the same accuracy as the deterministic attribution algorithm. Compared with the deterministic attribution algorithm, the proposed algorithm can save more than 80% of the computation and the time efficiency is 4 times more than that of the deterministic attribution algorithm. Conclusions: The proposed algorithm retains good accuracy and greatly improves the time efficiency. The larger the amount of data, the more obvious the advantage of the proposed algorithm. © 2024 Editorial Department of Geomatics and Information Science of Wuhan University. All rights reserved.

引用

页码：2323 / 2328

页数：5

共 21 条

[1]

Huahao Shou, Ziwei Yuan, Yongwei Miao, Et al., The Voronoi Diagram of Two-Dimensional Shape with Algebraic Curve Boundary［J］, Computer Science and Application, 1, 2, pp. 39-43, (2011)

[2]

Huahao Shou, Ziwei Yuan, Yongwei Miao, Et al., A Subdivision Algorithm for Voronoi Diagram of Planar Point Set［J］, Journal of Graphics, 34, 2, pp. 1-6, (2013)

[3]

Qingping Liu, Xuesheng Zhao, Lei Wang, Et al., A Raster Voronoi Diagram Generation Algorithm Based on Horizontal-Longitudinal Scanning［J］, Acta Geodaetica et Cartographica Sinica, 48, 3, pp. 393-399, (2019)

[4]

Lei Meng, Junwei Zhang, Xiaoting Wang, Et al., An Improved Incremental Algorithm for Voronoi Diagram［J］, Journal of Image and Graphics, 15, 6, pp. 978-984, (2010)

[5]

Huahao Shou, The Voronoi Diagram of Two-Dimensional Shape with Algebraic Curve Boundary ［J］, Computer Science and Application, 1, 2, pp. 39-43, (2011)

[6]

Haifei Si, Zhen Shi, Hongjian Wang, Et al., Research on Voronoi Diagrams Generation Algorithm for Multi-point Dynamic Objects in Two-Dimensional Space［J］, Journal of Jinling Institute of Technology, 36, 1, pp. 1-5, (2020)

[7]

Shamos M I，, Hoey D., Closest-Point Problems, 16th Annual Symposium on Foundations of Computer Science, (1975)

[8]

Wensen Tu, Jiajia Wang, Raster-Based Method for Voronoi Diagram Using GPU Parallel Technology ［J］, Modern Electronics Technique, 38, 4, pp. 66-68, (2015)

[9]

Shuyan Li, Han Cao, Niling Liu, Generation Parallel Algorithm Research of Vorenoi Diagram［J］, Journal of Zhengzhou University of Light Industry （Natural Science, 25, 1, pp. 105-109, (2010)

[10]

Held M., VRONI：An Engineering Approach to the Reliable and Efficient Computation of Voronoi Diagrams of Points and Line Segments［J］, Computational Geometry, 18, 2, pp. 95-123, (2001)

← 1 2 3 →