基于Voronoi理论判别刚体运动轨迹的方法

张铁强

辽宁对外经贸学院，辽宁大连 116052

基于Voronoi理论判别刚体运动轨迹的方法

张铁强

辽宁对外经贸学院，辽宁大连 116052

基于平面点集的 Voronoi 图提出一种定性判别刚体运动轨迹的方法。通过物体点与背景点组成的Voronoi 图的点集与边集的变化来定性判别物体运动的轨迹。实验结果表明，该算法能准确地描述物体运动轨迹，结果精确。

空间推理；Voronoi图；Voronoi边；运动轨迹

空间推理（spatial reasoning）是人工智能学科处理常识性空间知识的一种方法[1]。刚体随时间运动的问题属于空间推理[2]的范畴，已经应用在很多领域，例如：运动规划、几何建模、物理系统以及虚拟现实系统的计算机模拟、机器人、模式识别[3]等方面。在这些应用中，选择一个有效的数据结构是解决这些大型系统的关键。Voronoi 图则常用于这种数据结构，它是计算几何学科中的一个重要结构，能准确描述空间方向关系[4-5]，已广泛应用于上述各领域[6]。

本文正是利用Voronoi图来描述背景点与刚体点的拓扑结构，并根据这一拓扑结构的变化来定性描述物体运动轨迹的。在余下的篇幅中，将详细地阐述该方法的特点：刚体点与背景点构成voronoi图，刚体点在平面上运动，将会使voronoi图发生改变，当刚体点与某背景点消失voronoi边时，刚体点远离该背景点，反之，当刚体点与某背景点生成voronoi边时，刚体点靠近该背景点。当voronoi图的状态未发生改变时，刚体点的运动状态也视为未发生变化。

1 Voronoi图理论基础

1.1 Voronoi图的定义

设P={p1,p2,…,pn}⊂R2，R2是二维欧氏空间上的点集，d(·，·)为欧氏距离。称为 Voronoi区域。其中，由点集P生成的Voronoi图可定义为：

Voronoi图区域的边被称为Voronoi图的边，Voronoi图区域的顶点被称为Voronoi图的顶点。

1.2 Voronoi图的生成算法

Voronoi图的平面点集构造算法有3类：平面扫描法、分治法和增量算法。其中的增量算法不但可以适用于静态点集，而且可以适用于动态点集，本文中选取增量算法构造平面点集(包括背景点与刚体点)的Voronoi图。

1.2.1 翼边数据结构

首先介绍Voronoi图的存储结构——翼边数据结构。

1）将Voronoi图扩充为几何图(平面图)。用足够大的闭合曲线围绕Voronoi图的顶点，无限边相交在此曲线，将此曲线分割成若干个曲线段，称为Voronoi边，此图称为扩充几何图。令G=(V，E)，其中，，。

2）首先对每一条边任选并且固定方向，然后，命名顶点序号1，2，…，nv与边的序号1，2，…，ne，并称为生成子pi的Voronoi多边形为i(i=1，2，…，n，∞)。

利用已有的多边形数组描述Voronoi图的翼边数据结构。

1.2.2 增量算法

在增量算法的设计阶段，首先做出3个点的Voronoi图，其余各点都位于单位正方形中，附加3点的坐标为：

输入：点集P，l，Vl-1

输出：翼边数据结构（Vl）

过程：

1）找出pl的Voronoi区域；

2）假设pl与Voronoi区域所在生成子pi的垂直平分线与V(pi)的边界交于ω1和ω2两个点，而且pl在有向线段ω1ω2区域的左侧，可生成V(pl)的一条边，从这条边进入相邻的Voronoi多边形。用同样方法，找到pl与邻接的Voronoi区域多边形的生成子的垂直平分线的所有线段序列，直到起点ω1；

3）删除图Vl-1中在图V(pl)中的数据构造，同时修改对应的翼边数据结构。

1.3 Delauny三角剖分与凸包、最大空圆

Delauny三角剖分是Voronoi图相对于点集的对偶图，其中任意三角形的外接圆都不包含点集中的所有点。所以，在构造点集对应的Voronoi图后，作它的对偶图，即对每条Voronoi边分别做通过点集中任意两点的垂线，便得到Delauny三角剖分。

