结合边缘归属与双向扫描的栅格Voronoi图生成算法
A Raster Voronoi Diagram Generating Algorithm Using Edge Attribution and Bilateral Scanning
王磊 1宋志学 1殷楠 1程钢1
作者信息
- 1. 河南理工大学测绘与国土信息工程学院,河南 焦作,454000
- 折叠
摘要
Voronoi图是计算几何领域中的一个重要研究方向,其生成算法是该领域的关键技术.确定归属算法符合计算机的离散特征,是精度最优的栅格Voronoi图生成算法之一,但在海量数据处理时效率不高.针对这一问题,提出一种基于结合边缘归属与双向扫描的栅格Voronoi生成算法.在深入探究确定归属算法精度优异和效率较低原因的基础上,首先将数据边界栅格通过确定归属计算赋予Voronoi区域归属,建立3×3的邻域模板,进行正向扫描;然后在深入剖析正向扫描结果的基础上,通过逆向纠错确保所有栅格归属的正确性;最后利用不同规模的数据进行了实验对比.结果表明,所提算法具有与确定归属算法相同的精度,但省去80％以上的计算量,效率提高4倍以上,且数据规模越大,算法优势越明显.
Abstract
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 determinis-tic 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 algo-rithm,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 3X3 neighboring domain template is established,and the forward scanning is performed by using the do-main template.Then,the correctness of Voronoi attribution of all the rasters is ensured by reverse error cor-rection 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.Com-pared 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.
关键词
Voronoi图/双向扫描/边缘归属Key words
Voronoi diagram/bilateral scanning/edge attribution引用本文复制引用
出版年
2024
NETL
NSTL
万方数据