论文题目: 欧氏障碍空间的最短路径问题解法（MA-ESPO）
论文类型: 博士论文
论文专业: 地图学与地理信息系统
作者: 杨传勇
导师: 胡鹏
关键词: 最短路径,障碍,网络分析,计算几何,地图代数
文献来源: 武汉大学
发表年度: 2005
论文摘要: 欧氏障碍空间的最短路径问题(ESPO:Euclidean space Shortest Path with Obstacles)问题是网络分析中基础和核心问题一最短路径问题的更广义问题,是图论、S计算几何、网络设计、网络最优化等领域的基本理论问题,其中三维ESPO是NP-难问题,至今无其它有效解。它的突破将具有重要科学意义和巨大经济价值。本论文针对这一问题,进行了重要研究。 本论文分析了空间数据的基本特征以及空间数据的表达模型,提出了空间数据的“位”、“邻”、“近”、“势”的概念,完善了空间关系的描述。提出了空间衍生数据显式初始化带来的运算、存贮开销,以及对复杂、动态、连续地理过程的分析处理的不适应性,从整体上提出了当前GIS的空间分析存在的空间复杂性理论问题。 提出了新型“矢—栅”紧密结合型数据模型:“矢量为体,栅格为用,矢栅互换,利用长处”,这是一条新型GIS的建设路线。论述它全面解决空间问题的可行性、动态性、规范性,并给出了地图代数的“栅→矢”新方法和“矢→栅”中经典方法构成了一对“矢栅互换”支撑技术。并以三维形体集合运算,结合复杂的三维ESPO空间分析,三维点集精密绘图,在主要关键上给出了它的实验论证。 本文提出了MA—ESPO方法。理论上和实验上解决了著名的二维、三维障碍空间最短路径ESPO问题,并且把障碍物、源、汇图形都扩大到全形态图形,是著名Dijkstra问题的广义解。它是以地图代数栅格路径距离变换原理为基础发展、拓广而成,在理论上论证了该方法能在任意有限的障碍空间内,以指定精度,有效实现最短路径;在算法中实现了模板(2k+1)~3中正整数k动态扩大的自动机制和算法;并提供了大区域分段、分块技术作业的理论和技术保证:其时间复杂性为O(kn),k为不大的常数(其决定于区域大小的小型模板中元素);空间复杂性为O(n)。 给出了MA-ESPO统一方法实验软件。它在二维上,能提供3000~2范围内障碍空间最短路径ESPO广义问题解决实验验证,三维上,能提供200~3范围内障碍空
论文目录:
摘要
ABSTRACT
第一章 绪论
1.1 ESPO问题研究
1.1.1 欧氏障碍空间及其空间问题
1.1.2 最短路径问题(Shortest Path)
1.1.3 欧氏障碍空间的最短路径问题(ESPO)
1.1.4 广义ESPO问题研究内容
1.2 国内外研究现状及分析
1.2.1 国内外研究现状
1.2.2 解决状况回顾与分析
1.3 本论文内容安排
第二章 解决ESPO问题的空间数据模型
2.1 度量空间及几个重要概念
2.1.1 尺度的数学定义
2.1.2 欧氏度量空间
2.1.3 点到点集间的距离
2.1.4 距离变换
2.1.5 欧氏障碍空间中的相应概念
2.2 GIS空间数据模型
2.2.1 空间数据几个重要概念
2.2.2 空间数据模型
2.3 实体数据的表达
2.3.1 空间“位”数据的表达
2.3.2 空间关系数据的运算和表达
2.4 空间数据组织的困惑和应对
2.4.1 空间数据量分析实例
2.4.2 空间数据表达模型的复杂性
2.4.3 复杂动态的空间数据组织和空间数据初始化问题
2.5 ESPO问题的数据组织和初始化
2.6 本章小结
第三章 E~2、E~3下ESPO研究
3.1 地图代数的栅格平面
3.2.E~2下障碍空间的距离传播和最短路径
3.2.1 E~2下小障碍空间的距离变换
3.2.2 有限障碍区域上距离变换
3.2.3 讨论
3.2.4 E~2下ESPO研究小结
3.3 E~3下障碍空间的距离传播和最短路径
3.3.1 E~3下3×3×3邻域的栅格路径障碍距离变换
3.3.2 有限障碍区域上距离变换
3.3.3 误差分析
3.3.4 最短路径
3.4 讨论
3.4.1 时间复杂性
3.4.2 空间复杂性
3.4.3 圆盘和球的运动规划和最短路径
3.4.4 E~3下ESPO研究小结
第四章 三维ESPO问题的栅格数据生成与可视
4.1 障碍空间数据数据生成组织和初始化
4.1.1 三维栅格坐标系统
4.1.2 障碍物、源与汇数据
4.1.3 最短路径数据
4.2 障碍空间数据数据组织和初始化
4.2.1 空间数据数据组织
4.2.2 空间数据数据初始化
4.3 三维栅格数据可视化
4.3.1 栅格点集数据可视化的数据结构
4.3.2 光照和法向量处理
4.3.3 几何图原的中心位置和投影变换
4.3.4 表面点和隐藏点
4.3.5 剖面图显示
4.3.6 显示实例
4.4 本章小结
第五章 MA-ESPO实验软件的设计和实例
5.1 E~2下障碍空间的结构分析
5.1.1 E~2下13×13邻域内距离的传播
5.1.2 E~2下障碍空间的距离传播
5.1.3 13×13模板的数据结构
5.1.4 E~2下空间结点的数据结构
5.1.5 E~2下MA-ESPO的设计
5.2 E~3下障碍空间的结构分析
5.2.1 E~3下13×13邻域内距离的传播
5.2.2 E~3下障碍空间的距离传播
5.2.3 13×13×13模板的数据结构
5.2.4 E~3下空间结点的数据结构
5.2.5 E~3数据的存储结构
5.2.6 E~3下MA-ESPO的设计
第六章 分析、应用与展望
6.1 本文创新内容和分析
6.1.1 创新内容
6.1.2 讨论及分析
6.2 应用与展望
参考文献
攻博期间的主要科研工作
致谢
发布时间: 2006-03-27
相关论文
- [1].复杂动态随机网络最短路径问题研究[D]. 俞峰.浙江大学2009
- [2].时变、随机网络最优路径算法及其应用研究[D]. 谭国真.大连理工大学2002
- [3].避障路径规划的算法研究[D]. 戴光明.华中科技大学2004
- [4].地貌信息提取中的结构化问题研究[D]. 王涛.武汉大学2005
- [5].地理本体的形式化表达机制及其在地图服务中的应用研究[D]. 黄茂军.武汉大学2005
- [6].空间可视分析的关键技术和应用研究[D]. 应申.武汉大学2005
- [7].土地利用数据库综合的结构化模型和算法研究[D]. 陈先伟.武汉大学2005
- [8].大区域分布式多级道路网的最优路径算法与服务研究[D]. 陈玉敏.武汉大学2005
- [9].GIS的空间数据零初始化与栅格网络分析研究[D]. 李圣权.武汉大学2004
- [10].空间相似性理论与计算模型的研究[D]. 丁虹.武汉大学2004