（信号与信息处理专业论文）基于道路网的最短路径算法的研究与实现.pdf

武汉理工大学硕士学位论文 摘要 地理信息系统( g i s ) 是以地理空间数据库为基础，采用地理模型分析方法， 适时提供多种空问和动态的地理信息，为地理研究和地理决策服务的强有力的 工具。随着计算机及网络的普及和发展，g i s 因其强大的功能得到日益广泛和 深入的应用。网络分析作为g i s 最主要的功能之一，在电子导航、交通旅游、 城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用。 最短路径问题是网络分析中最基本的问题，它作为许多领域中选择最优问题的 基础，在交通网络分析系统中占有重要地位。最短路径分析在车辆导航系统以 及各种城市应急系统中有着广泛的应用。 本文介绍了有关地理信息系统的一些基本概念，包括地理信息系统概念、 地理信息系统的发展及现状、地理信息系统的应用领域、地理信息系统数据模 型、地理信息系统数据的组织和管理、地理信息系统中的网络分析，简述了地 理信息系统应用软件m a p l n f o 的特点。 针对城市交通道路网的特点，对基于城市道路网的最短路径分析的关键技 术进行了研究和分析，着重分析研究了城市交通道路网的矢量地图表达、网络 拓扑结构的提取和构建、最短路径算法的高效实现等关键技术。 最短路径问题是交通网络分析中的一个重要问题，也是交通地理信息系统 ( g z s t ) 中的一个研究热点。它是资源分配、路线设计及分析等优化问题的基 础。本文根据g i s 中网络计算的实际情况，从网络结构的拓扑表示以及d i j k s t r a 算法中快速搜索技术的实现入手，提出了一种基于椭圆限制区域的优化二叉堆 优先级队列的改进型d i j k s t r a 最短路径算法。此算法是在对城市交通网络空问 分布特征进行统计分析的基础上，针对具体的起点、中间点以及终点，设定合 理的椭圆限制搜索区域，以减少算法的搜索规模；并且利用两点问直线段最短 的原理，以当前节点的邻接点与当前点和终点连线夹角最大作为贪婪搜索策略。 该算法能够有效降低d i j k s t r a 算法的时间复杂性，提高系统的运行效率。 在系统实现部分，利用m a p b a s i c 语言，在m a p l n f o 平台上实现了最短路径 分析，可通过简单的点击操作，确定起点、中间点和终点，得到最短路径并予 以显示，方便直观。 关键词：最短路径算法，d i j k s t r a ，地理信息系统，网络分析 1 i 一一一 堕坚堡兰盔堂堡! 堂垡堡茎 a b s t r a c t w i t ht h ep r e v a l e n c eo ft h ec o m p u t e ra n dt h en e t w o r k ，a n dt h ed e v e l o p m e n to f g e o g r a p h i c a li n f o r m a t i o ns c i e n c e ，g e o g r a p h i c a li n f o r m a t i o ns y s t e m ( g i s ) h a sg r e a t a p p l i c a t i o nf o rp o w e r f u lf u n c t i o n n e t w o r ka n a l y s i s ，a so n eo ft h em o s tp r i m a r y f u n c t i o n ，h a sa ni m p a c tu p o nm a n yn e t w o r ki n c l u d ee l e c t r o n i cn a v i g a t i o n 、t r a f f i c t o u r 、c i t yp l a n n i n g 、e l e c t r i cp o w e r 、c o m m u n i c a t i o n a n ds oo n s h o r t e s t p a t hp r o b l e m i so n eo ft h ep r i m a r y p r o b l e m s o fn e t w o r k a n a l y s e s a st h eb a s eo fo p t i m a ls e l e c t i o n p r o b l e mi nm a n yf i e l d s ，c o m p u t i n gs h o r t e s tp a t h so v e ran e t w o r kh a sb e c o m ea n i m p o r t a n tt a s ki nm a n yt r a n s p o r t a t i o na n dn e t w o r ka n a l y s e ss y s t e m s s h o r t e s tp a t h a n a l y s i s h a sb e e nw i d e l yu s e di nv e h i c l el o c a t i o n s y s t e ma n dc i t ye m e r g e n c y s y s t e m s t h ep a p e rd e s c r i b e ss o m ep r i m a r yc o n c e p t i o n sa b o u tt h eg i s ，i n c l u d i n gt h e c o n c e p t ，m a t h e m a t i c sm o d e l ，t h e f r a m e w o r ka n dm a n a g eo fd a t a ，n e t w o r k a n a l y s i s o f g i s t h e p a p e rs t u d i e sa n dt e s t st h ek e yt e c h n i q u e so fs h o r t e s tp a t ha n a l y s i s w es e t f o c u so ns o l u t i o n sw h i c hi n c l u d et h ev e c t o rm a pr e p r e s e n t a t i o no fc i t yr o a d n e t w o r k ，t h ea b s t r a c t i o na n dc o n s t r u c t i o no ft h et o p o l o g i c a ls t r u c t u r eo fn e t w o r k ，a n d t h ee f f i c i e n ti m p l e m e n t a t i o no fs h o r t e s tp a t h a l g o r i t h m b a s e do nt h ef a c to fg i sn e t w o r k s ，w es t a r tw i t hc o n s t r u c t i o no ft h et o p o l o g j 【c a l s t r u c t u r eo fn e t w o r ka n dt h er e a l i z a t i o no fr a p i ds e a r c ht e c h n o l o g yo fd i j k s t r a a l g o r i t h m ，a n dp r o p o s e t h ei m p r o v e dd i j k s t r as h o r t e s ta l g o r i t h m ，w h i c hi m p r o v et h e t r a d i t i o n a lo p e r a t i o n so fb i n a r yh e a po p t i m a la r r a yo nt h eb a s eo fl i m i t i n gr e g i o no f u s i n ge l l i p s e i ti sb a s e do n t h es t a t i s t i c a la n a l y s i so fc h a r a c t e ro fc i t yt r a n s p o r t a t i o n s p a c ed i s t r i b u t i n g ，a n dd e s i g na r e a s o n a b l el i m i t i n gr e g i o no fu s i n ge l l i p s et or e d u c e t h es c a l eo ft h es e a r c ho ft h ea l g o r i t h m a n di tm a k e su s eo ft h et h e o r yt h a tt h e b e e l i n ei st h es h o r t e s tb e t w e e nt w op o i n t s ，a n dw e g e tt h en e wg r e e d y s e a r c hs t r a t e g y w h i c hi sd e t e r m i n e db yt h em a x i m u md e g r e et h a tc o m b i n e db yt h ec u r r e n tn o d e ，i t s n e a r e s tn o d ea n dd e s t i n a t i o nn o d e a tl a s t ，b a s e do na b o v ea l g o r i t h m s ，t h ea l g o r i t h m i n 武汉理： 大学硕士学位论文 i sp r o p o s e d a n dt e s ts h o wt h a tt h ep r o p o s e da l g o r i t h mh a st h ep r a c t i c a b i l i t ya n d f l e x i b i l i t y ，c o u l dm e e t t h er e q u i r e m e n t s k e y w o r d s ：s h o r t e s t p a t ha l g o r i t h m ，d i j k s t r a ，g i s ，n e t w o r ka n a l y s i s i v 武汉理工大学硕士学位论文 1 1 课题背景 第1 章绪论 随着知识经济时代的来临，信息将成为人类社会财富的源泉。事物的时空 特性为人们认识世界提供了更深的广度和宽度。信息科学技术的飞速发展与广 泛应用带动了全社会对空间信息的需求，因此空间信息必将成为国家或全球信 息流中的重要组成部分，并逐渐发展成为当今社会最基本的信息服务之一【1 】。 地理信息系统( g e o g r a p h i c a l i n f o r m a t i o ns y s t e m ，简称g i s ) 是一种在计算 机硬软件支持下，以空间数据库为基础，运用系统工程和信息科学的理论，对 空间数据进行科学管理和综合分析，为规划、决定、管理和研究提供信息的技 术系统。它与其他信息系统的主要区别在于其存储和处理的信息是经过地理编 码的，地理位置及与该位置有关的地物属性信息成为信息检索的重要部分。在 地理信息系统中，现实世界被表达成一系列的地理要素和地理现象，这些地理 特征至少由空间位置参考信息和非位置信息两个组成部分。 地理信息系统的定义是由两部分组成的。一方面，地理信息系统是一门学 科，是描述、存储、分析和输出空间信息的理论和方法的一门新兴的交叉学科； 另一方面，地理信息系统是一个技术系统，是一地理空间数据库( g e o s p a t i a l d a t a b a s e ) 为基础，采用地理模型分析方法，适时提供多种空间的和动态的地 理信息，为地理研究和地理决策服务的计算机技术系统。 地理信息系统具有以下三个方面的特征： 第一，具有采集、管理、分析和输出多种地理信息的能力，具有空阐性和 动态性； 第二，由计算机系统支持进行空间地理数据管理，并由训算机程序模拟常 规的或专门的地理分析方法，作用于空间数据，产生有用信息。 第三，计算机系统的支持是地理信息系统的重要特征，因而使得地理信息 系统能快速、精确、综合地对复杂的地理信息系统进行空间定位和过程动态分 析【”。 网络分析作为g i s 最主要的功能之一，在电子导航、交通旅游、城市规划 武汉理工大学硕士学位论文 以及电力、通讯等各种管网、管线的布局没计中发挥了重要的作用，而网络分 析中最基本和最关键的问题是最短路径问题。它作为许多领域中选择最优问题 的基础，在交通网络分析系统中占有重要地位。从网络模型的角度看，最短路 径分析就是在指定网络中两结点间找条阻碍强度最小的路径。根据阻碍强度 的不同定义，最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其 它的度量，如时间、费用、线路容量等f 3 】o 相应地，最短路径问题就成为最快 路径问题、最低费用问题等。最短路径分析在实际中常用于汽车导航系统以及 各种城市应急系统等( 如1 1 0 匪警、1 1 9 火警以及1 2 0 医疗急救系统) ，还有 各种线路保障问题( 配电网的抢修问题，通讯光缆的最快抢修问题) 4 1 。 有些系统一般要求计算出到出事点地最短路径应该在1 s 3 s 内，在行车过程 中还需要实时计算出车辆前方地行驶路线等。因此最短路径分析不仅应能表征 实际的道路网，而且要有足够快的响应速度。具体对于基于g i s 的城市快速消 防调度系统来说，当火灾发生时，准确确定报警点及着火点位置，自动通知火 场周围有关单位，并快速生成通往火场的最短行车路线是系统中关键性的问题 之一，高效率的实现可以提高消防补救的快速反应能力和整体指挥作战能力垆】。 最短路径问题一直是计算机科学、运筹学、交通工程学、地理信息学等学 科的一个研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有 效结合使得新的最短路径算法不断涌现，各具特色【6 】。由于这些算法主要诞生 于计算机科学及运筹学领域，在算法的设计过程中只考虑了抽象网络的拓扑特 性，力求通过各种新型的计算机数据结构和运筹学方法，从理论上减少算法的 时问复杂度，而忽略了具体的网络可能具有的空间分布特性。而这一点正是描 述交通网络结构的稀疏图与其它描述拓扑结构的平面图的根本区别所在。如何 有效利用交通网络空问分布特性对最短路径算法进行改进，以减少算法的搜索 规模，提高算法运行效率，是本文所要探讨的f 可题。 最短路径问题是交通网络分析中的一个重要问题，也是交通地理信息系统 中( g s - t ) 的一一个研究热点。它是资源分配、路线设计及分析等优化问题的基 础。 国内外大量专家学者对此问题进行过深入研究。最短路径问题可分为单源 最短路径i ；7 题及全源最短路径问题两种【6 】。其中单源最短路径问题更具有普遍 意义，且可为全源最短路径问题提供良好的借鉴方案。单源最短路径问题的算 法有很多种，从早期的基于限制条件的深度优先搜索算法、基于有向无环图的 2 武汉理工大学硕二 j 学位论文 动态规划法、基于邻接矩阵的d i j k s t r a 算法【4 】、到最大相关边法、最大相关点法、 基于邻接表的d i j k s t r a 算法、a + 算法等6 1 。针对不同的网络特征、应用需求及 具体的软硬件环境，各种算法在空间复杂度、时间复杂度、易实现性等方面各 具特色。其中，采用贪心的启发策略的d i j k s t r a 算法是目前己知的理论上最完 善的算法【+ 7 】【”，它以极强的抗差性而得到广泛的普及和应用。单从计算机数据结 构的角度出发单源最短路径也有很多种类型如何结合实际需要选择合适的最佳 抢修路径算法的数据结构及实现方式如何有效利用城市交通网络特征之间的空 间方位关系使之与单纯从计算机数据结构和算法设计出发的交通网络最短路径 算法有效融合以便使算法适用范围更大运行更灵活运行效率更高具有更好的抗 差性由以上分析可知研究交通网络中最短路径算法具有重要的学术和实用意 义。 最短路径问题在运筹学中有着许多重要的意义，也是g i s 网络分析的重要 内容之一，而且网络分析的其它优选问题诸如最小成本计算、位址选择模型、 节点连通性等都和图论中的最短路径问题等价，在方法论上它们有着很大程度 的相似性与一致性。在求解网络图上节点间最短路径的方法中，目前国内外一 致公认的较好算法有迪杰斯特拉( d i j k s t r a ) 2 及弗罗伊德( f l o y d ) 算法。这两种算法 中，网络被抽象为一个图论中定义的有向或无向图，并利用图的节点邻接矩阵 记录点问的关联信息。在进行图的遍历以搜索最短路径时以该矩阵为基础不断 进行目标值的最小性判别，直到获得最后的优化路径。 1 2 最短路径算法研究现状 g i s 因为其强大的数据分析功能、空间分析功能已被广泛应用于各种系统 中与空间信怠有密切关系的各个方丽，各种在实际中的系统如电力系统，光缆 系统涉及到最佳、最短抢修等问题的都可以折合到交通网络中来进行分析，故 而交通网络中最短路径算法可以广泛应用与其它很多的最佳、最短抢修或者报 警系统中去。 最短路径问题是g i s 网络分析功能的应用。最短路径问题可分为单源最短 路径问题及所有节点问最短路径问题，其中单源最短路径更具有普遍意义p j 。 武汉理工大学硕士学位论文 1 1 1 单源最短路径算法分类 根据解决问题的思想不同可将单源最短路径算法分为基于g i s 空间查询语 句( 如：g e o s q l ) 最短路径分析【1 0 1 【l l 】和基于专门设计的功能模块的最短路径 分析两大类【l 。 基于g i s 空间查询语言的最短路径算法 这种方法目前更多的停留在理论研究阶段，如m a x 定义了一套空间查询 语言，对其完备性进行了证明，并举证分析了范围查询、时态查询、最邻近查 询的应用举例，通过形式化定义一种适合于g i s 空间查询的变量，查询代数拓 展了一般查询代数的查洵空间，从而完成最短路径分析功能；提出边和区域的 空间连接预处理和空间约束条件的预处理两种优化方法，从而提出4 种空间路 径查询处理优化策略。尽管针对基于g 1 s 空间发展研究的g e o s q l 不失为一种 处理最短路径的手段，但由于受g i s 数据库技术发展的制约，而实际应用领域 及背景的不同，也使其离商业实际应用还有很长的距离。 基于功能模块思想的最短路径算法 基于功能模块思想的最短路径算法研究是目前研究的热点。针对不同的应 用领域，不同的功能要求产生了各式各样的单源最短路径，算法按照不同的分 类方法、问题特征及实现技术的差异，可分为很多种【1 3 ，比如：d i j k s t r a 算法， 动态规划方法，神经网络法，流体神经网络模拟交通网并结合遗传算法优化参 数法i 1 ，遗传法优化路径参数的d i j k s t r a 法【1 4 】，基于路径模糊信息的最大满意 度路径法1 1 5 1 等。针对不同的背景应用需求及具体的软硬件环境。各种算法在空 间复杂度和时间复杂度的易实现性等方面各具特色。其中，采用贪一t l , 启发搜索 策略的d i j k s t r a 算法，是目前已知理论上最完善的算法【1 0 】，得到了广泛应用。 1 1 2 空间推理中的启发式搜索策略 启发式搜索策略介绍 对于图的搜索主要有以下几种策略 1 1 穷举法 又叫u n i n f o r m e d 或b l i n d 搜索方法，包括深度优先与广度优先两种搜索算 法。这是最基本的两种图搜索算法，它们实质上是对图中路径进行遍历的过程， 单纯应用深度优先或广度搜索策略的最短路径算法，其效率将随着交通网络的 4 武汉理 大学硕士学位论文 扩大迅速降低。此外因为要求在遍历过程中到达目标节点即返回，此类算法不 能保证所得到的路径是最佳路径。 2 1 动态规划法1 1 6 j 这种方法是一种步进式s t e p t a k i n g 搜索方法，要求每一步都必须距目标 更近，即不得在反方向搜索，更适合于栅格数据中的路径搜索。 3 ) 启发式搜索方法i l 又叫i n f o r m e d 搜索方法，是一种首先对最有希望的节点进行搜索的搜索策 略。在计算机搜索算法中，启发式策略指通过一定知识进行搜索，即通过选定 一。种评估函数，在搜索过程中的每一步，寻找评估函数得分值最高的节点作为 下一个搜索扩展节点。启发式搜索策略的主要优点在于可将搜索限定在一定规 模内，寻找最佳路径的算法在实际应用中主要是指这种算法。 启发式策略有很多种，如贪心策略、方向策略、区域策略、层次策略等。 基于启发式贪心策略的最短路径算法包括贪心算法、爬山法、a 4 算法等。其中 贪心算法属于启发式搜索策略中的b f s ( b e s t f i r s ts e a r c h ) 类型，即对节点评估函 数值进行排序，评估值最高者首先扩展。爬山法( h i l lc l i m b i n g ) 是另一种贪心搜 索算法，它将当前至终点的欧氏距离作为扩展路径的启发式策略，对于处理规 则交通网络中的最短路径搜索，具有一定优势。a t 算法是一种在随机产生式系 统中应用比较广泛的启发式搜索算法，它与步进式算法类似，不同点在于当无 法得到至终点的路径时，a 。允许路径的回溯与重新选择。 基于启发式方向策略的最短路径算法，包括空间有效方向的可控参数法1 1 “、 空间方向性优化算法【1 6 l 等。其中空间有效方向的可控参数法，通过设置可调节 系数，使得当有效方向上路径无效时能保证得到可用路径；空间方向性优化算法 是利用两点间直线最短的原理，通过构造二叉树来得到最短路径，其实质是有 损最短路径。 基于启发式区域策略的最短路径算法，包括椭圆限制搜索区域的最短路径 算法 7 】、矩形限制搜索区域的最短路径算法【7 】等。其中椭圆限制搜索区域算法以 待求最短路径的起终节点作为焦点，构造椭圆限制区域，进而在该限制区域内 进行贪心搜索。 基于启发式层次策略的最短路径算法包括层次空间推理的最短路径算法【l “， 层次编码路径视图( h i e r a r c h i c a le n c o d e d p a t hv i e w ，h e p v ) 结构的最短路径算 法( 1 j j 等。其中，层次空间推理算法是根据路段等级将交通网络如分成不同的层 武汉理工大学硕士学位论文 次，尽可能地在高阶层次完成最短路径的选择( 通过过滤掉大量与欲解决问题 无关的细节信息) ，实质上是一种有损最短路径。h e p v 结构的最短路径算法 提出用h e p v 结构层次化平面图，并实例化最短路径，即预先计算和存储最短 路径，来保证实时最短路径查询的响应时间。 上述多种启发式策略结合可有效提高最短路径算法的效率。从严格意义上 讲，这里所描述的各种算法只是搜索策略的逻辑描述，需要结构交通网络的具 体存储结构，才能在计算机中有效实现，从而形成各种实用的最短路径算法， 如基于邻接矩阵的d i j k s t r a 算法和基于邻接表的d i j k s t r a 算法等。 基于贪心策略的d i j k s t r a 最短路径算法 荷兰数学家e w d i j k s t r a ( 1 9 5 9 ) 提出的标号设定法( l a b e ls e t t i n g a l g o r i t h m s ) ，是目前理论最完善，迄今为止应用最广泛的非负权值网络最短路 径算法【”】。标号设定法是一种基于贪心策略的最短路径算法，它要求在路径选 择中的每一步所选择的路径都是目前为止最好的，在局部最优而导致总体最优 的假设下，寻求最佳路径不同的实现方法，构成了d i j k s t r a 算法的庞大家族， 如a r c i n f o 中的n e t w o r k 采用二叉堆优先级队列来实现d i j k s t r a 算法；g e o s t a r 采用快速排序的f i f o 队列来实现d i j k s t r a 算法；采用动态段数据模式的双向比 较追索法的d i j k s t r a 算法；采用最大邻接节点数构造邻接节点矩阵的d i j k s t r a 算 法；采用改进型o p e n c l o s e 表的d i j k s t r a 算法【9 等。 与a + 算法不同，为保证起点到当前结点的路径最优性，d i j k s t r a 算法要求 对所有未访问过的节点进行搜索，包括反方向搜索。与爬山法搜索策略不同， d i j k s t r a 算法以起点至当前节点路径权的和作为贪心选择策略。 针对网络中可能存在负权边的问题，采用不同启发式策略的标号改正法 r l a b e lc o r r e c t i n ga l g o r i t h m s ) 已有研究，标号改正法可以解决存在负权边的网络 最短路径问题，但它不能保证在每次循环中均能发现一条最优路径，其效率一 般比标号设定法低。由于交通网络中不存在负权边，所以交通网络最短路径算 法常指标号设定法，即改进的d i j k s t r a 算法1 1 。 1 3 论文的研究内容 本文对基于交通网络的最短路径分析的各项关键技术进行了研究和验证， 在此基础上实现了一个最短路径分析系统，这些技术包括交通网络的矢量地图 武汉理jf 大学硕l 学位论文 表达、网络拓扑结构的提取和构建、最短路径算法的高效实现等。 在g i s 中多数的网络都是有向带权图，如道路有单双向问题，电流、水流 都有方向( 如果是无向图也可归为有向图的特例) ，且不同的方向都有可能有 不同的权值。将实际的交通网络转化到地图的图层中去时，必须充分考虑到这 些情况，并且应方便于提取弧段和节点的信息，从而构建出正确的网络模型。 另外，g i s 中的数据( 如道路、管网、线路等) 要进行最短路径的计算，就必 须首先将其按节点和边的关系抽象成图的结构，这个在g i s 中称为构建网络的 拓扑关系。本文针对交通网络的地图表示及网络拓扑结构的提取和构建这两项 关键技术提出了实用、高效的解决方案。 由于在实际应用中对最短路径分析的实际处理要求很高，因此论文研究的 关键和主要技术难点也就集中在如何高效率地生成最短路线。本文对最短路径 算法进行了深入分析，在原有算法的基础上对其进行了优化，以提高效率。 1 4 论文的组织结构 论文主要包括五章内容： 第1 章为绪论部分。主要内容包括：课题的背景、交通网络中最短路径算 法的研究现状、课题的研究内容、论文的组织结构。 第2 章为地理信息系统基本概念。主要内容包括：地理信息系统概述、地 理信息系统数据模型、地理信息系统数据的组织和管理、地理信息系统中的网 络分析。 第3 章最短路径分析系统的设计。主要介绍基于城市道路网的最短路径分 析系统的设计思想，主要内容包括：最短路径分析概述，系统流程设计、系统 开发平台的介绍、交通路网的矢量地图表达、网络拓扑结构的提取和构建。 第4 章为最短路径分析系统的实现。主要内容包括最短路径算法模型的分 析、最短路径算法的优化与实现、最短路径分析系统的实现。 第5 章为结论。主要是对以往工作的体会和总结及对下一步工作的展望。 7 璺坚型三盔兰堡主堂垡堕塞 2 1 概述 第2 章地理信息系统基本概念 2 1 1 地理信息系统的概念 地理信息系统( g e o 铲印h i c a li n f o r m a t i o ns y s t e m ，简称g i s ) 是一种将空间位 置信息和属性数据结合在一起的系统，是一种为了获取、存储、检索、分析和 显示空间定位数据而建立的计算机化的数据库管理系统( 1 9 9 8 年，美国国家地 理信息与分析中心定义) 【2 1 。这里的空间定位数据是指采用不同方式的遥感与 非遥感手段所获得的数据，它有多种数据类型，包括地图、遥感、统计数据等， 它们的共同特点都有确定的空间位置。地理信息系统的处理对象是空间实体， 其处理过程正是依据空间实体的空间位置和空间关系进行的。其体系结构可用 图2 - 1 表示。从图中可看出，g i s 空问数据库是g i s 的核心构件之一。 乔景产 “面 、 空间分析i 乔 非空阃分析等 f 输入 输出 用户接口 妙 l 非空间分析等l 图2 - 1g i s 体系结构 地理信息系统的外在表现为计算机软硬件系统其内涵却是由计算机程序和 地理数据组织而成的地理空间信息模型。当具有一定地理学知识的用户使用地 理信息系统时，他所面对的数据不再是毫无意义的，而是把客观世界抽象为模 8 堕坚堡兰叁堂堕主堂篁笙奎 型化的空问数据。用户可以按应用的目的观测这个现实世界模型的各个方面【l 勺 内容，取得自然过程的分析和预测的信息，用于管理和决策，这就是地理信息 系统的意义a 一个逻辑缩小的、高度信息化的地理系统，从视觉、计量和逻辑 上对地理系统在功能上进行模拟，信息流动以及信息流动的结果，完全由计算 机程序的运行和数据的变换来仿真。地理学家可以在地理信息系统支持下提取 地理系统各不同侧面、不同层次的空间和时间特征，也可以快速地模拟自然过 程演变成思维过程的结果，取得地理预测或“实验”的结果，选择优化方案， 用于管理与决策【”。 一个完整的g i s 主要由四个部分构成，即计算机硬件系统、计算机软件系 统、地理数据( 或空间数据) 和系统管理操作人员。其核心部分是计算机系统( 硬 件和软件) ，地理数据反映g i s 地地理内容，而管理人员和用户则决定系统的工 作方式以及信息表示方式【2 l 】。 2 1 2 地理信息系统的发展及现状 地理信息系统的发展历史及现状【2 2 】 g i s 技术起源干2 0 世纪5 0 年代地理学的定量革命，并脱颖于机助制图技 术。当时定量地理学随着统计方法和计算机的介入，正在着手解析空间分析方 面的探讨，并开始了机助制图的研究。g i s 的发展依赖于计算机技术的发展， 尤其是计算机图形学的发展。g i s 萌芽于2 0 世纪6 0 年代初，是由加拿大的 r o g e r 7 0 年代，美国人口调查局为g i s 技术的发展奠定了基础，它们把数学中 的一个分支拓扑学用于人口统计中，并成为地图学的新方法，即用点、线、 多边形来描述地图特征、边界和面积，并使之与现实世界中的空间实体一一对 应。用拓扑学原理建立的数字图形文件中包含了拓扑信息，通过它们可以确定 地图中各特征之间的相邻和连接关系，为用数字和数学方法进行地图研究提供 了时髦的空间分析方法。相对于早期仅仅提供了对空间特征和边界图形跟踪的 “面条”文件来说，这些文件有很大的进步，因为用拓扑结构文件不仅降低了 数字图形文件的大小，同时也促使了地理基础文件二元独立地图编码系统 f g b f d i m e ) 的发展。目前g b f d i m e 系统在拓扑集成地理编码参照t i g e r 中 仍然使用，并是当今许多城市g i s 系统中地理数据库的主要技术。 g 1 s 技术的成熟8 0 年代，伴随工作站和微机的出现，计算机软硬件的成本 迅速降低，功能不断增强，同时随着关系数据库管理系统( r d b m s ) i 拘广泛使用， 9 垫坚堡兰尘堂堡圭堂堡笙壅 使计算机制图系统和g i s 成本也丌始下降。同时，对计算机制图与g i s 的区别 也有了统一的认识，认为除了机助制图功能外，g i s 还具有空间分析功能，它 应该是一个综合系统，可以通过其软件对关系数据库管理系统f r d b m s ) 以及地 理属性数据进行控制，允许对数字图形文件进行解析分析。这样，空间分析功 能便成了g i s 的主要特征。尽管拓扑学在数字地图文件中的应用，为g i s 中空 间数据库的建立莫定了基础，但许多地理空间分析功能仍然只能通过诸如多边 形叠加等图形方法实现，即用传统上数字图形文件的矢量和栅格格式进行。但 由于这两种格式受不同系统的限制，在空问应用上很难形成统一的分析方法， 并存在着一定的数据转换误差，所以最近g i s 应用领域开始引进诸如专家系统 和面向对象等技术方法，以便形成一种统一的空间数据分析格式。当然，这一 问题还有待进一步探讨。销售商对g i s 的发展也起了很大的推动作用，他们最 初只提供计算机制图系统，然后加了空间分析模块，使其软件系统具有g i s 功 能，这种转换在桌面制图软件包中尤为明显。目前，仅美国从事g i s 产业的公 司约有1 6 0 多个，他们提供包括数字化、数据转换和专业应用方面的不同服务。 其中环境系统研究所( e r s i ) 和i n t e r g r a p h 公司就占了联邦和商业部门5 0 的 g i s 市场。另外，前国防系统的一些销售商也瞄准了g i s 技术，并开始向这一 市场转变。这些行为有力地推动了g i s 技术由机助制图向社会普及的发展。 我国g i s 的发展 我国g i s 的发展相对较晚，主要经历了四个阶段： 准备阶段：1 9 7 8 年到1 9 8 0 年，正式提出倡议，开始组建队伍、组织个别 实验研究。 起步阶段：1 9 8 1 年到1 9 8 5 年，理论探索和区域性实验研究。并在此基础 上制定国家地理信息系统规范。从1 9 8 4 年开始，国家测绘局测绘科学研究所着 手组建中国国土基础信息系统：1 9 8 5 年国家资源与环境信息系统实验室成立。 发展阶段：1 9 8 6 到1 9 9 5 年，地理信息系统的研究被列入我国“七五”攻 关课题，并且作为一个全国性的研究领域，已逐步和国民经济建设相结合，并 取得了重要进展和实际应用效益。在这个阶段，形成了一个比较系统的研究计 划：一方面，以研究资源与环境信息系统的国家规范和标准、省、市、县级的 规范和区域性的规范为主体，解决信息共享和系统兼容的问题；另一方面开展 全国性的自然资源与环境、国土和水土保持信息系统的建立和应用模式研究， 开展结合水土保持、洪水预警和救灾对策、防护林生态和城市环境等方面区域 1 0 武汉理工大学硕士学位论文 信息系统研究：第三方面是研制和发展软件系统和专家系统，从技术上支撑上 述研究领域的开拓与发展；建成了一批数据库，如林业部研制的全国森林资源 数掘库；开发了一系列空阎信息处理和制图软件，如南京大学的微机制图系统 及地图绘制软件包、中国科学院地理研究所的地理网络法软件系统；建立了一 些具有分析和应用深度的地理模型和基础性的专家系统，如北京大学的地理专 家系统、中国科学院综考会的资源开发模型工具库系统、武汉测绘学院的基于 g i s 的专题地图设计专家系统、华东师范大学的地理应用程序软件包等；完成 了一批综合性、区域性和专题性的信息系统，如中国科学院的中国国土基础信 息系统、黄土高原水土流失信息系统、黄河下游洪水险情预警信息系统、黄河 三角洲区域信息系统、洞庭湖堤境区域信息系统、三北、京津唐地区生态信息 系统，高校遥感联合中心的三川河流域区域治理与开发信息系统；g i s 教学科 研和国际合作都得到了很大的发展，逐步建立了不同层次、不同规模的研究中 心和实验室，如武汉大学的测绘遥感信息工程，国家重点实验室的建立等。 产业化阶段：从1 9 9 6 年到现在。组建了很多专业的g i s 软件和产业化公司。 2 1 3 地理信息系统的应用领域 从当前国内外g i s 技术研究和应用情况看，国内外对地理信息系统的研究 已经进入了广泛实际应用阶段，如城市交通管理、消防信息管理、城市地下管 道管理等。地理信息系统( g i s ) 自诞生至今，其应用领域己由自动制图、资源管 理、土地利用发展到与地理位置相关的邮电通讯、水利电力、金融保险、地质 矿产、交通运输等多个领域。目前交通行业的不少领导、工程管理人员、研究 人员、技术人员己将g i s 运用到交通行业的许多方面，尤其是在交通工程领域， 采用g i s 技术和方法研究交通规划、工程管理、交通运输及其相关的问题，与 其他传统的方法相比，具有无可比拟的优点，如快速灵活性、客观定量性、强 大的分析模拟能力等。越来越多的业内人士开始接受并运用这一先进的、科学 的研究手段1 2 3 j 。 2 2 地理信息系统数据模型 地理信息是用来表示地理实体特征的数据，是g i s 的研究、作用对象。地 理实体具有三个基本特征【2 1 ： 1 1 武汉理工大学硕士学位论文 属性特征：用来描述地理实体的特性，如地理实体的类别、等级、数量 和名称等。 空问特征：用来描述地理实体的地理位置以及空间相互关系，又称几何 特征和拓扑特征，前者如界桩的经纬度，后者如中国和印度接壤。 时间特征：用来描述实体随时问的变化，例如人口密度的逐年变化。 目前地理实体的时间特征的应用较少，多考虑其属性特征与空间特征的结 合。因此现在g i s 系统常用的表示地理实体特征的数据主要有两类，即：空间 数据和属性数据。 2 2 。1 空间数据模型 空间数据表示地理实体的空间位置或现在所处的地理位置，表达了物体地 理实体的几何定位特征，一般以坐标数据来表示，如城市和道路交叉口在交通 网络中的空间位置等：属性数据表达了地理实体的与几何位置无关的属性特征， 如交通网络中的路段的路线编号、等级、里程、路段交通量等表示路段的属性 特征。 地理空间数据是指以地球表面空间位置为参照的自然、社会和人文景观数 据，可以是图形、图像、文字、表格和数字等，由系统的建立者通过数字化仪、 扫描仪、键盘、磁带机或其它通讯系统输入g i s ，是g i s 所表达的现实世界经 过模型抽象的实质性内容。空间数据结构是指地理实体的空间排列方式和相互 关系的抽象描述。g i s 空间数据结构主要有两种类型：矢量结构和栅格结构。 目前，主要有两类用于空间数据处理的通用数据模型：基于实体的模型 f e n t i t y b a s e dm o d e l ) ：f l l 基于域的模型( f i e l d b a s e dm o d e l ) 。前者将空间信息表示 成离散的、可标识的空间实体。后者处理的是空间分布信息，每种空间分布都 可以表示成一个从空间框架( s p a t i a lf r a m e w o r k ) 至l j 属性域( a t t r i b u t ed o m a i n ) 的函 数，地形高程、降雨量和温度的分布就属于这种模型。在进行计算机图形处理 种，这两种模型分别转化为栅格( r a s t e r ) 模型和矢量( v e c t o r ) 模型【2 2 】【2 3 】1 3 8 1 1 3 9 1 。 栅格模型 栅格模型将空间分成一系列的单元，每个单元代表有限但确定的地球表面。 单元可以具有任何几何形状，只要能组合出表达研究区域的面即可。虽然栅格 单元有许多形状，如三角形、六角形，但通常采用固定大小的正方形。正方形 的栅格单元称为网格单元，空间事物就按其在网格种的行、列和取值来表示a 武汉理工大学硕士学位论文 网格单元的大小代表了栅格型地图( 空问) 数据库的分辨率。这些离散的数据 网格具有叠加方便、迅速的特点，所以常被用来作为空间物体的背景图。 在基于格网或栅格的系统中，有两种基本方法可以赋予实体( 对象) 属性 数据。最简单的一种是为每一个网格赋一个数值代表属性( 如土地覆盖) ，这 样，根据属性值的分布就可以表示实体的位噩。例如。如果用1 0 代表水，作为 x 或列方向和y 或行方向的第一个数，左上网格单元就是地图表面代表水的位 置。每个网格单元在所给地图中只能有个属性值。还有另- - , e e ，就是第种 的扩展，它把网格单元与数据库管理系统互相连接，一个网格单元就可以有多 种属性。这种方法的使用日益，不仅由于可以减少必须存储的数据量，而且也 可以很容易地同其他数据结构建立关联，在数据库管理系统下进行数据的存储、 查询与处理。图2 2 描述的是基本栅格数据的表达。 图2 - 2 基本栅格图形数据的表达 栅格模型的突出优点是，它可以直接利用遥感、数字摄影测量、扫描等方 式获取栅格形式的数据，且数据结构简单；空间数据的叠置和组合十分方便； 各类空间分析都很容易实现；数学模拟方便。其缺点是，随着精度的增大，数 据量不断增大，从而对设备的存储空间要求过高，且查询速度较慢。图形数据 量大：用大像元减少数据量时，图形精度和信息量受到损失；地图输出较差： 难以建立网络连接关系；投影变换十分耗时。栅格数据结构有利于多边形的叠 置、空间均值处理和空间分析，但输出的专题地图既不美观也不够精确。采用 陔类方法，难于实现空间实体的旋转及坐标的变换操作，对空间实体的识别和 武汉理= 人学硕士学位论文 标识操作较麻烦。 矢量模型 矢量模型假定地理空间是连续的，而不是量化为互相独立的小栅格。点用 独立的空间坐标对表示，线用一系列坐标对表示，面是由首尾相连的线构成的 多边形。如图2 3 描述了基本矢量图形数据的表达。 ( x a ) 谯 雕域 图2 。3 基本矢量图形的数据表达 矢量模型对地图上出现的多维实体更具有表达力，实体数据和属性数据分 别存储在不同文件中一在数据库管理系统中，再用某种方法把两者连接起来。 这是用简单的图例对表达实体的扩展，使得矢量模型更加图形化，更能形象地 表达地球表面。在栅格模型中，是基于栅格位置来存储属性数据和定位空间， 然而矢量模型地表示方法却完成不同，实体数据独立存储在一个地方，通过一 定的关系与其独立地属性数据相连。 在矢量模型中，线由两个或多个坐标对构成，与这条线相关的属性数据存 储在另一个文件中。一条直线用两个坐标对足以表示其空间位置和方向，复杂 一些的线由许多线段表示，每个线段由两个坐标对确定。对于复杂的线，必须 增加线段以表示线段方向的不断变化，线段越短，表示的复杂度也越准确。虽 然矢量模型更能精确表达实体的空间位置，但并不绝对准确，它仍然是地理位 置的抽象。 与栅格模型的数据结构相比，矢量模型的数据结构是一种更加紧密的数据 结构。所需的存储空间较小，精度不受限制，原始地图的精度既是矢量化地图 1 4 1厂 夕q 武汉理工大学硕士学位论文 的精度a 定位明显，属性隐含，容易定义和操作单个空间实体。矢量数据结构 能够进行有效的拓扑编码，便于进行空间拓扑分析。在进行