线段障碍城市Voronoi图的结晶生成

摘要

线段障碍城市Voronoi图是在城市Voronoi图基础上的扩展。城市Voronoi图的提出是基于一种平面为L1的度量，要求交通网络路线是水平和竖直方向，并且可以在任意点自由进出交通网络的具体模型。但客观世界中没有障碍而直接通行的情况是相对较少的，绝大部分交通网络都被一个个各种形状的障碍隔开，在各种形状的障碍中，又以线段障碍最为重要，许多障碍可以近似为线段障碍来处理，因此研究线段障碍的城市Voronoi图是很有必要的。 本文给出了线段障碍城市Voronoi图的定义、性质和相关性质的简单证明，同时，给出了线段障碍城市Voronoi图的结晶生成算法和程序实现，该算法简单，无需复杂的数据结构，可读性好，还可推广到任意障碍的几何图形，文中结合实例给出了线段障碍城市Voronoi图的应用，较好地解决了有障碍的基于平面L1度量、交通路线为水平和竖直方向且以时间距离考虑的对平面区域的分割。

目录

声明

摘要

第一章 绪论

1.1 Voronoi图的历史及应用

1.2 问题提出的现实背景及研究现状

1.3 论文的研究内容

1.4 论文的结构安排

第二章 Voronoi图、障碍Voronoi和城市Voronoi图

2.1 Voronoi图

2.1.1 Voronoi图的定义及其基本性质

2.1.2 Voronoi图的主要生成法

2.2 障碍Voronoi图

2.2.1 障碍Voronoi图的定义

2.2.2 障碍Voronoi图已有的生成方法

2.3 城市Voronoi图

2.3.1 城市Voronoi图的定义及简单性质

2.3.2 城市Voronoi图生成的基本思想

第三章 线段障碍城市Voronoi图

3.1 线段障碍城市Voronoi图的定义

3.2 线段障碍城市Voronoi图的性质

第四章 线段障碍城市Voronoi图的结晶生成

4.1 线段障碍城市Voronoi图结晶生成法的基本思想

4.2 线段障碍城市Voronoi图结晶生成算法

4.3 线段障碍城市Voronoi图结晶生成算法实现的关键技术

4.4 与已有算法的比较

第五章 应用举例(邻近就医问题)

第六章 总结和展望

6.1 本文工作总结

6.2 进一步要研究的工作

参考文献

致谢

附录