| Citation: |
WANG Lei, SONG Zhixue, YIN Nan, CHENG Gang. A Raster Voronoi Diagram Generating Algorithm Using Edge Attribution and Bilateral Scanning[J]. Geomatics and Information Science of Wuhan University, 2024, 49(12): 2323-2328. DOI: 10.13203/j.whugis20220110
|
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.
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.
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.
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.
| [1] |
寿华好, 袁子薇, 缪永伟,等. 以代数曲线为边界的二维形体的Voronoi图[J]. 计算机科学与应用, 2011, 1（2）： 39-43
Shou Huahao, Yuan Ziwei, Miao Yongwei, et al. The Voronoi Diagram of Two-Dimensional Shape with Algebraic Curve Boundary[J]. Computer Science and Application, 2011, 1（2）：39-43
|
| [2] |
寿华好, 袁子薇, 缪永伟, 等. 一种平面点集Voronoi图的细分算法[J]. 图学学报, 2013, 34（2）： 1-6.
Shou Huahao, Yuan Ziwei, Miao Yongwei, et al. A Subdivision Algorithm for Voronoi Diagram of Planar Point Set[J]. Journal of Graphics, 2013, 34（2）： 1-6.
|
| [3] |
刘青平, 赵学胜, 王磊, 等. 横-纵扫描的Voronoi图栅格生成算法[J]. 测绘学报, 2019, 48（3）： 393-399.
Liu Qingping, Zhao Xuesheng, Wang Lei, et al. A Raster Voronoi Diagram Generation Algorithm Based on Horizontal-Longitudinal Scanning[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48（3）： 393-399.
|
| [4] |
孟雷, 张俊伟, 王筱婷, 等. 一种改进的Voronoi图增量构造算法[J]. 中国图象图形学报, 2010, 15（6）： 978-984.
Meng Lei, Zhang Junwei, Wang Xiaoting, et al. An Improved Incremental Algorithm for Voronoi Diagram[J]. Journal of Image and Graphics, 2010, 15（6）： 978-984.
|
| [5] |
Shou Huahao. The Voronoi Diagram of Two-Dimensional Shape with Algebraic Curve Boundary[J]. Computer Science and Application, 2011, 1（2）： 39-43.
|
| [6] |
司海飞, 史震, 王宏健, 等. 二维空间多点动态目标Voronoi图生成算法研究[J]. 金陵科技学院学报, 2020, 36（1）： 1-5.
Si Haifei, Shi Zhen, Wang Hongjian, et al. Research on Voronoi Diagrams Generation Algorithm for Multi-point Dynamic Objects in Two-Dimensional Space[J]. Journal of Jinling Institute of Technology, 2020, 36（1）： 1-5.
|
| [7] |
Shamos M I, Hoey D. Closest-Point Problems[C]//16th Annual Symposium on Foundations of Computer Science, Washington D C, USA, 1975.
|
| [8] |
屠文森, 汪佳佳. Voronoi图栅格生成算法GPU并行实现[J]. 现代电子技术, 2015, 38（4）： 66-68.
Tu Wensen, Wang Jiajia. Raster-Based Method for Voronoi Diagram Using GPU Parallel Technology[J]. Modern Electronics Technique, 2015, 38（4）： 66-68.
|
| [9] |
李淑艳, 曹菡, 刘妮玲. Voronoi图的并行生成算法研究[J]. 郑州轻工业学院学报（自然科学版）, 2010, 25（1）： 105-109.
Li Shuyan, Cao Han, Liu Niling. Generation Parallel Algorithm Research of Vorenoi Diagram[J]. Journal of Zhengzhou University of Light Industry （Natural Science）, 2010, 25（1）： 105-109.
|
| [10] |
Held M. VRONI： An Engineering Approach to the Reliable and Efficient Computation of Voronoi Diagrams of Points and Line Segments[J]. Computational Geometry, 2001, 18（2）： 95-123.
|
| [11] |
吴建华, 戴鹏, 胡烈云. 一种面向多尺度面状居民地匹配的Voronoi图自适应构建算法[J]. 武汉大学学报（信息科学版）, 2022, 47（2）： 304-312.
Wu Jianhua, Dai Peng, Hu Lieyun. An Adaptive Voronoi Diagrams Algorithm for Matching Multi-scale Areal Residential Areas[J]. Geomatics and Information Science of Wuhan University, 2022, 47（2）： 304-312.
|
| [12] |
王磊, 张娜, 殷楠, 等. 利用质心Voronoi图对地形自适应简化的算法[J]. 武汉大学学报（信息科学版）, 2023, 48（5）： 793-798.
Wang Lei, Zhang Na, Yin Nan, et al. An Adaptive Terrain Simplification Algorithm Based on Centroidal Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University, 2023, 48（5）： 793-798.
|
| [13] |
Okabe A, Boots B, Sugihara K, et al. Spatial Tessellations： Concepts and Applications of Voronoi Diagrams[M]. Chichester, England： Wiley & Sons, 1992.
|
| [14] |
王磊. 基于QTM的球面Voronoi图生成算法与应用[J]. 测绘学报, 2018, 47（11）： 1561.
Wang Lei. QTM-Based Spherical Voronoi Diagram Generating Algorithms and Its Application[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47（11）： 1561.
|
| [15] |
Chen J. A Raster-based Method for Computing Voronoi Diagrams of Spatial Objects Using Dynamic Distance Transformation[J]. International Journal of Geographical Information Science, 1999, 13（3）： 209-225.
|
| [16] |
Guo L C, Wang F, Huang Z J, et al. A Fast and Robust Seed Flooding Algorithm on GPU for Voronoi Diagram Generation[C]//International Conference on Electrical and Control Engineering, Yichang, China, 2011.
|
| [17] |
王新生, 刘纪远, 庄大方, 等. 一种新的构建Voronoi图的栅格方法[J]. 中国矿业大学学报, 2003, 32（3）： 293-296.
Wang Xinsheng, Liu Jiyuan, Zhuang Dafang, et al. New Raster-Based Method for Constructing Voronoi Diagrams[J]. Journal of China University of Mining & Technology, 2003, 32（3）： 293-296.
|
| [18] |
王磊, 赵学胜, 官亚勤, 等. QTM格网空间中的球面Voronoi图并行生成算法[J]. 武汉大学学报（信息科学版）, 2017, 42（5）： 691-696.
Wang Lei, Zhao Xuesheng, Guan Yaqin, et al. A Parallel Algorithm for Generating Spherical Voronoi Diagrams in QTM Space[J]. Geomatics and Information Science of Wuhan University, 2017, 42（5）： 691-696.
|
| [19] |
Shih F Y, Wu Y T. Fast Euclidean Distance Transformation in Two Scans Using a 3×3 Neighborhood[J]. Computer Vision and Image Understanding, 2004, 93（2）： 195-205.
|
| [20] |
李佳田, 陈军, 赵仁亮, 等. 基于线性四叉树结构的Voronoi图反向膨胀生成方法[J]. 测绘学报, 2008, 37（2）： 236-242.
Li Jiatian, Chen Jun, Zhao Renliang, et al. A Backward Inflation Generating Method for Voronoi Diagram Based on Linear Quadtree Structure[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37（2）： 236-242.
|
| [21] |
Liang E H, Lin S G. A Hierarchical Approach to Distance Calculation Using the Spread Function[J]. International Journal of Geographical Information Science, 1998, 12（6）： 515-535.
|
| [1] | DU Yan, NING Lize, XIE Mowen, BAI Yunfei, LI Heng, JIA Beining. A Prediction Model of Landslide Displacement in Reservoir Area Considering Time Lag Effect[J]. Geomatics and Information Science of Wuhan University, 2024, 49(8): 1347-1355. DOI: 10.13203/j.whugis20220133 |
| [2] | XIAO Ruya, HE Xiufeng. Deformation Monitoring of Reservoirs and Dams Using Time-Series InSAR[J]. Geomatics and Information Science of Wuhan University, 2019, 44(9): 1334-1341. DOI: 10.13203/j.whugis20170327 |
| [3] | ZHANG Yan, LV Pinji, LIU Jia. Impact of the Yangtze River Three Gorges Reservoir on Fault Activity[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1497-1500. DOI: 10.13203/j.whugis20140983 |
| [4] | HUANG Shengxiang, LUO Li. Stability Analysis and Results of the Landslide MonitoringDatum in the Three Gorges Reservoir Area[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3): 367-372. DOI: 10.13203/j.whugis20120019 |
| [5] | WU Xueling, REN Fu, NIU Ruiqing. Spatial Intelligent Prediction of Landslide Hazard Based on Multi-source Data in Three Gorges Reservoir Area[J]. Geomatics and Information Science of Wuhan University, 2013, 38(8): 963-968. |
| [6] | HU Teng, DU Ruilin, ZHANG Zhenhua, WU Yue. Simulation and Mechanism Analysis on Crustal Vertically Deformation in Three Gorges Reservoir Area Under the Condition of Reservoir Impoundment[J]. Geomatics and Information Science of Wuhan University, 2010, 35(1): 33-36. |
| [7] | WU Tao, YAN Huiwu, TANG Guigang. Prediction on Time Series Analysis of Water Quality in Yangtze Gorges Reservoir Area[J]. Geomatics and Information Science of Wuhan University, 2006, 31(6): 500-502. |
| [8] | DU Ruilin, QIAO Xuejun, YANG Shaomin, WANG Qi. Results of the Crustal Deformation by GPS Survey and Horizontal Strain Rate Fields in the Three Gorges Area[J]. Geomatics and Information Science of Wuhan University, 2004, 29(9): 768-771. |
| [9] | SHI Dong, CHEN Jun, ZHU Qing. Oil-Gas Reservoir Evaluation Based on GIS[J]. Geomatics and Information Science of Wuhan University, 2004, 29(7): 592-596. |
| [10] | JIANG Fuzhen. Role of Gravimetry in Monitoring the Crustal Deformation of Three Gorges Reservoir Area[J]. Geomatics and Information Science of Wuhan University, 2003, 28(6): 679-682. |
| 1. |
李惠民，彭紫薇，李相如. 气候变化下干旱对大别山区植被的影响研究. 治淮. 2024(12): 44-46 .
| |
| 2. |
谢萍，张双喜，金涛勇，韦瑜，蔡剑锋，许晨. 武汉市GRACE水储量变化与气象干旱关联趋势分析. 排灌机械工程学报. 2023(06): 624-629 .
| |
| 3. |
胡艳茹，梁丽娇，何立平，许文锋，刘正学，兰波. 三峡水库蓄水前后库区及周边区域降水变化及其影响因素. 地理研究. 2023(07): 1921-1940 .
| |
| 4. |
肖家豪，张双喜，韦瑜，蔡剑锋，洪敏. 基于GPS垂向位移测定云南地区陆地水储量及其对累积降雨的响应机制. 测绘通报. 2022(01): 61-65 .
| |
| 5. |
咬登魁，段功豪. 基于季节性SARIMA模型的武汉市长序列降雨量趋势分析与预测. 地下水. 2022(02): 166-168 .
| |
| 6. |
谢萍，张双喜，周吕，李庆隆，肖家豪，蔡剑锋. 武汉市中心城区地表形变与洪涝灾害防治新策略. 武汉大学学报(信息科学版). 2021(07): 1015-1024 .
|
Supported by: Beijing Renhe Information Technology Co., Ltd. 
DownLoad: