基于Voronoi图的移动机器人SLAM算法(3)

2 Voronoi图定义

Voronoi图[7]是关于空间邻近关系的一种基础数据结构(如图2所示)，Voronoi图把平面分成n个区域，每个区域包括1个顶点，该点所在区域是到该点欧几里得距离最近的点的集合。对平面点集P为元素的Voronoi图来说，平面被划分为凸多边形区域，P中每个元素pi对应一个区域V(pi)，使得V(pi)内的任何点距离pi都比距离其他元素近，V(pi)定义如下：

V(pi) {x|d(x,pi) d(x,pj), i j, j 1,2, ,n} (2)

图2 Voronoi图

Fig.2 Example of Voronoi diagram

3 基于Voronoi图最近邻点算法

3.1 定义和定理[8 9]

定义1 (2-D栅格地图) 令R1和R2是栅格地图grid中的2点，定义顺序关系 y， y如下：

R1,R2 grid,R1yR2 yR1 yR2 (yR1 yR2 xR1 xR2) R1,R2 grid,R1 yR2

yR1 yR2 (yR1 yR2 xR1 xR2) (3)

定理1 如图3所示，有背景点u，v和w(ux<vx<wx),uv为点u与点v垂直平分线穿过直线y=r的点，vw为点v与点w垂直平分线穿过直线y=r的点，则观察图形可知，当uvx≥vwx时，直线y=r与点v所属的Voronoi多边形区域无交集，即对于所有纵坐标为r的点的最近邻点可排除v。

图3 当uvx≥vwx时，点v的Voronoi区域与

直线y=r无交集

Fig.3 Voronoi region of v does not intercept line r