基于GIS线性矢量图形的最优路径算法研究及仿真实现 摘 要：为了能够动态高效的采集线性矢量图形节点信息，本文提出了一种采集矢量图形节点信息的“截枝算法”，该算法尤其是适用于节点之间有多条线段连接的复杂的线性管网结构，在此基础上应用Dijkstra算法确定出了线性矢量图形任意两节点之间的最优路径节点序列。最后利用VC++语言和基于COM的MapObejcts组件技术实现了基于上述算法的仿真软件GISLOOP，并对国家基础地理信息系统（NFGIS）1:400万主要公路数据文件roa_4m进行仿真分析，结果证明了算法的高效性和准确性。 关键词：GIS线性矢量图形，截枝算法，Dijkstra算法，最优路径，VC++，MapObjects2 COM组件 中图分类号：TP391 Optimal Path Algorithms Research Based On the GIS Linear Vector Graphics and Simulation Implementing Abstract: The paper offer a “Cut Branch Algorithm” for sample the information of nodes that lies in the GIS linear vector graphics, Usually, it is more effectively for complex networks system. On the basis of it, we get the optimal path sequence by applying the Dijkstra algorithm. At last, We developing a simulation software “GISLOOP” that use VC++6.0 programming language and ESRI’s MapObecjts2 Component as a development tools. Depend on this software we analyzed the GIS shapefile “road_4m” that download from the National Foundation Geographic Information System (NFGIS) and make some approving results. Keyword: GIS Linear Vector Graphics, Cut Branch Algorithm, Dijkstra Algorithm, Optimal Path, VC++ programming language, MapObjects2 COM Component 一、引言 地理信息系统(Geographic Information System，简称GIS)是集计算机科学、地理学、测绘遥感学、环境科学、城市科学、空间科学、信息科学和管理科学为一体的一门新兴边缘学科。从Tomlinson在1967第一次提出了GIS的概念起，特别是近十几年以来，随着计算机技术、通信技术以及图形技术的发展，GIS在交通管理、物流配送、城市规划、环境保护等方面应用都取得了快速的发展。本文主要研究的是基于一类GIS矢量图形 — 线性矢量图形[7]线段节点信息动态采集以及任意两节点间最优路径的算法，在此算法基础上开发出了实用的GIS应用程序软件 — GISLOOP，并对国家基础地理信息系统（NFGIS）1:400万主要公路数据文件roa_4m进行最优路径分析，证明了算法的高效性和准确性。 最近十几年来，国内外都对GIS系统进行了大量的研究，并开发出许多成功的软件系统如国外的ArcInfo、MapInfo和国内的MapGIS、CityStar等，并提供一些二次开发的平台如MapObjects和SuperMap等。其中最优路径分析是GIS网络分析的一个基本的问题，国内外学者都对此进行了大量的研究。如经典Dijkstra算法[5]和Floyd算法[6]，还出现了一些诸如利用节点—弧段联合结构来表示图并利用深度优先算法实现最短路径的自动判断与获取的方法[4]等算法。结合其它技术，这些算法成功的应用在了交通车辆最佳路由调度问题[2], [3]，及无线通信网络实时分组最优路由问题[1]上等。但是在线形矢量图形中可能存在大量的折线段以及大量的端点，如在1:400万中国主要公路数据文件roa_4m中有151条折线段和36818个顶点，复杂图形更是如此，直接利用上述算法构造端点之间的邻接矩阵，不仅要浪费大量宝贵的计算时间和存储空间，还不可避免的出现“维数灾”问题，从而使某些实时（结合GPS）复杂图形路由问题成为不可能。 基于上述存在的问题，本文将GIS线形矢量图形最优路径确定问题分两方面来进行：应用截枝算法对原矢量图形进行预先处理以简化网络并构造相邻节点的邻接矩阵，如上述中国公路数据文件的预处理中可将原矢量图形151条折线段和36818个顶点合并成94条线段和74个节点并构造相邻节点中邻接矩阵；接着应用传统的Dijkstra算法来得到最优路径的节点序列。 二、应用截枝算法构造简化网络相邻节点间的邻接矩阵 本文将线性矢量图形节点划分为“端点”和“交叉点”，端点指的是在一条或者是两条线段上的点，交叉点指的是在三条或者是三条线段之上的点。通过这种划分我们可将相邻节点距离的采集分为端点到交叉点，交叉点到交叉点两个步骤来实现，由于端点到交叉点之间是一维的搜索，在端点较多的情况下可大大加速相邻节点距离采集的速度。 因原线性矢量图形存储的线段本身的不连续性，比如一条连续线段在数据库中可能是分成多条线段来进行存储的，故在确定线性矢量图形的端点和交叉点之前，应首先对原矢量图形的线段进行合并，如在实现程序中将roa_4m数据库中将151条原始公路线段以及36818个顶点合并成了97条线段、24个端点和50个交叉点。这样就大大提高了计算速度和减少了存储空间。 采集相邻节点的距离分两个步骤来实现：从端点到交叉点以及从交叉点到交叉点。通过上面的定义可知从端点到交叉点之间有且只有一条线段，采用一维搜索的方法搜索次数不超过合成线段的总数，而且一旦满足条件即可进行下一次的搜索，实现起来相对容易。而交叉点到交叉点之间可能有多条的连接线段，在数据量较大时，遍历整个数据库来得到所有的相邻线段是不可能的，故本文提出了一种“截枝算法”来实现交叉点与交叉点之间距离的采集并在第四部分给予实现。 “截枝算法”算法的主要思想是为了避免计算机对已经搜寻过的线段进行重复搜寻，可动态的将已经搜寻过的满足条件的线段进行删除，动态的改变搜寻线段数组的大小，随着搜索进程的进行，需搜索的的线段越来越小，直至为线段数组大小为0或者是所有的节点搜寻完毕即可结束。 当“交叉点”之间有很多条连接线段时，运行结果证明搜寻效果更加明显。如在roa_4m数据库中的公路有50个交叉点，随着程序运行，需要搜索线段总数随交叉点数变化的关系如图1所示。从图中可以可看出算法是收敛的，采集第1个交叉点需要搜索151条线段，而对最后一个交叉点（第50个）的距离的采集中只需要搜索4条线段。从而证明该算法在实践中是可行的。 需要说明的是在程序实现中，采集相邻节点距离的过程实质上就是获取相邻节点的线段，因为线段是GIS矢量图形，该线段包含实际的地理长度信息(线段长度 比例尺)和其他的一些权值信息，故可确定其他的最优权值路径（如费用等），在本文中的讨论以最短路径为主。随后对节点（端点和交叉点）进行动态的编号，构造相邻节点的邻接矩阵，为下一部分的Dijkstra算法提供数据准备。 三、应用Dijkstra算法确定任意两节点间最优化节点序列 Dijkstra在1959年提出了一种计算两个节点最短路径算法，所采用的图遍历是以顶点为基数的二次循环，每重循环的次数均为节点数 ，其算法执行时间复杂度为O（ ）。 在程序实现上，图形中每个节点用沿已知最佳路径到本节点的距离来标注。开始，一条路径也不知道，故所有的节点都标注为无穷大，随着算法的进行和不断找到的路径，标注随之改变，使之反映出较好的路径。一个标注可以是暂时性的，也可以是永久性，在搜寻开始时，所有的标注初始化为暂时的，在算法的进行过程中如果发现标注代表了从源节点到终节点的最短可能路径时，就使它成为永久性的，不再进行修改。 在程序模块的初始化过程中，不相邻的两个节点间的距离初始化为0。考虑到两个节点之间不连通的情况，在程序中也增加了阈值控制避免进入死循环。 在程序中定义了一节点状态的结构，如下所示： typedef struct _nodestate { UINT Previous_node; //工作节点的前继节点 DOUBLE Length; //从起点到本节点的（最短）距离 BOOL Labelstate; //标注本节点是临时节点还是永久节点 }Node_state [MAX_NODES]; //MAX_NODES定义在stdafx.h中 四、GISLOOP仿真软件实现 程序采用VC编程语言[8]和ESRI的MapObjects2 COM组件[7]，[9]来实现算法，仿真数据采用国家基础地理信息系统（NFGIS）1:400万主要公路数据文件roa_4m，该数据可从http://nfgis.nsdi.gov.cn下载。 程序除实现任意节点间最短路径的查询显示外还实现了：图形的放大缩小漫游功能、信息查询、事件显示、节点编号标注以及图形的最优路径保存、亮显和打印功能等。 程序添加了两个MapLayer层，roa_4m和bou2_4p（中国省界矢量图形）。其中bou2_4p是为了在程序中现实局部的最短路径而设置的。该程序支持两种查询方式：全部查询和局部的选择查询。全部查询又分为以省界为界和国界为单位的查询，如在本例中分别包含219和151条原始线段。下面以国界为单位的全部查询来介绍。 首先获取全部矢量线段，roa_4m包含了151条原始线段，在程序获取数据对话框列出了每条线段的的起点坐标、终点坐标以及线段的长度。随后进行获取图形的端点、交叉点、端点到交叉点以及交叉点到交叉点的的线段，分别为24，50，24，73；然后进行节点编号、节点矢量距计算构造相邻节点的距离。结果如图2所示。(其中在图形中端点到交叉点以及交叉点到交叉点之间的是直线的显示，而实际的计算是有多点的折线段，在程序中每一条直线段都对应着一条合成折线段。这主要是为了提高搜索速度，以及在计算相邻节点矢量距提供校验手段而设置的。) 之后就可以在图中选择起点和终点，然后进行最短路径查询。我们任意选取图中两点，进行最短路径查询，就得到了这两点间的最短距离66.927875，并显示最短的路径，如图3所示。要想得到其他任意两个节点之间的最短路径，可重新选取两个节点，直接进行查询，不需要进行上述的节点编号和矢量距计算，因在此之前，程序已经存储了网络的拓扑信息，不需要数据的准备阶段，在以后的查询中可进行快速的查询。 为了对大型的管网模型进行快速查询以及实际应用的灵活性（如在该最短路径必须经过某条道路等等）等原因，程序还提供了一种局部选择查询的方法来进行最优路径的查询。如图4所示。具体的操作方法是连续点选择多个区域，先在该区域线段中进行快速的查询，确定在该区域中的最短路径，在此基础上再选择另一区域进行二级查询，以此类推还可进行多级查询。该方法需要人的参与，并且每次都需要准备数据的阶段，故在中小型线性网络模型中采用全部查询的方法。 多次的运行结果证明，无论是运行速度还是准确程度（在已运行的次数中100%正确）上，都取的了极好的效果。还需要说明的是软件不依赖特定的线性矢量图形，其功能可不加修改的应用到其他的线性矢量图形，具有通用性。 五、结论 本文采用“截肢算法”动态的采集节点间的线段以及Dijkstra算法确定两点间的最佳距离，从而可对任意的线性矢量图形进行快速节点信息动态采集，并通过线段数据库相应的字段（距离，费用，流量等，本例为距离）的进行其它最佳权值确定，并得到了以下的结论： （1）对于节点间有多条连接线段的情况，应用“截肢算法”可取得更高的搜索效率。故该算法可更适合复杂管网模型的节点信息采集。 （2）在实现上，不依赖特定的线性矢量图形，具有通用性。对不同的矢量图形经过动态的采集节点信息后，在以后的每次搜索中可快速的进行查询。 （3）基于节点信息是以矢量线段为基础的，通过查询矢量线段的数据库可实现其他权值的最佳路径。 （4）对于大型的管网模型，可多区域，多级的采集节点信息来确定最佳的权值路径，增加了程序的实用性和灵活性。 （5）算法和程序的实现过程中并没有局限于一层图形，因而可进一步扩充为多层不同线性矢量属性的最优查询。 参考文献： 1、Karimi, H.A, Krishnamurthy, P. Real-time routing in mobile networks using GPS and GIS techniques. System Sciences, 2001. Proceedings of the 34th Annual Hawaii International Conference on,2001, Page(s)3470-3480. 2、You-Ning Wang,Thompson,R.G., Bishop,I. A GIS based information integration framework for dynamic vehicle routing and scheduling Michael Kunes and Thilo Sauter, Vehicle Electronics Conference, 1999. (IVEC ´99) Proceedings of the IEEE International , 1999 Page(s): 474 -479 vol.1. 3、Holtzman, J., Hui, J., Moayeri, N., Seskar, I., Varma, H., Yip, J., Maric, S., Williams, T. A vehicular traffic GIS and simulator for route guidance on NY/NJ highways. Vehicle Navigation and Information Systems Conference, 1993., Proceedings of the IEEE-IEE , 1993 Page(s): 367 –372. 4、王杰臣,毛海城,杨得志.图的节点-弧段联合结构表示法及其在GIS最优路径选取中的应用[J],测绘学报 2000，2,Vol.29,No.1 P47-51. 5、Andrew S. Tanenbaum 《计算机网络》第三版，清华大学出版社。 6、陈宝林. 《最优化理论与算法》清华大学出版社。 7、MapObjects Online Reference, 18th, June 1999. 8、David J.Kruglinski, Scot WIngo, George Shepherd. "Programming Visual C++",Fifth Edition, Microsoft Press.(English version) 9、Dale Rogerson. 《COM技术内幕—微软组件对象模型》， 清华大学出版社(中文版) 相应的源程序可来信索取，此外文中部分省！Tman
