王斌君，王秋实，李璟莹，沙俊松

(1.中国人民公安大学 信息技术与网络安全学院,北京 100240;2.公安部第一研究所 物联网部,北京 100048)

Voronoi图[1]是计算几何领域中的一个重要研究方向,Voronoi图的生成算法是该领域的关键技术。Voronoi图被广泛应用于气象学、地理学、晶体学、信息科学、机器人路径规划、警力部署、商圈划分、室内布局、林业等应用领域。目前,Voronoi图的理论热点集中在高阶[2]和高维空间[3]的相关问题研究,但其核心思想和算法仍然是以传统的分区加权Voronoi图为基础。因此,研究和改善基本的分区加权Voronoi图生成算法的性能有一定的理论和实用价值。

截至目前为止,已有的基本分区加权Voronoi图生成算法主要包括矢量法和栅格法两大类。相对于Voronoi图矢量法[4-5]的精度高但数据结构和计算复杂,只适用于简单Voronoi图而言,栅格法[5-8]虽然精度较低,但能适用于任何Voronoi图(生成元可为点、线或面,且各生成元可分区、加权),其扩展性强、速度快,具有很强的泛化能力和适用性。

Voronoi图的栅格法包括逐点扫描法[6]和模拟生长法,模拟生长法目前包括距离表[7]和离散构造[8]两种算法。本文对分区加权Voronoi图模拟生长法进行系统分析和研究,发现文献[7-8] 存在诸多的缺陷。为此,我们设计并实现了一种改进的算法,克服了原算法的不足,提高了原算法的效率。

1 现有算法研究

模拟生长法的基本思想是[4]:对于平面上n个生成元,每个生成元的每个扇区都被赋予不同颜色和权值,分别以每个生成元为圆心,同步在各扇区以指定速率(与权重成正比)向外扩展画弧,直到空间被颜色填满,不同颜色区域的边界即为分区加权Voronoi图的近似边界。在逐步扩展画弧过程中,画每一个点前需检查该点是否已被着色,如为白色,则用相应扇区的颜色填涂;否则不作处理。该算法思路清晰,实现简单。

但文献[8] 提出的离散构造算法存在以下问题:

问题1边界粗糙问题。边界线的形成是通过各生成元同步扩展过程的“碰撞”来粗糙逼近的,最终生成的边缘与扩展过程中生成元的先后次序有关。图1(a)和图1(b)分别是模拟增长法对相同生成元的不同次序结果图,边界上有一定的差异，图1(c)是逐点扫描法的对比结果图。其实,模拟生长法天生存在边界上的缺陷问题,对其构造的现有算法[7-8]都会存在边界不精确问题。

问题2角度增量问题。为了对所有半径的扩展弧进行逐点着色扫描,设置了一个足够小的固定角增量,以便正确处理大半径的情况,即对小半径弧和大半径弧扫描的角度增量一样,这就导致原算法在前期(扩展半径小的时候)着色速度明显很慢。改进的方法是将角增量设定为与半径成反比的动态值。理想情况下,角增量应该是扩展弧上相邻两个点对应的角度。绘图区域两点之间的最小距离为1,对应的劣弧会略大一点点。按照半径、劣弧和角度的计算关系,将角增量设置为1/r。它既能满足算法的正确性,而且在扩展半径小的时候,算法的运算速度会明显加快,提高了原算法的效率。

图1 边界粗糙问题Fig.1 The problem of boundary roughness

问题3斑马纹问题。算法没有考虑大权值的情况，同步扩展时大权值的实际扩展半径(步)的增量如果大于1,就会因为跨步太大导致未着色区域,如图2(a)所示。图2(b)是一个示例的结果,其中,左下角和右上角存在两个权值比较大的生成元,结果出现了错误。

图2 斑马纹问题Fig.2 The problem of zebra stripe

与该问题相关的一个问题是,当生成元的权值太小时,原算法需要重复计算扩展弧,从而影响了算法的效率。

问题4不连续区域问题。该算法存在的更重要问题是没有考虑不连续Voronoi图的情况(文献[4] 的性质Ⅳ)。对于某个生成元，当其周围的边界确定后,就不再扩展,这只是在没有不连续区域Voronoi图的情况下是正确的。我们曾撰文讨论了该问题[9],并简单地修正了算法的终止条件(每个生成元都需要扩展并判断到所有绘图区域),以保证算法的正确性。但文献[9] 尚未对算法终止条件进行详细分析。

下面对模拟生长法的终止条件进行讨论。首先给出定理1。

定理1对模拟生长法,在算法依次扩展过程中,如果绘图区域的某个点第一次被某个生成元覆盖,即确定了某个颜色,则该点在算法以后的扩展过程中不会改变颜色。

证明按照模拟生长法的思想,某个点被标记为某个颜色后,其算法的后续步骤不会再改变其颜色,该定理的结论显然是正确的。

推论1对模拟生长法,当最大权值生成元覆盖了绘图区的所有点时,算法可结束。

证明先证明一般的情况。对任何一个生成元,如果其扩展区域能覆盖了所有绘图区域的点,则绘图区域任何一个点都在本次或之前的算法扩展过程中确定了颜色。根据定理1,算法可结束。

