GIS网内容搜索
GIS网热门内容
GIS网推荐内容
GIS网最新内容
提出意见和建议
添 加：2008-04-01； 发 表：2008-04-01； 点 击：524
| GIS门户网提示：本文章共2760字，分2页，当前第1页，快速翻页： | |||
本文提出了一种基于矢量角度的最短路径搜索算法，设计出一种类似于面向对象的数据存储结构来存储网络图中的节点及弧段对象，在最短路径的搜索上引入矢量夹角标量值做为搜索因子，充分利用了网络图中各点元素和线元素间的拓扑关系，提高了搜索的趋势性，同时还考虑了各弧段的长度值（或权值），较好的将网络图中对象的空间信息和属性信息相结合…… 1 引言 随着地理信息产业的建立和数字化信息产品在全世界的普及，地理信息系统将深入到各行各业甚至各家各户，成为人们生产、生活学习和工作中不可缺少的工具和助手。 地理信息系统中网络分析功能的主要目的是对地理网络（如交通网络）、城市基础设施网络（如各种网线、电力线、电话线、供排水管线等）进行地理分析和模型化。 最短路径问题是地理信息系统网络分析中的最基本最关键的问题，在交通网络结构的分析，交通运输线路的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接应用的价值。 关于最短路径问题，目前为人们所公认的最好求解方法，是1959年由E.W.Dijkstar提出的标号法，但具体实现中在存储空间及运行效率上还存在着一定的问题。 本文从图形数据的存储结构及最短路径顶点的搜索策略两个方面对Dijkstra算法进行了改进，提出了一种基于矢量角度的最短路径搜索算法。 2 道路网络数据结构 构造类似于面向对象的数据结构存储网络图： Public Type Mynode（点结构） Dim NodeID As Integer '节点ID，唯一标识节点 Dim AdjoinNum As Integer '邻接弧段数量 Dim AdjoinArcID() As Integer '邻接弧段ID Dim AdjoinNodeID() As Integer '邻接节点ID Dim AdjoinClamp() As Double '指向邻接节点的矢量的角度 End Type Public Type MyArc（弧结构） Dim ArcID As Integer '弧段ID，唯一标识弧段 Dim Length As Double '弧段长 End Type 其中节点对象中的三个数组大小在初始化时利用邻接弧段数量设置大小，因此对应不同的节点对象其大小是不固定的，使用此种结构，对于有向图不会造成数据的冗余，而对应于无向图也仅多存储了一倍的弧段ID，邻接节点ID及矢量角度，相对于经典Dijkstra算法来说，需要的存储空间仍较小。对于弧段对象来说，其中的Length可以设置为弧段长度，也可根据需要设置为时间、费用等相应的权值。 3 算法原理 由两点之间直线最短的定理，构造一条理想最短路径（如图一中的AB），这条直线段一定是A、B两点间弧段中距离最短的一条。但实际上这条直线段作为一段道路存在的可能性极小，但这条从起点到终点的直线段却代表了一个路线的趋势，从概率的角度，顺着这个方向的某些路段的集合组成最短路径的可能性较大。  以矢量夹角标量值做为最短路径顶点选取的第一要素。 如图一，求解A、B两点间的最短路径。∠1为矢量Aa与矢量AB间夹角的标量值，当前节点的每个邻接节点都对应一个角度标量值，按照标量值的正负值大小，构造标识分别为正负的两个队列，两个队列均根据节点对应标量值的绝对值从小到大进行排序。 分别从正负两个队列中选出排在最前位的节点，加入到最短路径树中。 除第一次搜索外，其余过程中都需要判断搜索到的节点是否已存在于最短路径树中，如果该节点已存在于最短路径树中，则需要比较本次搜索过程结束后该节点信息与对应的最短路径树节点信息。
|
GIS
GIS