关于障碍Voronoi图的研究

论文摘要

Voronoi图是一个关于空间划分的基本数据结构。作为计算几何的一个重要分支,它的应用越来越为人们所关注。近年来,它被应用在与几何信息相关的许多领域。随着计算机技术的普及和发展,Voronoi图的应用范围也在不断扩大。传统Voronoi图是在没有考虑障碍物的情况下对空间划分的一种理想模型,而在实际生活中往往存在很多自然或人为的障碍,使得两个目标之间不能直接通行,因此传统Voronoi图将不再实用。为了进一步扩大Voronoi图的应用范围,必须对存在障碍物的Voronoi图进行研究,从而确立了论文的研究内容。本文首先从一般Voronoi图的原始定义出发,系统地总结了传统Voronoi图的性质、经典生成算法。在对Voronoi图的生成算法进行进一步研究的基础上,提出了构造Voronoi图的增点算法。这种算法是对构造Voronoi图增量算法的改进和完善,同时也给出了增点算法的流程图。这种改进的算法逻辑程序简单,避免了构造Voronoi图过程中对新增点位于一些特殊位置情况下的处理。基于离散点集的Voronoi图和三角剖分之间的对偶关系,提出了基于Voronoi图下的Delaunay三角剖分,研究了构建Delaunay三角剖分的经典算法。改进了构建Delaunay三角剖分的逐点插入法,这种算法通过优化核心算法达到了提高整个算法效率的目的。而这个算法就是点在多边形内外测试的新算法,该算法采用极限思想,引入一条射线来分析问题,大大减低了整个问题的复杂性,重要的是在实际设计计算机程序时这条射线不需要存储。然后研究了障碍物为线段的Voronoi图,给出了线段障碍Voronoi图一些很好的性质,论述了线段障碍Voronoi图的生成算法,其中有些生成算法是可以直接推广到障碍物为任意几何形状的障碍Voronoi图的生成算法中。同时提出了一种半平面求交算法,是目前唯一的直接生成算法。最后给出了障碍Voronoi图的应用实例。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 障碍VORONOI 图的背景与意义
• 1.2 国内外研究现状分析
• 1.3 VORONOI 图的应用
• 1.4 本文研究框架结构和研究的主要内容
• 第2章 VORONOI 图
• 2.1 VORONOI 模型的提出
• 2.2 VORONOI 图的定义及性质
• 2.2.1 Voronoi 图的定义
• 2.2.2 Voronoi 图的性质
• 2.3 构造VORONOI 图的算法
• 2.3.1 半平面求交法
• 2.3.2 增量构造算法
• 2.3.3 分治算法
• 2.3.4 平面扫描算法
• 2.3.5 栅格算法
• 2.4 增点算法
• 2.5 离散生成算法
• 2.6 本章小结
• 第3章 基于VORONOI 图的DELAUNAY 三角剖分
• 3.1 DELAUNAY 三角剖分与VORONOI 图的关系
• 3.2 DELAUNAY 三角剖分的性质
• 3.3 构造DELAUNAY 三角剖分的算法
• 3.4 DELAUNAY 三角剖分逐点插入算法
• 3.5 点在多边形内测试的新算法
• 3.5.1 算法思路
• 3.5.2 算法描述
• 3.5.3 算法分析
• 3.6 本章小结
• 第4章 有障碍物的VORONOI 图
• 4.1 一般意义下的VORONOI 图的应用局限性
• 4.2 I 型线段障碍VORONOI 图
• 4.2.1 I 型线段障碍Voronoi 图的定义
• 4.2.2 I 型线段障碍Voronoi 图的性质
• 4.2.3 I 型线段障碍Voronoi 图的生成方法
• 4.2.4 线段障碍Voronoi 图的半平面求交算法
• 4.3 II 型线段障碍VORONOI 图
• 4.3.1 II 型线段障碍Voronoi 图的定义
• 4.3.2 II 型线段障碍Voronoi 图的性质
• 4.3.3 II 型线段障碍Voronoi 图的生成算法
• 4.4 线段障碍VORONOI 图的应用实例
• 4.4.1 存在障碍的邮局问题
• 4.4.2 购物问题
• 4.4.3 入学问题
• 4.5 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