关于加权Voronoi图离散构造法的正确性研究
2017-01-11李璟莹王斌君
李璟莹, 王斌君
(中国人民公安大学信息技术与网络安全学院, 北京 100038)
关于加权Voronoi图离散构造法的正确性研究
李璟莹, 王斌君
(中国人民公安大学信息技术与网络安全学院, 北京 100038)
针对加权Voronoi图离散构造法的正确性问题,系统研究了Voronoi图的原始定义和性质,并对照加权Voronoi图的逐点扫描算法,发现离散构造法是一个粗略的算法,在生成具有多个离散区域的加权Voronoi图时,该算法不正确;通过实验也证实了离散构造法的错误。通过分析离散构造法的算法,发现其扩展终止条件有错误,提出了相应的改进算法,保证了算法结果的正确性。
加权Voronoi图; 分区加权Voronoi图; 离散构造法; 逐点扫描法
0 引言
Voronoi图解决了平面上离散生成元的空间划分问题,是描述空间邻近关系的一种基础数据结构,适用于解决几何重构、覆盖模拟、路径规划、空间分析等问题,在气象学、地理学、晶体学、信息科学、机器人路径规划等领域应用广泛[1]。
最初的Voronoi图是基于最短距离的空间剖分[2],考虑的因素比较理想化,但在实际应用中生成元往往具有不同的“影响力”,于是又扩展出加权Voronoi图[2]、分区加权Voronoi图[3]、线段加权Voronoi图[4]等各种加权Voronoi图。
对于生成元被加权的Voronoi图,生成算法包括矢量算法和栅格算法。矢量算法结果精确但计算复杂,栅格算法相对简单但精度受栅格大小影响。在栅格算法中,常用的有离散构造法和逐点扫描法。1980年, B.N.Boots提出的模拟生长模型(Growth Simulation Model)奠定了离散构造法的基本思路,即通过模拟母点的动态生长过程来生成Voronoi图[2]。……