Voronoi图的栅格生成方法研究与分析

Voronoi图的栅格生成方法研究与分析

Voronoi图是一种空间分割算法。其是对空间中的n个离散点而言的，它将平

面分割为n个区域，每个区域包括一个点，此区域是到该点距离最近的点的集合。由于Voronoi图具有最邻近性，邻接性等众多性质和完善的理论体系，其被广泛的应用在地理学、气象学、结晶学、航天、机器人等领域。

Voronoi图的生成主要有矢量方法和栅格方法。矢量法中，典型的方法有增量法、分治法和间接法。分治法是一种递归方法，算法思路简单，但是很难在应用过程中实现动态更新。间接法则是根据其对偶图Delaunay三角网来构造Voronoi图，因此其性能的高低由所采用的Delaunay三角网的构造算法所决定。增量法通过不断向已生成的Voronoi图中增加点来动态构建Voronoi图。相对于前两种方法，增量法构造简单并且容易实现动态化，所以被广泛应用。矢量方法的优势是生成Voronoi图精度高，但是存在存储复杂，生长元只能是点和线，以及难以向三维及高维空间扩展等问题。因此本文重点研究了Voronoi图的栅格生成方法，首先比较了常见的栅格方法生成Voronoi图的优缺点，然后结合CUDA的出现，提出一种基于GPU的 Voronoi图并行栅格生成算法。

1 栅格法简介栅格方法生成Voronoi 图主要是将二值图像转化为栅格图像，然后确定各个空白栅格归属。主要方法有两类，一类以空白栅格为中心，计算每个空白栅格到生长目标的距离，以确定其归属，常见的方法有代数距离变换法，逐个空白栅格确定法等;另一类以生长目标为中心，不断扩张生长目标的距离半径，填充其中的空白栅格，直到将整个图像填充完成，主要有圆扩张法，数学形态学距离变换法等。代数距离变换法对距离图像进行上行扫描（从上到下，从左到右）和下行扫描（从下向上，从右到左）两次扫描，计算出每个空白栅格最邻近的生长目标，以此生长目标作为其归属。此方法中栅格距离的定义直接影响了空白栅格的归属和Voronoi图的生成精度，通常使用的栅格距离定义有街区距离、八角形距离、棋盘距离等。距离变换的栅格生成方法精度低、耗时长，所需要花费的时间和栅格的数量成正比，当栅格为n×n大小时，其时间复杂度为O（n×n）。圆检测法以生长目标为圆心，以一定的步长为初始半径，所有生长目标同时对其构成的圆内的空白