乘权Voronoi图的动态构造法

刘 欣，刘颖华，王 辉

(承德石油高等专科学校社科与数理部，河北 承德 067000)

1 背景简介

普通Voronoi图，是计算几何的一个重要分支，在计算几何理论和应用中起着重要作用。而完全按照普通Voronoi图的算法划分区域，有很大的局限性。为扩展Voronoi图使其应用在更广泛的领域，在Voronoi图中引入了权的概念。在研究全国城镇体系、讨论地理输送系统以及交通网络中被广泛地应用。在确定城市中心功能区中必不可少地需要引用权值，因此越来越多的学者开始研究乘权Voronoi图。传统的算法构造乘权Voronoi图时，运算效率与母点个数有密切关系[1-4］。而动态构造算法几乎与母点个数无关，且母点个数越多，其相对效率越高。进行构造时，对以不同颜色区分Voronoi区域的乘权Voronoi图进行横向扫描，在扫描过程中，如果某像素与其后续像素颜色不同，就将该像素置为指定的颜色(例如黑色);否则置为另一种颜色(例如白色);再进行纵向扫描，处理同上。两次扫描完成后，其结果便为由指定颜色画出的乘权Voronoi图。

2 定义

2.1 经典 Voronoi图

2.2 乘权 Voronoi图

乘权Voronoi图的乘权距离定义如下:

我们称这个距离为乘权Voronoi距离或MW距离。则平分线为

2.3 动态的乘权Voronoi图的构造

现在我们以9个生成元分为例，用离散算法构造乘权Voronoi图。组图3显示了其动态生成过程。图3所示括号中的数字代表该生成元的权重。首先，我们分配不同的颜色代表不同的生成元点，然后以画圆圈的点为中心，以生成元乘权距离为半径，最后得到乘权网络Voronoi图。我们把生成元的黑色和分配的其他像素的白色，然后构造出乘权Voronoi图。

3 结论

乘权Voronoi图的动态构造算法能克服多种缺点，因为我们只需要考虑生成元变化。所以结果表明，它比传统的算法更简单，高效，并且具有较高的理论意义和广泛的应用价值，能较好地解决加权Voronoi图在地理信息处理、模式识别、生态研究、城市规划、最优化配置等许多领域的问题[5-7］。

[1]张有会，浅也哲夫，小保方幸次.关于一般图形Voronoi图的近似构造法的研究[J］.数值计算与计算机应用，2002，9(3):216－225.

[2]杨秀芬，李涛.公共自行车服务系统推广模型[J］.承德石油高等专科学校学报，2014(6):61－65.

[3]吴壮志，杨钦，怀进鹏.Power图的性质及构造算法研究[J］.计算机辅助设计与图形学学报，2001，13(12):1057－1062.

[4]周培德，卢开澄.计算几何算法分析与设计[M］.北京:清华大学出版社，2000.

[5]王新生，郭庆胜.Voronoi图的扩展、生成及其应用于界定城市空间影响范围[J］.华中师范大学学报(自然科学版)，2002，36(1):107 －111.

[6]周德培.计算几何-算法分析与设计[M］.北京:清华大学出版社，2000.

[7]杨洋，沈法华，董晶晶，等.多普勒测风激光雷达校准仪中激光入射和接收角度设计[J］.中国仪器仪表，2007(12):29－31.