横-纵扫描的Voronoi图栅格生成算法

Voronoi图是计算几何学中一个重要数据结构,在诸多领域具有广泛的应用。栅格扫描算法符合计算机离散特征,优化了欧氏距离算法,是最优的栅格Voronoi图生成算法之一。但是,由于栅格单元距离与欧氏距离的差异,在扫描过程中部分单元的归属不可避免地产生一定的误差,使栅格Voronoi图的应用受到一定限制。本文针对传统扫描算法存在的误差缺陷,提出了一种基于横-纵扫描的栅格Voronoi图改进生成算法。首先,深入分析了传统扫描算法产生误差缺陷的原因和区域分布特征;然后,以3×3邻域为模板,在一个正常周期的水平(横向)扫描后,增加一个周期竖直(纵向)扫描,即通过横-纵两个周期扫描实现Voronoi图的准确生成;最后,应用不同的栅格数据进行了试验对比,结果表明:改进后的算法既具备扫描算法效率上的优势,同时解决了原算法扫描的误差缺陷,在高效生成的同时把误差限制在一个格网以内。

A raster Voronoi diagram generation algorithm based on horizontal-longitudinal scanning

The Voronoi diagram is an important data structure in computational geometry and has a wide range of applications in many fields. The scan algorithm of raster is an optimization of the Euclidean distance algorithm, which is in line with the discrete features of computers. It is one of the optimal algorithms for the generation of raster Voronoi diagram. However, due to the difference between the grid distance and the Euclidean distance, the ownership of some grids in the scanning process inevitably has some errors, so that the application of the raster Voronoi diagram is limited. In this paper, according to the characteristics of error existing in traditional scanning algorithms, an improved algorithm for the generation of raster Voronoi diagram based on horizontal-longitudinal scanning is proposed. First of all, the causes and the regional distribution characteristics of defects of the traditional scanning algorithm are analyzed in depth. Then, using the 3×3 neighborhood as a template, a vertical scan is added after a horizontal scan. That is to say, the Voronoi diagram can be generated accurately by horizontal and vertical scanning. Finally, different raster data are used to carry out experimental comparison. The results show that the improved algorithm not only has the advantage of efficiency of scanning algorithm, but also solves the error of the original algorithm. It keeps the efficiency while limiting the error to a grid.