所以,该结论对最大生成元也成立。

推论2对模拟生长算法,当绘图区域所有点被着色后,算法可结束。

证明根据定理1可直接得到本推论。

推论1是从生成元的角度设置算法的终止条件,而推论2则是从绘图区域的角度设置终止条件。按照推论1,当出现图3的情况(权值最大生成元靠近某一个角,而另一个相对权值比较大的生成元在另一个角)时,尽管绘图区域已经完全被覆盖(如图3所示,在算法扩展过程中的某个时刻,点虚线和细的杠虚线是右上角生成元的覆盖情况;粗的杠虚线是左下角生成元的覆盖情况),绘图区域各点的颜色都确定了,但算法仍需继续,效率比较低。按照推论2,可用一个计数器,当绘图区域中被着色点的总数达到了绘图区域所有点的总数即可结束算法,算法效率会更高。

图3 以最大生成元覆盖作为终结条件的情况Fig.3 The case of termination with maximum generator

需要注意的是,文献[7] 也存在问题1和问题4。问题1是模拟生长法本身存在的共性问题,除非采用并行算法,否则任何模拟生长法的常规算法都存在问题1;而问题4是距离表算法[7]和离散构造算法[8]本身设计不合理造成的。

2 改进的算法设计

基于上文对现有离散构造算法的分析,对其存在的问题,本文设计的改进算法如下。

算法:改进的离散构造算法。

S1:初始化

绘图区域置白色;着色点计数器count为0;生长步数计数器num为1;

S2:while (count<绘图区域栅格总数) {

for (i=1;i≤生成元数;i++){

S2.1://第1个扇区

for(r=(num-1)*Wi1;r

Δθ= 1/r;

for(θ=θi1;θ<θi2;θ=θ+Δθ){

计算(curX, curY)的颜色;

if ((curX, curY)的颜色为白色){

置(curX, curY)为Ci1;

count++;}}

}

S2.2://第2个扇区

……}

}

S3:提取边界

S4:结束

其中,Wi1表示第i个生成元中第1扇区的权重,θi1和θi2分别表示第i个生成元中第1扇区的起始角度和结束角度,Ci1表示第i个生成元中第1个扇区的颜色。

本算法通过设立动态的角度增量1/r,解决了问题2;通过增加了一个步长循环,解决了问题3;特别是通过count计数器建立终止条件,解决了问题4。

3 实验的结果及分析

图4分别是采用原离散构造算法[8]、文献[9] 的改进算法和本算法的实验结果。

图4 3种模拟生长算法的对比图Fig.4 Constrast diagram of three simulated growth methods

图4(a)是文献[8] 离散构造算法的结果,其中左侧的不连续区域不能正确生成,结果中也存在斑马线。图4(b)是文献[9] 改进原始算法终止条件后得到的能正确处理具有不连续区域Voronoi图的

结果,但仍然存在斑马线。图4(c)是本算法的结果,它能正确处理不连续区域问题和斑马线问题。

表1是在相同软硬件环境下,不同参数的对比数据。其中,所有生成元、生成元的扇区角度(本实验均采用一个生成元有3个扇区)以及生成元各扇区的权重都是随机生成的。

图5是表1数据的趋势对比图。图5(a)，图5(b)和图5(c)分别是对应表1中300*300，500*500和800*800屏幕绘图区的3种算法趋势图。从表1和图5可以看出,文献[9] 虽然纠正了原算法[8]不能正确处理具有不连续区域Voronoi图的错误,但需要将所有生成元扩展到绘图区域的边界,所以计算速度慢。本算法能正确处理不连续区域Voronoi图和斑马线问题,且效率明显快,甚至优于文献[8] 。虽然本算法也与生成元多少、屏幕大小成正比,但其增长速度比文献[8] 和文献[9] 明显缓慢。

在表1中,500*500屏幕区域，50个生成元的情况,本算法生成Voronoi图需要10.9s,而100个生成元的只需要6.3s,这与生成元的分布有关,但并不影响算法的整体效果。

表1 3种模拟生长算法的数据对比Tab.1 The constrast of three simulated growth methods with different data

4 结 语

目前,Voronoi图的理论热点集中在高阶[2, 10-11]和高维空间[3]的相关问题研究,更多的研究成果是Voronoi图在区域划分、覆盖和选址[12-15]等方面的应用研究,但其核心思想和算法仍然是以传统的分区加权Voronoi图为基础。本文研究了Voronoi图模拟生长法的相关问题,重点分析了文献[8] 提出的算法,对其不完善和效率问题,提出了分区加权Voronoi图离散构造法的改进算法。理论分析和实验结果表明,改进的算法能正确处理不连续Voronoi图、斑马纹等问题,且改进算法的效率优于原算法。

图5 3种模拟增长算法的趋势对比Fig.5 Trend contrast of three simmulated growth methods

但是,由于Voronoi图模拟生长法的本质特征,模拟生长法除非采用并行算法,否则生成元覆盖区域边界都会出现不精确的问题，生成元分布不均时,算法效率就会下降，下一步将结合逐点扫描法进行研究。