APP下载

关于加权Voronoi图离散构造法的正确性研究

2017-01-11李璟莹王斌君

中国人民公安大学学报(自然科学版) 2016年3期
关键词:定义区域

李璟莹, 王斌君

(中国人民公安大学信息技术与网络安全学院, 北京 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]。……

登录APP查看全文

猜你喜欢

定义区域
永久基本农田集中区域“禁废”
分割区域
永远不要用“起点”定义自己
定义“风格”
关于四色猜想
分区域
成功的定义
基于严重区域的多PCC点暂降频次估计
修辞学的重大定义
山的定义