变速城市Voronoi图及其生成

论文摘要

城市Voronoi图是基于考虑L1-平面上任意两点之间花费的最短时间而提出的,它作为Voronoi图在距离方面的推广具有重要意义。本文对城市Voronoi图定义作了进一步的扩展,提出了一种新的城市Voronoi图——变速城市Voronoi图,给出了变速城市Voronoi图的定义、性质及相关证明,同时提出了一种基于结晶生长方式的直接构造变速城市Voronoi图的算法,该方法也完全适用于构造城市Voronoi图。结晶生长是从若干个点出发,每一点分别按照各自的生长方式结晶式向外扩展的一种方式。该算法与生成元的个数,交通路线的条数、类型和位置无关,简单易行,效率较高,尤其在构造生成元个数较多,交通网络比较复杂的变速城市Voronoi图方面具有显著优势。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 计算几何与Voronoi图
• 1.2 问题提出的现实背景及研究现状
• 1.2.1 问题提出的现实背景
• 1.2.2 问题的研究现状
• 1.3 论文的研究内容
• 1.4 论文的结构安排
• 第二章 Voronoi图和城市Voronoi图
• 2.1 Voronoi图
• 2.2.1 Voronoi图的定义及其基本性质
• 2.2.2 Voronoi图的主要生成法
• 2.2 城市Voronoi图
• 2.2.1 城市Voronoi图的定义及简单性质
• 2.2.2 构造城市Voronoi图的基本思想
• 第三章 变速城市Voronoi图
• 3.1 变速城市Voronoi图的定义
• 3.2 变速城市Voronoi图的基本性质
• 第四章 变速城市Voronoi图的生成算法
• 4.1 结晶生长的定义
• 4.2 算法的基本思想
• 4.3 算法实现的几个关键步骤
• 4.3.1 确定当前生长点的生长方式
• 4.3.2 确定象素点是否位于交通路线上
• 4.3.3 实现交通路线上的生长点在交通路线方向上的扩展
• 4.3.4 实现结晶生长过程
• 4.3.5 变速城市Voronoi区域的形成过程
• 4.3.6 变速城市Voronoi边的抽取
• 4.4 变速城市Voronoi图的离散生成算法
• 4.5 与已有算法的比较
• 第五章 应用举例
• 5.1 作图实例
• 5.2 应用实例
• 第六章 总结与展望
• 6.1 本文工作总结
• 6.2 进一步研究工作
• 参考文献
• 致谢
• 附录