（计算机软件与理论专业论文）基于gis空间分布特征的dijkstra最短路径算法研究.pdf

重庆大学硕士学位论文中文摘要 摘要 随着计算机的普及以及地理信息科学的发展，g i s 因其强大的功能得到日益广 泛和深入的应用。g i s 网络分析是g i s 的研究热点和难点，而最短路径问题是g i s 网络分析中最基本和最关键的问题，在许多方面具有直接的应用价值，人们对最 短径算法的深入研究也从未间断过。经典的图论与不断发展完善的计算机数据结 构及算法的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间 复杂度、易实现性及应用范围等方面各具特色。 d i j k s t r a 算法是目前多数系统解决最短路径问题的理论基础。d i j k s t r a g 法的优 点是程序设计简单、通用性强。缺点是该算法不是专门针对特定两点的，而在g i s 的最短路径寻找中，往往是寻找两个特定点之间的最短或近似最短路径，因而此 算法在这方面效率较低；另外，传统的d i j k s t m - 算法采用邻接矩阵数据结构，占用 空间十分巨大，严重浪费计算机的资源，很不适合g i s 中结点量巨大的实际情况。 因此，在g i s 的实际应用中。针对g i s 应用的实际情况对基于d i j k s t r a 的最短路径算 法进行改进是完全有必要的。 基于d i j k s t r a 算法的理论基础并针对g i s 路径分析的特点，已有的应用系统对 d i j k s t r a 算法采用了很多不同的改进方法。鉴于g i s 的广泛应用和d i j k s t r a 算法在该 应用中的运行效率的重要性，本文通过对d i j k s t r a 最短路径算法的分析，充分利用 g i s 中空间分布特征，针对g i s 中搜索两个特定点的最短路径的应用，从数据结构、 搜索技术及算法本身对d i j k s t r a 最短路径搜索算法提出了优化和改进，使之更加适 合于在g i s 两个特定点之间的最短路径查找。本文主要研究工作包括： 研究了经典d i j k s t r a 算法的主要思想及其实现；讨论了平面图搜索策略，从问 题类型、网络类型和实现方法三个方面对最短路径算法进行系统分类； 研究了g i s 中的数据结构；分析了各种最短路径算法思想及其应用的数据结构 以及各种数据结构的特性； 对最短路径算法在实时化和并行化方面的发展进行了讨论； 研究了g i s 空间分布特征；结合g i s 公路交通中查找最短路径的具体情况， 分析了传统最短路径算法在这种特定应用中的不足，提出了一个充分利用g i s 中 空间分布特征的改进算法，对传统d i j k s t r a 算法的路径搜索提出了一种新的搜索思 想，即方向优先搜索。最后编程实现了该改进算法，通过实验验证了该算法的有 效性。 关键词：最短路径算法，g i s ，d i j k s t r a ，空间分布，路径搜索，数据结构 重庆大学硕士学位论文英文摘要 a b s t r a c t w i t ht h e p r e v a l e n c e o f c o m p u t e r a n dt h e d e v e l o p m e n t o f g e o g r a p h y i n f o r m a t i o n , g i sw a sa p p l i e dt h o r o u g h ya n dw i d e l y g i sn e t w o r kp a t ha n a l y s i si st h e h o t s p o to fg i sr e s e a r c h , a n dt h es h o r t e s tp a t hi st h em o s tb a s i ca n dt h em o s tp i v o t a l p r o b l e m ，i th a sm a n yd i r e c t l ya p p l i c a t i o n ，s ot h er e s e a r c ho ni tw a sn e v e ri n t e r r u p t e d t h e e f f e c t i v ec o m b i n eo fc l a s s i c a lg r a p ht h e o r y a v i t hc o m p u t e rd a t as t r u c t u r ea n da l g o r i t h m w h i c hd e v e l o pp e r f e c t l yh a su n c e a s i n 舀ym a d en e ws h o r t e s tp a t ha l g o r i t h m se m e r g e s t h e yh a v ee a c hc h a r a c t e r i s t i ci nr e s p e c to fs p a c ec o m p l e x i t y , t i m ec o m p l e x i t y , e a s y r e a l i z a t i o na n da p p l y i n gr a n g e d i j k s t r aa l g o r i t h mi st h eb a s i ct h e o r yo fm o s ts y s t e m ss o l v i n gt h es h o r t e s tp a t h p r o b l e mp r e s e n t ，t h ee x c e l l e n c eo fd i j s k t r aa l g o r i t h mi se a s yp r o g r a m m i n ga n ds t r o n g c o m p a t i b i l i t y b u ti ti sn o ta i m i n ga tt w os p o t s ，a n di nt h ep r o c e s so ff m d i n gs h o r t e s t p a t hi ng i sw eu s u a l l yw a n tt of i n dt h es h o r t e s tp a t ho ft w os p e c i a ls p o t s ，s ot h e e f f i c e n c yo ft h i sa l g o r i t h mi sl o w i na d d i t i o nt r a d i t i o n a ld i j k s t r aa l g o r i t h ma d o p tt h e a d j a c e n c ym a t r i xd a t as t r u c t u r ew h i c ho c u p y se n 0 1 t n o u ss p a c ea n dw a s t a st h ec o m p u t e r r e s o u r c eg r a v e l ys oi ti su n s u i t a b l ef o ri m m e n s e i t yn o d ea m o u n t so fg i s t h e r e f o r e i n t h ea c t u a la p p l i c a t i o no fg i s ，i t sn e c e s s a r yt oi m p r o v et h es h o r t e s tp a t ha l g o r i t h m b a s e do nd i j k s t r ad i r e c tt op r a c t i c a ls i t u a t i o n e x s i t i n ga p p l i c a t i o ns y s t e ma d o p t sal o to fd i f f e r e n tm e h o dt oi m p r o v ed i j k s t r a a l g o r i t h mb u s e do nt h ed i j k s t r aa l g o r i t h mt h e o r ya n dt h ef e a t u r eo fg i sp a t ha n a l y s i s r e s p e c t i n gt h ew i d e l yu s eo fg i sa n dt h ei m p o r t a n c eo fr u n n i n ge f f i c e n c yo fd i j k s t r a a l g o r i t h mt h i st h e s i s ，b ya n a l y z i n gt h ed i j k s t r as h o r t e s tp a t ha l g o r i t h m ，f u l l yu t i l i z e s p e c i a ld i s t r i b u t i o nc h a r a c t e r i s t i ci ng i s ，a p p o i n tt ot h ea p p l i c a c t i o no ff i n d i n gt h e s h o r t e s tp a t hb e t w e e nt w os p o ti ng i s ，a n da p p l yo p t i m i z a t i o na n di m p r o v e m e n tf o r d i j k s t r as h o r t e s tp a t hs e a r c h i n ga l g o r i t h mf r o mt h ed a t as t r u c t u r e ，s e a r c ht e c h n i q u ea n d a l g o r i t h mi t s e l f , a n dt h e nt h i sp a p e rm a k e si tm o r es u i t a b l et of i n ds h o r t e s tp a t hb e t w e e n s p e c i a ls p o ti ng i s t h em a i ns t u d yo f t h i sp a p e ri n c l u d e s ： r e s e a r c hm a i ni d e aa n dr e a l z i t i o no fc l a s s i c a ld i j k s t r aa l g o r i t h m d i s c u s s s e a r c hp o l i c yo fi c h n o g r a p h y c l a s s i f yt h es h o r t e s tp a t ha l g o r i t h ms y s m e t i c l yf r o m t h r e ea s p e c t si n c l u d i n gp r o b l e mt y p e ，n e t w o r kt y p ea n dr e a l i z a t i o nm e t h o d r e s e a r c ht h ed a t as t r u c t u r ei ng i s a n a l y s ev a r i o u ss h o r t e s tp a t ha l g o r i t h m i d e a , d a t as t r u c t u r ei tu s e sa n d 也ec h a r a c t e r i s t i co f v a r i o u sd a t as t r u c t u r e n 茎壅奎兰堡主兰垡笙奎 墨茎塑茎 d i s c u s st h ed e v e l o p m e n to f t h es h o r t e s tp a t ha l g o r i t h mi na s p e c to f r e a l t i m e a n dp a r a l l e y s t u d yt h e g i s s p e c i a l d i s t r i b u t i o nf e a t u r e c o n s i d e r i n gt h e c o n c r e t e c o n d i t i o n so ff i n d i n gt h es h o r t e s tp a t hi ng i sr o a dt r a f f i c ，t h i sp a p e ra n a l y s et h e d e f i c i e n c yo f t r a d i t i o n a ls h o r t e s tp a t ha l g o r i t h ma p p l y i n gi nt h es p e c i a la s p e c ta n d t h e np u tf o r w a r dai m p r o v e da l g o r i t h mw h i c hu s e sg i ss p e c i a ld i s t r i b u t i o nf e a t u r e 如1 1 va n dt a k ean e ws e a r c hm e t h o d a tl a s t ，r e a l i z em i si m p r o v e da l g o r i t h m t h r o u g hp r o g r a m m i n ga n dv e r i f yv a l i d i t yo f t h ea l g o r i t h mt h r o u g he x p e r i m e n t k e y w o r d s ：t h es h o r t e s tp a t ha l g o r i t h m ，g i s ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ) ， d i j k s t r a , s p a i c a ld i s t r i b u t i o n , p a t hs e a r c h ，d a t as t r u c t u r e 1 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位做作者签名犯挎纷 签字日期加夕年牛月万日 学位论文版权使用授权书 本学位论文作者完全了解重庆太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重鏖太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( x ) 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：庑掳竣 签字日期：勾口j 7 年年月疹日 导师签名：刁瓜分 签字日期：2 叼年午月巧日 重庆大学硕士学位论文1 绪论 1 绪论 最短路径问题一直是一个研究热点，在计算机科学、运筹学、地理信息科学 等学科中都起着极重要的作用。g i s 的出现是信息技术及其应用发展到一定程度的 必然产物。在各类信息管理系统中，g i s 是目前发展最快的系统之一，网络分析是 g i s 空间分析的一个非常重要的方面，而最短路径问题是g i s 网络分析中的最基本 最关键的问题，因此对应用于g i s 的最短路径算法进行研究是有必要的。 1 1 课题研究背景 随着计算机的普及以及地理信息科学的发展，g i s 因其强大的功能得到日益广 泛和深入的应用。网络分析作为g i s 最主要的功能之一，是地理信息系统的重要组 成部分，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的 布局设计中发挥了重要的作用，是研究的一个热点和难点。而最短路径问题是g i s 网络分析最基本最关键的问题，在交通网络结构的分析、交通运输线路的选择、 通讯线路的建造与维护、运输货流的最小成本分析、城市公共交通网络的规划等 方面，都有直接应用的价值。最短路径不仅仅指一般地理意义上的距离最短，还 可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就 成为最快路径问题、最低费用问题等。最短路径算法不仅是资源分配、路线设计 及分析等优化问题的基础，交通网络分析中的其它问题，如最可靠路径问题、最 大容量路径问题、各种各样的路径导航问题也都可以归并到最短路径问题类型中 【2 1 。其实，无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短 路径算法。对于最短径算法的相关研究层出不穷，其各种最短路径算法的分析评 述可参见文献“。 目前在g i s 应用领域，对最短路径搜索问题的研究和应用较多，其中最短路径 搜索算法的效率问题是普遍关注和在实际应用中迫切需要解决的问题。所采用的 算法主要是来源于图论领域中的称为d i j k s t m 的算法，该算法运行的结果是某一顶 点到其它所有顶点的最短路径。d i j k s t r a _ 舅l 法由于适应网络拓扑的变化，性能稳定， 因而在计算机网络拓扑路径选择以及g i s 中得到广泛的应用。例如，从美国发展起 来的一项重要的移动服务手机位置服务( m o b i 2 1 e g i s ) ，方便地帮助用户查找位置信 息，做到问路不求人，在“问路不求人”功能模块寻找最短路径采用的就是d i j k s t r a 算法【9 】。d i j k s t r a 算法的优点还有程序设计简单，通用性强。但将传统d i j k s t r a 算法 直接应用于g i s 中的最短路径查找是不适当的，首先d i j k s t r a 算法不是针对特定两点 的，而在g i s 的最短路径寻找中，往往是需要查找两个特定点之间的最短或近似最 重庆大学硕士学位论文l 绪论 短路径，因而效率较低；h n 2 _ 传统d i i k s 仃算法中采用邻接矩阵数据结构，占用空间 十分巨大，严重浪费计算机的资源，很不适合g i s 中结点量巨大的实际情况，最重 要的是，传统d i j k s t r a 算法是一个解决平面中源点到其它所有点的最短路径的通用 算法，运用中没有去考虑处理对象的空间分布特征。因此，在通用性和完备性的 意义上，d i j k s t r a s g 法无疑是非常优秀的，但基于g i s 空间分布特征和g i s 中最短路 径查找的具体情况，其在算法本身的改进及效率的的进一步提高是完全有必要的。 1 2 国内外研究现状 1 。2 ，lg l s 技术应用研究现状 地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，g i s ) 是能够收集、管理、查询、 分析、操作以及表现与地理相关的数据信息的计算机信息系统，能够为分析、决 策提供重要的支持平台。它广泛地应用于地学、资源管理、土地规划、环境监测、 防灾减灾、电力行业、交通管理、城市规划、科研、教育和国防等领域，在我国 星民经济建设中发挥着越来越重要的作用。 目前世界上常用的g i s 软件已达4 0 0 多种。它们大小不一，风格各异。国外 较著名的有a r c i n f o ，g e n a m a p ，m g e 等；国内较著名的有m a p g i s ，g e o s t a r 和c r r y s t a r 等。虽然g i s 起步晚，但它发展快，目前已成功地应用到一百多个 领域。 尽管现存的地理信息系统软件很多，但对于它的研究应用，归纳概括起来有 两种情况。一是利用g i s 系统来处理用户的数据：二是在g i s 的基础上，利用它 的开发函数库二次开发出用户的专用的地理信息系统软件。目前已成功地应用到 了包括资源管理、自动制图、设施管理、城市和区域的规划、人口和商业管理、 交通运输、石油和天然气、教育、军事等九大类别的一百多个领域。在美国及发 达国家，地理信息系统的应用遍及环境保护、资源保护、灾害预测、投资评价、 城市规划建设、政府管理等众多领域。近年来，随我国经济建设的迅速发展，也 加速了地理信息系统应用的进程，在城市规划管理、交通运输、测绘、环保、农 业、制图等领域发挥了重要的作用，取得了良好的经济效益和社会效益。 由于g i s 是“关系到国家安全的战略性技术”，因此开发拥有自主知识产权的 国产g i s 系统平台，研究和掌握g i s 中的前沿关键技术，对我国g i s 的发展和应 用有着菲常重要的意义。 1 2 ，2 最短路径算法研究现状 最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究 热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完 善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在 2 重庆大学硕士学位论文1 绪论 空问复杂度、时问复杂度、易实现性及应用范围等方面各具特色。现在的研究热 点，一是针对实际应用中网络特征优化运行结构，在统一时间复杂度的基础上尽 可能地提高算法的运行效率；二是对网络特征进行限制，如要求网络中的边具有 整数权值等，以便采用基数堆等数据结构设计算法的运行结构；三是采用有损算 法，如限制范围搜索、限定方向搜索及限制几何层次递归搜索；四是采用拓扑层 次编码路径视图，对最短路径进行部分实例化编码存储；五是采用并行算法，为 并行计算服务。 据统计，目前提出的此类最短路径的算法大约有1 7 种。e b e n j a m i nz h a n 等人 对其中的1 5 种进行了测试，结果显示有3 种效果比较好，它们分别是：t q q ( g r a p h g r o w t hw i t h t w oq u e u e s ) 、d k a ( t h ed i j k s t r a s a l g o r i t h mi m p l e m e n t e dw i t h a p p r o x i m a t eb u c k e t s ) 以及d k d ( t h ed i j k s t r a sa l g o r i t h mi m p l e m e n t e dw i t hd o u b l e b u c k e t s ) 。其中t q q 算法的基础是图增长论，用两个f i f o 队列实现了一个双端 队列结构来支持搜索过程，较适合于计算单源点到其他所有点的最短距离。后两 种算法则是基于d i j k s t r a 算法，采用桶结构明显提高了永久标记点的搜索速度。 1 2 3 最短路径算法在g i s 中的研究、应用现状 路径寻优是g i s 网络分析中的一个基本问题。目前基于g i s 的最短路径搜索 算法研究很多，但用得最广泛的还是来源于图论领域中的称为d i j k s t r a 的算法，该 算法运行的结果是某一顶点到其他所有顶点的最短路径。算法的优点是程序设计 简单，通用性强；缺点是算法不是针对特定两点的，因而效率较低；加之邻接矩 阵占用空间十分巨大，不适合g i s 中海量数据的实际情况，严重浪费计算机的资 源【l 们。这方面的改进研究是地理信息系统领域一个非常有实际意义的问题。图论 中的最优路径算法是针对所有的实际问题而抽象出的最一般的模型。两点间的路 径既可以表示长度，也可以表示工程时间、工程费用等各种属性，因此，在通用 性和完备性的意义上，d i j k s t r a 算法无疑是非常优秀的。然而，针对某些特殊的问 题，无疑应该有更加高效的算法。因此针对g i s 应用中的具体情况对d i j k s h a 算 法进行改进是有必要的，也是一个研究的热点。 1 3 论文的研究目标、内容和技术路线 1 3 1 研究目标 本文研究的问题为基于d i j k s t r a 算法豹最短路径算法分析及它在g i s 网络分析 中的应用和改进，主要是要解决基于g i s 空间分布特征的d i j k s t r a 算法的改进问题。 本文将对现有的一些d i j k s t r a 算法的改进方法进行学习、比较和总结，然后根据 g i s 中最短路径查找的实际情况，试图从网络结构的拓扑表示( 即数据结构) 以及 d i j k s t r a 算法中快速搜索技术的实现入手，找出一种在g i s 应用中能有更高效率的 重庆大学硕士学位论文1 绪论 d i j k s t r a 改进算法，并最终实现该改进算法的代码编制和运行。 1 3 2 主要研究内容 拟研究的问题如： 研究经典d i j k s t r a 算法的主要思想及其实现；讨论了平面图搜索策略，从问题 类型、网络类型和实现方法3 方面对最短路径算法进行系统分类： 研究g i s 中的数据结构：分析各种最短路径算法思想及其应用的数据结构以及 各种数据结构的特性； 对最短路径算法在实时化和并行化方面的发展进行了讨论； 研究g i s 空间分布特征；结合g i s 公路交通中查找最短路径的具体情况，分 析传统最短路径算法在这种特定应用中的不足，提出一个充分利用了g i s 中空间 分布特征的改进算法，对传统d i j k s t r a 算法的路径搜索提出一种新的搜索思想，即 方向优先搜索。最后编程实现该改进算法。 1 3 3 技术路线 广泛收集相关资料，学习现有的最短路径算法的改进方案。 研究各种最短路径算法的基本思想，搞清楚其求解原理，熟练掌握最短路径算 法中相关数据结构的特性。学习研究g i s 的空间分布特征。 对目前应用于d i j k s t r a 算法的数据结构和搜索技术进行学习研究，在此基础上 努力找出在g i s 这种特定的应用环境中更高效率的实现方法。 以d e l p h i 作为开发工具实现改进最短路径算法的代码编制，完成算法的实现。 1 4 本章小结 本章首先介绍了本文的研究背景，阐述了最短路径算法和g i s 应用目前的研 究现状，指出d i j k s t r a 的最短路径算法在g i s 最短路径查找应用中进行改进的必要 性。最后提出本文的研究目标、内容和技术路线。 4 重庆大学硕士学位论文 2g i s 基本理论介绍 2g i s 基本理论介绍 2 1g i s 概述 2 1 1g i s 的概念 电子计算机的兴起极大地推动了地学的发展，人们开始有可能用电子计算机 来收集、存储和处理各种与空间和地理分布有关的图形和属性数据，并希望通过 计算机对数据的分析来直接为管理和决策服务。这种与g i s 的结合即地学与计算 机科学的结合就导致了地理信息科学的问世。 地理信息系统，简称g i s ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ) 。顾名思义，地理信 息系统是处理地理信息的系统。地理信息是指直接或间接与地球上的空间位置有 关的信息，又常称为空间信息。一般来说，g i s 可定义为：”用于采集、存储、管 理、处理、检索、分析和表达地理空间数据的计算机系统，是分析和处理海量地 理数据的通用技术”。从g i s 系统应用角度可进一步定义为：”g i s 由计算机系统、 地理数据和用户组成，通过对地理数据的集成、存储、检索、操作和分析，生成 并输出各种地理信息，从而为土地利用、资源评价与管理、环境监测、交通运输、 经济建设、城市规划以及政府部门行政管理提供新的知识，为工程设计和规划、 管理决策服务。 2 1 2g i s 的发展简史及应用现状 g i s 发展简史 人类生活在地球上，8 0 以上的信息与地球上的空间位置有关。g i s 的出现是 信息技术及其应用发展到一定程度的必然产物。从发展现状和趋势来看，地理信 息系统技术是一门综合性的技术，它的发展是与地理学、地图学、摄影测量学、 遥感技术、数学和统计科学、信息技术等有关学科的发展分不开的。g i s 的发展可 分为四个阶段：第一个阶段是初始发展阶段，2 0 世纪6 0 年代世界上第一个g i s 系统由加拿大测量学家r e t o m l i s o n 提出并建立，主要用于自然资源的管理和规 划；第二个阶段是发展巩固阶段，2 0 世纪7 0 年代由于计算机硬件和软件技术的飞 速发展，尤其是大容量存储设备的使用，促进了g i s 朝实用的方向发展，不同专 题、不同规模、不同类型的各具特色的地理信息系统在世界各地纷纷付诸研制， 如美国、英国、德国、瑞典和日本等国对g i s 的研究都投入了大量的人力、物力 和财力；第三个阶段是推广应用阶段，2 0 世纪8 0 年代，g i s 逐步走向成熟，并在 全世界范围内全面推广，应用领域不断扩大，并与卫星遥感技术结合，开始应用 于全球性的问题，这个阶段涌现出一大批g i s 软件，如a r c i n f 0 ，g e n a m a p ， s p a n s ，m a p i n f o ，e r d a s ，m i c r o s t a t i o n 等：第四个阶段是蓬勃发展阶段，2 0 5 重庆大学硕士学位论文2 g i s 基本理论介绍 世纪9 0 年代，随着地理信息产品的建立和数字化信息产品在全世界的普及，g i s 成为确定性的产业，并逐渐渗透到各行各业，成为人们生活、学习和工作不可缺 少的工具和助手。 地理信息系统的研制与应用在我国起步较晚，虽然历史较短，但发展势头迅 猛。我国g i s 的发展可分为三个阶段。第一阶段从1 9 7 0 年到1 9 8 0 年，为准备阶 段，主要经历了提出倡议、组建队伍、培训人才、组织个别实验研究等阶段。机 械制图和遥感应用，为g i s 的研制和应用做了技术和理论上的准备。第二阶段从 1 9 8 1 年到1 9 8 5 年，为起步阶段，完成了技术引进、数据规范和标准的研究、空间 数据库的建立、数据处理和分析算法及应用软件的开发等环节，对g i s 进行了理 论探索和区域性的实验研究。第三个阶段从1 9 8 6 年到现在，为初步发展阶段，我 国g i s 的研究和应用进入有组织、有计划、有目标的阶段，逐步建立了不同层次、 不同规模的组织机构、研究中心和实验室。g i s 研究逐步与国民经济建设和社会生 活需求相结合，并取得了重要进展和实际应用效益。主要表现在四个方面： 1 1 制定了国家地理信息系统规范，解决信息共享和系统兼容问题，为全国地理信 息系统的建立做准备。 2 1 应用型g i s 发展迅速。 3 ) 在引进的基础上扩充和研制了一批软件。 4 ) 开始出版有关地理信息系统理论、技术和应用等方面的书籍，设立了地理信息 系统专业。培养了大批人才，并积极开展国际合作，参与全球性地理信息系统的 讨论和实验。 g i s 应用现状 2 0 世纪8 0 年代以前，国外城市交通资料主要通过关系型数据库来管理属性资 料，空间数据则是以c a d 图形式存放与管理，随着计算机软硬件迅速发展，特别 是大容量存贮功能磁盘的使用，为地理空间资料的录入、存贮、检索、输出提供 了强有力的手段，使g i s 朝实用方向迅速发展。美国、加拿大、英国、西德、瑞 典、日本等发达国家先后建立了许多不同专题、不同规模、不同类型的各具特色 的地理信息系统用以管理城市的交通规划资料并加以应用。 2 0 世纪8 0 年代，g i s 软件可以很好地与关系数据库结合，可以通过o d b c 连接m s a e c e s s 、s q ls e r v e r 、o r a c l e 、d b 2 ，可进行空间数据和属性数据的统一存 储，使数据转换和建库同步完成。随着g i s 与卫星遥感技术的结合，g i s 已用于 全球变化的资料的采集、研究与监测。 与国外的发展相类似，国内的城市交通规划资料的管理主要依靠有e x e c l ， a u t o c a d 等软件。g i s 应用技术在我国的应用起步较晚，从8 0 年代开始，国内开 始使用国外成熟的g i s 软件( 如m a p l n f o 公司的m a p l n f o ，e r s i 公司的a r c h i n f o ) 6 重庆大学硕士学位论文2 g i s 基本理论介绍 来管理城市交通规划资料，同时国内开始开发自己的g i s 软件，如m a p g i s ， g c n s t a r 和c i t y s t a r 等。 2 1 3 g i s 的组成 g i s 的应用系统由五个主要部分构成，即硬件、软件、数据、人员和方法。 硬件 硬件是指操作g i s 所需的一切计算机资源。目前的g i s 软件可以在很多类型 的硬件上运行，从中央计算机服务器到桌面计算机，从单机到网络环境。一个典 型的g i s 硬件系统除计算机外，还包括数字化仪、扫描仪、绘图仪、磁带机等外 部设备。根据硬件配置规模的不同可分为简单型、基本型、网络型。图2 1 是一个 典型的基本型g i s 硬件配置，它是一般用户最常用的配置。 j描位堆千抱蕊 图2 1 基本型g i s 硬件系统 f i g 2 1g i sh a r d w a r es y s t e mo f b a s i ct y p e 软件 是指g i s 运行所必须的各种程序，主要包括计算机系统软件和地理信息系统 软件两部分。地理信息系统软件提供存储、分析和显示地理信息的功能和工具。 主要的软件部件有：输入和处理地理信息的工具；数据库管理系统工具；支持地 理查询、分析和可视化显示的工具；容易使用这些工具的图形用户界面( g u 0 。 数据 数据是一个g i s 应用系统的最基础的组成部分。空间数据是g i s 的操作对象， 是现实世界经过模型抽象的实质性内容。图2 2 展示了g i s 对现实世界的信息表达 与分层。 7 晦一p 重庆大学硕士学位论文2 g i s 基本理论介绍 图2 2g i s 对现实世界的信息表达及分层 f i g ，2 2g i se x p r e s s i o na n dh i r a c h yo f r e a l i t y 一个g i s 应用系统必须建立在准确合理的地理数据基础上。数据来源包括室 内数字化和野外采集，以及从其它数据转换而来。数据包括空间数据和属性数据， 空间数据的表达可以采用栅格和矢量两种形式。空间数据表现了地理空间实体的 位置、大小、形状、方向以及几何拓扑关系。 人员 人是地理信息系统中重要的构成要素，g i s 不同于一幅地图，它是一个动态的 地理模型，仅有系统软硬件和数据不能构成完整的地理信息系统，还需要人进行 系统组织、管理、维护和数据更新、系统扩充完善以及应用程序开发，并采用空 间分析模型提取多种信息。因此，g i s 应用的关键是掌握实施g i s 来解决现实问 题的人员素质。这些人员既包括从事设计、开发和维护g i s 系统的技术专家，也 包括那些使用该系统并解决专业领域任务的领域专家。一个g i s 系统的运行班子 应有项目负责人、信息技术专家、应用专业领域技术专家、若干程序员和操作员 组成。 方法 这里的方法主要是指空间信息的综合分析方法，即常说的应用模型。它是在 对专业领域的具体对象与过程进行大量研究的基础上总结出的规律的表示。g i s 应用就是利用这些模型对大量空间数据进行分析综合来解决实际问题的。如基于 g i s 的矿产资源评价模型、灾害评价模型等。 2 1 4g i s 的功能 一个g i s 软件系统应具备五项基本功能，即数据输入、数据编辑、数据存贮 与管理、空间查询与空间分析、可视化表达与输出。 数据输入 数据输入是建立地理数据库必须的过程。数据输入功能指将地图数据、物化 8 重庆大学硕士学位论文2 g i s 基本理论介绍 遥数据、统计数据和文字报告等输入、转换成计算机可处理的数字形式的各种功 能。对多种形式、多种来源的信息，可实现多种方式的数据输入。如图形数据输 入、栅格数据输入、g p s 测量数据输入、属性数据输入等。 数据编辑与处理 数据编辑主要包括图形编辑和属性编辑。属性编辑主要与数据库管理结合在 一起完成，图形编辑主要包括拓扑关系建立、图形编辑、图形整饰、图幅拼接、 图形变换、投影变换、误差校正等功能。 数据的存储与管理 数据的有效组织与管理，是g i s 系统应用成功与否的关键。主要提供空间与 非空间数据的存储、查询检索、修改和更新的能力。矢量数据结构、光栅数据结 构、矢栅一体化数据结构是存储g i s 的主要数据结构。数据结构的选择在相当程 度上决定了系统所能执行的功能。数据结构确定后，在空间数据的存储与管理中， 关键是确定应用系统空间与属性数据库的结构以及空间与属性数据的连接。目前 广泛使用的g i s 软件大多数采用空间分区、专题分层的数据组织方法，用g i s 管 理空间数据，用关系数据库管理属性数据。 空间查询与分析 空间查询与分析是g i s 的核心，是g i s 最重要的和最具有魅力的功能，也是 g i s 有别于其他信息系统的本质特征。地理信息系统的空间分析可分为三个层次的 内容： 1 ) 空间检索：包括从空间位置检索空间物体及其属性、从属性条件检索空间物体； 2 ) 空间拓扑叠加分析：实现空间特征( 点、线、面或图像) 的相交、相减、合并 等，以及特征属性在空间上的连接； 3 ) 空间模型分析；如数字地形高程分析、b u f f e 分析、网络分析、图像分析、 三维模型分析、多要素综合分析及面向专业应用的各种特殊模型分析等。 可视化表达与输出 中问处理过程和最终结果的可视化表达是g i s 的重要功能之一。通常以人机 交互方式来选择显示的对象与形式，对于图形数据，根据要素的信息密集程度， 可选择放大或缩小显示。g i s 不仅可以输出全要素地图，也可以根据用户需要，分 层输出各种专题图、各类统计图、图表及数据等。 除上述五大功能外，还有用户接口模块，用于接收用户的指令、程序或数据， 是用户和系统交互的工具，主要包括用户界面、程序接口与数据接口。由于地理信 息系统功能复杂，且用户又往往为非计算机专业人员，用户界面是地理信息系统 应用的重要组成部分，使地理信息系统成为人机交互的开放式系统。 9 重庆大学硕士学位论文 2 g i s 基本理论夯绍 2 1 5g i s 的主要应用领域及其与c a d 的区别 g i s 的应用领域 自6 0 年代加拿大建立世界上第一个地理信息系统并由t o m l i n s o n 率先提出 g i s 的概念之后，在最近的二十多年时间里o i s 的研究与应用得到了突飞猛进的 发展。主要应用在环境保护与管理，社会调查与统计分析，城市基础设施管理， 土地信息系统的建立等方面，以及城市规划、房地产开发及物业管理、商业开发 与购物中心设置、资源调查、灾害预报与灾后评估、金融机构与投资分析、地质 普查、采矿等。 g i s 与c a d 的区别 c a d 和g i s 之间有大量的技术重叠，两者都用计算机图形，相似的输入、输 出设备，和生成漂亮的彩色图像。但是，两者的相似性到此为止，表2 1 列举了二 者的区别。 表2 1c a d 与萄s 的区别 1 h b l e 2 1d i f f e r e n t i o no f c a da r i dg i s c a d g 工s 由制图员构成图形 由扫描数字化或测量方法得到图形 包含水平和垂直线段，通常线段之间的夹角是规实际上不包含水平或垂直线段，除了直角，其它的规则夹 则的；角很少；另一方厩，形状破碎的线段，如等高线和海岸线， 则很平常； 频繁用到映射、旋转、比例、拷贝之类的操作不常用映射、旋转、比例、拷贝之类的操作 圆弧和曲线是基本的；实际上不存在圆弧和曲线； 一个典型的多边形有四个顶点 一个多边形可能有上千个顶点 目标问的拓扑关系实际上不存在；拓扑是主要的考虑因素 很少用栅格栅格是获取地图库或卫星数据的一个有效、经济的方法。 2 1 6 我国g i s 的应用前景和存在的问题 面临的机遇 目前g i s 的研究和应用都处在一个高速发展的阶段。在国外g i s 技术已被各 级政府部门和企业界广泛认知和采用。尤其是在北美、欧洲、日本和奥大利亚等 国家和地区，g i s 市场已经基本形成。g i s 数据公司和软件公司比较多，他们在 g i s 系统建立和空间数据的使用方面已有了一套比较规范和成熟作法。在我国g i s 技术也正被越来越多的政府部门和大型企业所采用。虽然起步较晚，但是有后发 优势，可以少走弯路，以比较高的起点开展g i s 的理论研究和开发应用工作。 存在的问题 与国外对比分析，目前我国g i s 发展中存在的问题主要表现在如下几个方面： 1 ) g i s 的科学和经济价值尚未被广泛地接受和认知，因此处于资金投入不足、推 广应用比较困难的局面。 1 0 重庆大学硕士学位论文2 g i s 基本理论介绍 2 ) 根据有关资料的分析，地理信息系统中数据部分要占整个系统投资的百分之七 十左右，也就是说g i s 系统的建立需要大量的数字地图或电子地图及其属性信息 库的支持，但在我国地图数字化的比例还很低。这需要政府部门及有关企业投入 大量的精力及资金进行数字地图的建库工作。 3 ) g i s 市场尚未形成，有关数字产品的法律、权属、定价等方面的问题还没有得 到有效的解决。 4 ) 有关数字地图产品的规范和标准，以及数据格式有待统一和完善。 5 ) 我国具有自己知识产权的g i s 系统平台比较少，目前只有m a p g i s 、g e o s t a r 等少数几个产品，大量进口g i s 系统平台增加了g i s 应用开发的成本。而且，由 于国