A Raster Voronoi Diagram Generating Algorithm Using Edge Attribution and Bilateral Scanning
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.
NETL
NSTL
万方数据
