障碍Voronoi图性质及其应用研究

论文摘要

自90年代以来,Voronoi图应用在各个领域,Voronoi图不仅在计算几何学的方面上扮演重要的角色,而且在人们现实生活中的很多地方也是发挥着重要的作用,可以说它是一种非常有用、重要的图形。随着计算机技术的普及和发展,Voronoi图的应用范围也在不断扩大,利用Voronoi图的理论可有效地解决最近点的查找、求最大空圆、求最小树、求n个平面点的凸包等问题。通常意义下的Voronoi图是以欧氏距离为度量,对平面区域进行的一种分割,这是一种不考虑障碍物的理想模式。为扩大Voronoi图的应用领域,本文对Voronoi图进行了扩展,主要研究障碍Voronoi图的生成算法及应用。首先从Voronoi图的定义出发,将Voronoi图的性质及生成算进行全面的归纳和总结,进而提出了基于Voronoi图的分块划分空间的算法,将二维或多维空间划分为具有周期性的分块区域空间,具有广泛的应用价值。通过对Voronoi图的全面研究,将Voronoi图推广到障碍环境中,给出了障碍Voronoi图的概念,定义了城市中的障碍Voronoi图,包括城市距离和障碍城市距离。并对障碍Voronoi图的各种生成算法进行了详细的研究,比较各种算法的优缺点,得出较好的生成障碍Voronoi图的算法。最后将障碍Voronoi图与可视图有效结合,应用到障碍环境中的最短路径规划,给出可视Voronoi图的算法。可用于任意间隙值c、任意起点和终点间的有效路径规划,时间复杂度为O ( n2 logn),减少了查询阶段的对几何图形分析和执行预处理阶段的计算。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 Voronoi 图的背景与意义
• 1.2 国内外研究现状分析
• 1.3 课题来源
• 1.4 本文主要研究内容
• 第2章 Voronoi 图基础知识
• 2.1 Voronoi 图的相关概念
• 2.2 Voronoi 图的生成算法
• 2.2.1 Voronoi 图的矢量生成方法
• 2.2.2 Voronoi 图栅格生成方法
• 2.3 Voronoi 图的应用
• 2.4 本章小结
• 第3章 障碍Voronoi 图
• 3.1 障碍Voronoi 图的定义
• 3.2 障碍城市Voronoi 图的定义
• 3.3 障碍Voronoi 图的常用生成算法
• 3.4 本章小结
• 第4章 障碍Voronoi 图的最短路径规划
• 4.1 障碍路径规划基本概念
• 4.1.1 相关基本定义
• 4.1.2 VV 图
• 4.2 VV 图的构造及合成
• 4.2.1 VV 构造
• 4.2.2 VV 图合成
• 4.2.3 具体算法
• 4.3 复杂度分析
• 4.4 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