- 相关推荐
有关基于Mapx的最短路径选择算法的实现
摘 要：最短路径分析是智能交通系统和GIS道路网络分析中的重要组成部分。要实现最短路径的选择，必须具有道路、弧段和节点的拓扑信息，而Mapx的图形数据并不具有拓扑结构，因此在进行路径选择时必须先生成道路网的拓扑关系，再利用Dijkstra算法找出最短路径。
关键词：Dijkstra算法，Mapx，access，拓扑关系，最短路径引言软件技术的日新月异极大地推动了GIS的发展，如今组件式GIS的开发已成为GIS开发的潮流之一。组件式GIS的基本思想是把GIS的各大功能模块分为几个控件，每个控件完成不同的功能。各个GIS控件之间，以及GIS控件与其他非GIS控件之间，可以方便地通过可视化的软件开发工具集成起来。这种开发方式不但可以实现GIS的绝大部分功能，而且开发成本较低，也使开发人员无需掌握专门的GIS开发语言。Mapx是MapInfo公司开发的一个GIS控件，它使用与MapInfo一致的地图数据格式，并实现了MapInfo的大多数功能，如：tab格式地图的显示、地图的放大、缩小、拖动、专题图的制作、数据绑定、图层控制等[1]。
数据处理主要采用Tab表数据，地图数据按照内容的不同以图层(Layer)的形式存储，而道路网又可按照道路等级的不同进行分层存储。为了打印和存储的方便，需要把所有的道路图层中的图元及图元名称Clone到一个图层中。
最短路径分析中道路交叉点是系统实现的关键数据，确保道路在交叉处确实相交，并具有一个交叉节点。对于互穿的道路，可以利用intersectionpoints方法，把flags参数设置为来捕获一个交点，而对于在交叉口断开的道路，需要利用MapInfo的捕捉功能，使两条或多条道路在交叉口处交于一点，以消除道路网中的断点。
由于地图编辑中的失误，可能产生只有一个坐标点的线图元，在建立拓扑关系之前需要利用feature的Length属性把ftr.Length=0的线图元剔除。
基于Mapx的拓扑关系的构建最短路径分析是道路网络分析中的一个基本内容，其中的关键是建立道路网中各个弧段之间、节点之间和道路之间的拓扑关系。但Mapx最大的不足之处就是不能建立地图数据的拓扑结构，所以在进行最短路径分析时首先需要建立节点、弧段和道路之间的拓扑关系。
为获得适于道路搜索的路网图，必须将在交叉点处将道路拆分成最基本的路段，使其只在端点处与其他路段相交。拆分后的基本路段对应于路网图中的弧，其端点就是图中的顶点。
路网中的拓扑关系可以用三个二维表格分别存放顶点相关信息和弧段相关信息，如表1、表、表3。
表设置pnts点集和pnt点变量，利用feature的parts属性来获得道路图层中所有组成道路节点的坐标Node_X和Node_Y并把节点按递增的顺序进行编号。但是对于两条或多条道路交叉点不是道路已有节点的情况，就要利用Mapx的IntersectionPoints属性来获取道路的交叉点添加到Nodes表中。代码如下：
表主要利用Nodes表中的Type1字段生成。在Type1字段中字段值为1的点为道路的交叉点，道路在交叉点断开为基本的弧段，获得弧段的FromNode、ToNode编号和Edgename编号，而EdgeLength利用两两之间的节点距离相加而得。如图1：有四条道路，其中道路一节点的编号为1—11，被分成1—5、5—9、9—11三段弧，其中1—5弧段的长度为表利用ARC表生成，保存所有道路节点和弧段信息，主要是为了加快搜索速度。
算法在GIS中的实现算法原理算法是典型的最短路径算法，用于计算一个节点到其他所有节点的最短路径。
主要通过为每个顶点V保留目前为止所找到的从S到V点的最短路径来工作，首先以起始点为中心向外层扩展，，直到扩展到终点为止[2]。初始时，源点S的路径长度被赋为0(d[s]=0)，同时把所有其他顶点的路径长度设为无穷大(d[V]= ∞)，即表示不知道任何通向这些顶点的路径。当结束时，d[V]中存储的便是从S到V的最短路径，如果d[V]是无穷大说明从点到点V无可通的路径。Dijkstra算法的基本操作是边的拓展，如果存在一条从U到V的边，那么从S到V的最短路径可以通过将边(U，V)添加到尾部来拓展一条从S到V的路径。这条路径的长度是d[U]+W(U,V)(从顶点U到V的非负花费值)。如果这个值比目前已知的的值要小，可以用新值来替代当前d[V]中的值。拓展边的操作一直执行到所有的d[V]都代表从S到V最短路径的花费[3]。
算法的实现算法利用VB来实现，首先设置graph()二维数组来记录任意i点到其他所有顶点的距离，distance1()数组来记录起始点到其他所有顶点的距离，visited()来记录顶点的访问情况。
最短路径的显示利用Dijstra算法中返回的最短路径中所遍历的点生成最短路径。如图2：
由Dijkstra算法获取所遍历的顶点;利用遍历的相邻顶点的编号，在Nodes表中查找道路上所对应节点的编号;利用createline方法在图层dijkstra中创建最短路径所对应的线图元。
结论和展望本文通过对道路数据的处理、拓扑关系的创建、Dijkstra算法的实现等一系列研究工作，建立了道路数据库及其结点，弧段，道路三个表，构造了节点、弧段和道路之间的拓扑关系，实现了最短路径分析，增强了基于Mapx组件式二次开发的空间分析能力，但该问题的处理还有许多不足之处：
效率低：由于Dijkstra算法在搜索时要遍历所有的顶点，并且在创建拓扑关系时要遍历道路中的所有节点，计算量大、耗时长，有待于进一步改进。
数据的限制：在进行最短路径选择时，起始点和终点的坐标必须与道路上某一节点的坐标相同，在算法上需要进一步改善。
【基于Mapx的最短路径选择算法的实现】相关文章：
基于DSP的FFT算法实现的研究07-01
基于SOPC的LMS自适应滤波算法实现08-24
基于Cyclone系列FPGA的1024点FFT算法的实现09-30
基于MapX的城市GIS的初步建立08-06
图像拼接算法及实现07-23
基于MapX的多字段专题饼图的设计07-22
基于人性化管理分析旅游酒店管理的路径选择05-24
FFT算法的研究与DSP实现09-23