平面点集S的凸包是包含S中所有点的最小凸集，亦即所有Delauny三角形的并集。

平面点集S的最大空圆，给定平面上n个点的点集S，寻找一个不包含S中点的最大圆，即为S的最大空圆。

2 定性判定刚体运动轨迹

判定过程：

[1.输入背景点] 在平面上随意确定一个点集，作为背景点集。

[2.输入刚体点] 在平面上确定一个点集作为刚体点。由于是刚体，可用平均值法将刚体点集归结为一点进行处理。

[3.生成voronoi图] 利用增量算法生成背景点集与刚体点构成的平面点集的voronoi 图。

[4.记录刚体点初始状态] 记录刚体点与背景点集的voronoi边状态。

[5.移动刚体点] 在平面上移动刚体点。

[6.记录voronoi边的变化]

刚体点与背景点生成的voronoi图中，voronoi边的变化情况可定性反映出刚体点与背景点之间的位置关系和方向关系：

1）设刚体点4与背景点1、2、3的初始空间关系如图1所示。

图1 4个点的原始状态

2）点与某背景点之间有voronoi边生成，则可定性表示为刚体点靠近该背景点。（如图2）

图2 刚体点4与背景点2生成voronoi边

图3 刚体点4与背景点1消失voronoi边

3 实验与结论

3.1 实验结果

1）输入背景点1-8，输入物体点9。（图4）

2）沿图示轨迹拖动物体点。对物体点运动做定性分析。（图5）

当刚体点9沿着图5中的轨迹运动时，它与背景点集的voronoi边的变化序列如下。

点9与背景点5之间生成边，点9与背景点2之间消失边，点9与背景点8之间生成边，点9与背景点3之间消失边，点9与背景点4之间生成边，点9与背景点6之间消失边，点9与背景点1之间生成边，点9与背景点7之间消失边，点9与背景点8之间消失边。

因此，点9的运动轨迹可以用自然语言序列定性表示：

点9靠近背景点5，点9远离背景点2，点9靠近背景点8，点9远离背景点3，点9靠近背景点4，点9远离背景点6，点9靠近背景点1，点9远离背景点7，点9远离背景点8。

图4

3.2 结论

实验证明，本文提出的方法可以基本准确的定性描述刚体点的运动轨迹。

图5

[1]廖士中，石纯一.定性空间推理的研究与发展[J].计算机科学，1998，25（4）：11-13.

[2]石纯一，廖士中.定性推理方法[M].北京：清华大学出版社，2002.

[3]边肇祺，等.模式识别[M].北京：清华大学出版社，2000.

[4]闫浩文，郭仁忠.用Voronoi图描述空间方向关系的理论依据[J].武汉大学学报（自然科学版），2002.

[5]闫浩文，郭仁忠.基于Voronoi图的空间方向关系形式化描述模型[J].武汉大学学报（自然科学版），2003.

[6]周培德.计算几何—算法分析与设计[M].北京：清华大学出版社，1999.

[7]王哓东，廖士中.一个基于桶技术的平面点集Voronoi图增量算法[J].辽宁师范大学学报（自然科学版），2002.

图3 管理员子系统

3 结论

总之，该统计学立体化教学平台的设计充分考虑了教学过程中的学生需求和教师需求。本文主要研究了统计学立体化教学平台的设计，为统计学传统教学和互联网融合指引了方向，该平台的设计主要为提高统计学的教学质量提供良好的辅助功能。有了该平台能使统计学教学质量更上一层楼[5]。

参考文献

[1]刘贵富.信息环境下高校立体化教学资源建设研究[J].黑龙江高教研究，2009，8：138-140.

[2]刘立群.立体化教学资源建设及其模型研究[J].沈阳师范大学学报(自然科学版).2010，4：571-573.

[3]余朝文.基于网络学习型社会的立体化教学资源建设研究[J].中国电化教育，2011，6：70-91.

[4]刘媚.概率论与数理统计课程立体化教学改革初探[J].宁夏师范学院学报，2013，6：85-87.

[5]翟成景.网络立体化教学资源交互平台的设计与实现[D].山东：山东大学，2013：2-5.

TP3

A

1674-6708（2015）149-0148-03

张铁强，副教授，研究方向：计算机应用、教学管理