资源描述：
《基于栅格法的矢量路径规划算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3期王卫红等:基于栅格法的矢量路径规划算法·57·*基于栅格法的矢量路径规划算法王卫红,顾国民,秦绪佳,李琰琰(浙江工业大学软件学院,浙江杭州310032)摘要:最短路径分析是网络分析系统的最基本的功能之一,在地理信息系统(GIS)中有着重要应用。将栅格法应用于矢量图层中进行节点的预处理,提出并建立一个存储点的拓扑空间模型,在此空间模型的基础上对Di-jkstra算法进行改进和优化,利用在处理一个点的同时预处理与它相邻的节点的方法,从时间和空间上提高了该算法的效率。实验结果表明,改进算法搜索速度快、占用空间小,该算法可用于小容量终
2、端机上。关键词:最短路径分析;栅格;空间分析;Dijkstra算法;地理信息系统中图法分类号:TP301文献标识码:A文章编号:1001-3695(2006)03-0057-03AlgorithmofVectorRoutePlanningBasedonRasterMethodWANGWei-hong,GUGuo-min,QINXu-jia,LIYan-yan(CollegeofSoftware,ZhejiangUniversityofTechnology,HangzhouZhejiang310032,China)Abstract:T
3、heshortestrouteanalysisisoneofthefundamentalfunctionsinnetworkanalysissystem.Ithasanimportantap-plicationinGeographicalInformationSystem(GIS).Atopologicalspacemodelhasbeenpresentedandbuilt,whichstoreallpointsinthevector-graphlayerbasedongridmethod.TheclassicalDijkstraa
4、lgorithmisimprovedandoptimizedbasedonthetopologicalspacemodel.Intheprovedalgorithm,whentreatingapoint,allpointsadjoinsthepointarepre-treatedandputinatemporaryset.Experimentsdemonstratethattheimprovedalgorithmcanspeeduptheroutesearchinganddecreasetheme-moryoccupancy.The
5、newalgorithmcanbeusedtosmallmemoryterminal.Keywords:ShortestPathAnalysis;Raster;SpaceAnalysis;DijkstraAlgorithm;GIS(GeographicalInformationSystem)随着计算机和地理信息系统(GIS)的飞速发展,GIS技术率。本文就是通过从这两个方面来阐述如何实现更高效的最[2]因其强大的功能已经运用到社会各个领域。对地理网络、城市短路径的查找。基础设施网络(如交通线路等)进行地理分析和模型优化,是1基于栅格
6、算法的网络拓扑的建立地理信息系统中网络分析功能的主要目的,网络分析是非常重要的空间分析功能之一。路径分析是GIS中网络分析的最基拓扑空间关系是一种对空间结构进行明确定义的数学方本功能,其核心是对最短路径(或最佳路径)的求解,不仅可以法,具有拓扑关系的矢量数据结构就是拓扑数据结构。一般具指地理上的距离最短,还可以引申到时间最短、费用最少等,但有了拓扑结构就可以很快地确定一种地图实体相对于另一种它们的核心都是最短路径算法,即求取指定网络模型中两点或地理实体的空间位置关系。对于拓扑关系的自动建立问题,研[1]者多点间阻碍强度最小的路径。随
7、着计算机硬件技术的飞究焦点是如何提高算法与过程的效率。速发展,在最短路径查找中,空间存储已经不是主要考虑的问每条弧段都有两个端点,即节点。一个图层上的所有节点题,于是通常的做法是以空间来换取时间。这确实让算法的效在未处理之前是散乱的,需要通过节点匹配建立起节点与节率有较大的提高,本文的重点也是放在提高时间效率上。但是点、节点与弧段之间的拓扑关系。假设有N条弧段,即有2N现今计算机终端设备的多样化,如车载终端等小容量存储设备个节点,可以通过两两匹配建立起拓扑关系,但是其时间复杂的出现,要求在算法设计时也要考虑到空间方面的效率。当前度是
8、2N×(2N-1),对于处理海量数据的路径查找来说是难的路径分析的众多算法中,最趋于成熟的还是Dijkstra算法。[3,4]以让人忍受的。本文采用的栅格法大大缩短匹配时间。本文也在这个算法的基础上,从时间和空间两个方面来考虑优1.1
