基于矢量夹角的最短路径分析

论文题目: 基于矢量夹角的最短路径分析

论文类型: 硕士论文

论文专业: 地图学与地理信息系统

作者: 张燕

导师: 付仲良

关键词: 地理信息系统,网络分析,最短路径,迪克斯拉算法,矢量夹角

文献来源: 武汉大学

发表年度: 2005

论文摘要: 随着地理信息产业的建立和数字化信息产品在全世界的普及,地理信息系统将深入到各行各业甚至各家各户,成为人们生产、生活学习和工作中不可缺少的工具和助手。 地理信息系统中网络分析功能的主要目的是对地理网络、城市基础设施网络(如交通网络、各种网线、电力线、电话线、供排水管线等)进行地理分析和模型化。 最短路径问题是地理信息系统网络分析中的最基本、最关键的问题,在交通网络结构的分析、交通运输线路的选择、通讯线路的建造与维护、运输货流的最小成本分析、城市公共交通网络的规划等,都有直接应用的价值。 关于最短路径问题,目前为人们常用的求解方法,是1959年由E.W.Dijkstar提出的标号法,但该方法在具体实现中在存储空间及运行效率上还存在着一定的问题。 本文从图形数据的存储结构及最短路径顶点的搜索策略两个方面对Dijkstra算法进行了改进,提出了一种基于矢量角度的最短路径搜索算法。该方法采用一种类似于面向对象的数据存储结构来存储网络图中的节点及弧段对象,相对于Dijkstra算法存储数据常用的邻接矩阵、邻接表等结构,节约了大量的存储空间。 在最短路径的搜索上引入矢量夹角标量值做为搜索因子,提高了最短路径搜索向终点的收敛速度;充分利用网络图中各元素间的拓扑关系,减小了每次搜索的节点范围;同时还考虑了各弧段的长度值(或权值),较好的将网络图中对象的空间信息和属性信息相结合。 经过实验,以本文讨论的算法求解最短路径得出的结果在准确性及速度方面都能满足实际要求。

论文目录:

摘要

Abstract

第一章 绪论

§1.1 研究的目的和意义

§1.2 国内外研究现状

§1.3 本文的研究内容

§1.4 论文组织

第二章 地理信息系统中的网络分析

§2.1 空间数据的组织与管理

2.1.1 空间数据的基本特性

2.1.2 空间数据的组织

2.1.2.1 栅格数据

2.1.2.2 矢量数据

2.1.2.3 栅格数据结构与矢量数据结构的比较

2.1.3 空间数据的管理

2.1.3.1 GIS数据库的特点

2.1.3.2 GIS数据库的管理

§2.2 空间拓扑关系

2.2.1 拓扑的概念

2.2.2 空间数据的拓扑关系

2.2.2.1 空间对象间的关系

2.2.2.2 拓扑关系的表示方法

2.2.2.3 拓扑关系的关联表达

§2.3 网络分析的基本功能

2.3.1 路径分析

2.3.2 资源分配

2.3.3 连通性分析

2.3.4 流分析

§2.4 最短路径分析

2.4.1 最短路径概念

2.4.2 最4短路径算法

第三章 基于矢量夹角的最短路径分析

§3.1 数据的存储结构

3.1.1 节点的存储结构

3.1.2 弧段的存储结构

3.1.3 树节点的存储结构

§3.2 最短路径搜索算法

3.2.1 理想最短路径

3.2.2 角度搜索的原理

3.2.3 角度搜索的特点

3.2.4 角度搜索的问题

3.2.5 基于矢量夹角的最短路径分析算法

§3.3 非交叉点位置间的最短路径分析

第四章 实验

§4.1 实验环境

4.1.1 数据来源

4.1.2 硬件环境

4.1.3 软件环境

§4.2 数据预处理

4.2.1 点元素的自动生成

4.2.2 线元素的拓扑检查

4.2.3 自定义对象的初始化

§4.3 算法实现

§4.4 结果显示

§4.5 结果分析

第五章 结束语

参考文献

致谢

发布时间: 2006-03-27

参考文献

• [1].基于道路网的最短路径算法的研究与实现[D]. 荣玮.武汉理工大学2005
• [2].基于网络分析的小型GIS平台的开发与实现[D]. 罗洪月.大连理工大学2007
• [3].最短路径分析及GIS/GPS集成技术研究[D]. 刘云翔.国防科学技术大学2002
• [4].基于集群的高性能GIS系统研究[D]. 姚闯.国防科学技术大学2016
• [5].水利地理信息系统的设计研究[D]. 胡品.东华理工大学2017
• [6].土遗址地理信息系统的设计与实现[D]. 史建尧.兰州大学2008
• [7].地理信息系统在银行业中的应用[D]. 宋美遐.首都师范大学2007
• [8].大型水利地理信息系统的建设研究[D]. 王勇.河海大学2007
• [9].地理信息系统中路径分析系统的设计与实现[D]. 司功闪.国防科学技术大学2003
• [10].香河供电公司低压配网地理信息系统设计与实现[D]. 闫亮.天津大学2015

相关论文

• [1].交通网络中最短路径算法的研究[D]. 戴文舟.重庆大学2004
• [2].城市道路网络最短路径的统计学特征及实用算法研究[D]. 孙健鹤.华东师范大学2006
• [3].基于道路网的最短路径算法的研究与实现[D]. 荣玮.武汉理工大学2005
• [4].WebGIS中最短路径算法及其应用的研究[D]. 陈珊.华东师范大学2005
• [5].动态最短路径的拟物方法的研究[D]. 徐海云.山东科技大学2005
• [6].并行遗传算法求解应急系统最短路径的研究[D]. 张晓波.太原理工大学2005
• [7].随机时间依赖网络中的自适应K期望最短路径[D]. 张勇.大连理工大学2006
• [8].最短路径问题的并行算法研究[D]. 平晓慧.大连理工大学2006
• [9].基于图论的动态导航系统最短路径算法研究[D]. 金振伟.广东工业大学2006
• [10].Dijkstra最短路径优化算法在汽车导航的研究及实现[D]. 王芬.上海师范大学2006

标签：地理信息系统论文;  网络分析论文;  最短路径论文;  迪克斯拉算法论文;  矢量夹角论文;