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 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.