（计算机软件与理论专业论文）基于电力gis的最短路径优化算法的应用与分析.pdf

；i ；! 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 论文使用授权 硇龟年y 其坍 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：里查：呈壬导师签名： d 埘 】+ 4 川尼 ，将d 括f 尼】赋值为 d 括旺刀+ 铆 尼】，并且将砌砌 尼】容器中的最后一个元素删除，添加_ ，。 5 重复执行步骤3 ，4 ，直到y s 集合中的元素为空为止，则就找到了从点出 发到图中所有其他节点的最短路径，及其长度值。 以图2 2 为例，运用d 钉k s t r a 算法，求出到其他节点的最短路径集合如下表 所示： 8 第二章最短路径算法的分析与研究 表2 1 最短路径结果 从顶点到k 中各个顶点的最短路径 顶点 巧k蚝 圪k 巧 o oo oo do oo 。 砭1 0 ( ，k ) 巧 o o 6 0 ( 圪，圪，巧) 5 0 ( ，圪，k ) 圪 3 0 ( ，圪)3 0 ( k ，圪) 圪 1 0 0 ( ，圪)1 0 0 ( ，圪)9 0 ( 圪，巧，圪)6 0 ( ，圪，巧，k ) s ( 圪，k )( 圪，匕，k )( k ，匕，k ，圪)( 圪，匕，巧，圪，圪) 实现d i j k s t r a 算法需要两层循环，外层循环的时间复杂度为d ( ，z ) ，内层循环 的时间复杂度也为d ( ，2 ) ，所以该算法的总的时间复杂度为d ( ，z 2 ) 。 2 2 2a 宰算法 a 木最短路径算法是一种比较好的空间寻路算法，该算法以人工智能为基础。 网络游戏的最短路径算法多是在此基础上开发的。不同于d 玎k s t m 算法中盲目的 查找下一节点，a 木算法在进行最佳路径搜索的时候，是用估计函数的值来确定搜 索方向的，估计函数为： 厂( ，1 ) = g ( ，2 ) + j l z ( ，z ) ( 2 - 1 ) 其中的厂( ，z ) 代表开始节点到达目标节点的估计函数，g ( ，z ) 表示的是开始节点 到节点豫的实际距离，办( ，z ) 为节点刀到目标节点的估计值，这个值的选择体现了 人工智能在最短路径搜索中的启发作用。乃( 胛) 的信息越多，则最短路径的选择方 向越准确，但是计算量就越大，所消耗的时间也就越多。如果 ( 刀) 的信息少，则 计算量就会变少，消耗的时间就会少。这之间需要有所衡量【3 2 1 。 在a 半算法中，要用到两个容器例和c 乙彻。例d e 容器中包含的元 9 电子科技大学硕士学位论文 素是已经计算出厂( 以) 的，但还没有检查过的节点。c l 彻容器中包含的元素为 已经检查过的节点。从删容器中，选出厂( 刀) 最优的节点，放到c 己锄容器 中，并遍历与该节点的相邻节点，计算出厂( ，z ) 放入删容器中。具体算法如下： 1 初始化例咂容器，将始节点插入仞咂容器中，并计算起始节点的估计函数 厂( 托) 。初始化c 乙彻容器为空。 2 从删容器中取出厂( 咒) 最优的节点，如果该节点是终结点，则查找成功。否 则，查看该节点是否在删容器或c 己彻容器中。 3 如果都不在，则将该节点放入c 乙彻容器中，遍历与该节点相邻的节点并计 算厂( 刀) ，插入删容器中。 4 如果该节点在d j 吧容器中，则比较该节点的厂( ，z ) 同在刎咂容器里的节点的 厂( ，z ) 的大小，如果小于的话，则更新例咂容器里该节点的厂( 以) 。如果大于的 话，删除删容器里的该节点。转2 操作。 5 如果该节点在c e 0 艇泐容器中，则比较该节点的厂( 以) 同c e 彻容器里的该节 点的厂( 甩) 的大小，如果小于的话，则将该节点重新放进。! 尸! e 容器里，然后改 变与该节点相关联的节点的厂( ，z ) 的大小。 6 重复第二步，直到d 尸：e 容器中为空为止【4 1 1 。 在进行a 木算法时，五( ，z ) 通常设置为节点，z 到终点的直线距离，假设节点，z 的 坐标为( 五，y 。) ，终点的坐标为( 恐，) ，则： 厂= _ j i z ( 刀) = ( 五一恐) 2 + ( y i 一儿) 2 ( 2 2 ) 从上面的算法可以看出，a 木算法总是优先选择距离终结点最近的节点，克服 了d i j k s 昀算法寻找目的节点时的盲目性。这种智能寻找节点的方法极大的提高 了查找最佳路径的效率，但也带来了计算上面的复杂性。 2 2 3 弗洛伊德算法 弗洛伊德算法也是求最短路径的一个非常著名的算法，虽然它在算法复杂度 方面同d i j k s t r a 算法是一样的都是0 ( 咒2 ) ，但是在形式上还是要简单一些。因此在 这里做一下介绍。 对于一个图的两个节点v 和y ，如果这两个点连通的话，则可以记下连同弧 度权值d m i n ，当然这不一定是最短路径。所以还需要进一步查找，具体的查找 过程是： 1 在h 和路径上添加一个节点，即( u ，v 0 ，) ，看是否存在该路径，如果存在， 1 n 第二章最短路径算法的分析与研究 则比较与d m i n 的大小，取较小者赋值给d m i n ，则找到的即为从 到1 ，的中间 节点的序号不大于o 的最短路径。 2 在v 和1 ，路径上添加一个节点m ，如果存在从m 到h 的最短路径，而且存在从m 到v ，的最短路径，则我们可以肯定能找到( m m y ，) 的最短路径，将它与 d m i n 相比较，取较小者赋值给d m i n ，并记录下最短路径经过的节点。则我们 找到了从坼到1 ，的中间节点的序号不大于l 的最短路径。 3 以此类推，假设要加入节点u 时，如果( m y 1 ，) 最短路径存在，则与d 耐n 比较，去最小值赋值给d m i n ，并记录下最短路径经过的节点。则寻找到的最 短路径为从到v ，的中间节点的序号不大于七的最短路径。 4 最后查找到节点u ，则经过以次节点的遍历，一定可以寻找到从m 到v ，的最短 路型4 1 1 。 弗洛伊德算法很适合运用递归的方法来进行编程，但是如果节点过多的话， 对系统效率的影响就很大。 2 3 最短路径算法性能比较 不论是d i j k s t r a 算法，a 半算法，还是弗洛伊德算法，都是最短路径中的静态 最短路径算法。所谓静态指的是，节点相对固定，节点与节点之间的连线也是相 对固定的。这跟我们电力网络结构很相似，变压器和变电所的相对位置是比较固 定的，而且城市中的电线分布也是相对稳定的。因此在电力g i s 中，通常都是运 用静态最短路径算法或其优化算法来解决最优路径问题。 d “k s 仃a 算法是为求出指定的节点到图中任意节点的最短路径来设计的，它的 时间复杂度为d ( ，z 2 ) ，空间复杂度为d ( 万+ 历) ，如果要是用这个算法来求图中任意两 点间的路径则它的空间复杂度为d ( ，z 3 ) 。 a 木算法的时间复杂度跟d i j k s t r a 算法的时间复杂度是一样的，不过a 木算法不 必搜索所有的剩余节点，这要选择最有可能的节点就可以了。如果我们在利用a 宰 算法时，如果设置一个值，只要从v 到1 ，的路径低于这个值的时候，就认为已经 找到了最短路径就不必再搜索图中的节点了。因此，虽然这两种算法的时间复杂 度都是d ( 力2 ) ，但是a 宰算法在实际应用中，运行效率比d i i k s t r a 算法要好很多。 弗洛伊德算法跟前两种比起来，它的时间复杂度为0 ( 刀3 ) 。该算法的一个最 大的优点就是，在你寻找从峙到1 ，的最短路径的时候，同时也会找到图中任意两 点间的最短路径。 电子科技大学硕士学位论文 从以上分析中可以看出，三种最短路径算法各有千秋，在应用中，要根据实 际情况选择，必要时要对其进行优化，使其能更有效的在g i s 系统中发挥作用。 2 4 本章总结 本章首先介绍了关于图在图论中的一些基本知识。然后给出了在计算机数据 结构中，图的两种存储结构：一种是邻接矩阵，另一种是链接表。并通过实例展 现了这两种数据结构怎么存储图的信息。然后介绍了三种目前比较经典的求最短 路径算法：d i j k s t r a 算法，a 木算法和弗洛伊德算法。通过具体的实例详细介绍了 这三种算法的处理过程，然后对这三种算法从时间复杂度和实际应用方面进行了 较为详细的比较和分析。 1 2 相关原理与技术 第三章g i s 与w e bg i s 相关原理与技术 3 1g i s 的基本概念与本质特征 g i s 最早是由美国和加拿大在上世纪6 0 年代发展起来的，随着该技术的不断 成熟，它在全球定位、电力、土地资源管理等方面起到了相当重要的作用。尤其 进入了2 1 世纪，随着互联网技术的飞速发展，g i s 的相关技术的不断发展和完善， 再加上与h l t e n l e t 的相结合为w 曲g i s 的产生和发展打下了良好的基础。 3 1 1g i s 的基本概念 地理信息系统( g e o 缪a p h i ci n f o m a t i o ns y s t e m s ，简称g i s ) ，是一种信息系统， 它将地球上事物的空间地理数据和信息同地球表面空间的地理现象作为处理的对 象。g i s 对抽象的地理空间数据进行加工，提取出有用的空间信息和知识系统。 在地理信息系统( g i s ) 中，通常包含有处理地理空间数据的几种主要功能，这其中 包括了采集( c o l l e c t i n 曲、存储( s t o r i n g ) 、显示( d i s p l a 姐n g ) 、操作( m a l l i p u l a t i n g ) 、 分析( a n a l y z i n 曲、管理( m a n a 百n g ) 、建模( m o d e l i n g ) 等。 空间地理信息系统比较完整的定义是在计算机软硬件的支持下，运用系统工 程和信息科学等理论，对地理空间数据进行采集、输入、存储、操作、分析和建 模，以提供对资源、环境和区域等的研究、规划、管理和其他决策所需的信息的 人机系统。 3 1 2g i s 的本质特征 作为一种对地图数据进行处理的系统，有它本身基本的特点： 1 物体在地图中的空间信息。我们在这里所说的空间信息指的是该物体在这个特 定的地图范围中的坐标，或者与其他物体的相互关系。因此物体的这种空间信 息包括了两个层次的意义：第一是物体的绝对位置，这个是物体在地图中的坐 标。例如一个变压器在成都市的坐标为( x ，y ) ，还有一个架空线在地图中需要 三维坐标( x ，y ，z ) 标识。这些坐标的取值可以为地图上某一个固定的参考物， 或者用地球坐标的经纬度来表示。第二是地图上物体之间的空间位置关系信息， 1 3 电子科技大学硕士学位论文 这些在电力系统中可表示为两个电缆线之间的距离，是否相交，有多少条电线 与一个变压器相连接等。 2 物体的自身所拥有的属性信息。g i s 系统不但会记录物体的空间位置信息，而 且也会记录物体本身所具有的属性信息。例如一个变电所，若仅有它的空间位 置( x ，y ，z ) 。那么这只是抽象的表现出物体在地图上的位置，但是它具体的属 性是什么，就需要从该设备的属性信息中得出。比如人们想知道这个变电所的 名称，每年有多少安的电流流经该变电所，该变电所为多少用户提供电能等等， 就要从该物体的属性信息中得到。 3 空间物体的时间特性。我们都知道g i s 系统中的空间数据信息只能反映采集信 息的那个时间段的特征，然而随着时间的推移这些信息就会出现变化。比如一 个变电所本来在( 五，y 。) 位置，但当地的城市规划将它迁移到( 屯，儿) 位置，则如 果地图信息不随之更新的话。那么在地图上对该变电所所做的操作在现实世界 中的映射都是错误的。还有一种，为了反映某事物的变化，可以定期采集信息， 通过g i s 系统可以看到该物体随时间变化的过程。随着地图信息采集技术的不 段发展，这个时空数据库技术正得到了全所未有的发展。 同一般的信息系统相比，g i s 是专业的以处理地图数据为基础，为用户提供 服务。因此，它具有别的信息系统所不同的特点，具体如下： 1 物体空间数据的复杂性。g i s 系统不同于一般的信息系统的一个重要特点是： g i s 系统所处理的都是物体的空间数据，而一般的信息系统处理的数据都是数 字信息，这也造成了g i s 系统比一般信息系统的复杂性。由上面的观点可以看 出g i s 中的空间信息不但包括物体的位置信息，同时也包括物体的属性信息。 其中的属性信息可以像一般的数据一样存储在数据库中，而物体的空间信息则 要进行空间数据建模等操作，经过特殊的转换存储在数据库中。在对空间数据 库中的数据进行查询的时候，还要经过特殊的处理才行。在心c g i s 访问空间 数据库时，程序员可以使用a r c s d e 所提供的接口来访问数据，但数据转换还 是要花费时间的。 2 g i s 比起一般的系统来，它的可视化要求更高。由于g i s 操作的都是地图数据， 所以可视化是该系统必须具备的功能之一。如何才能使得g i s 的可视化水平更 加科学已经成为现代科学中的热门话题，所谓科学的可视化指的是通过图形或 图像等可以看见并验证的手段，来表现物体的空间内涵。科学研究表明，人类 所获得的知识8 0 来自于眼睛，因此可视化是人们提高知识和信息理解的最有 效的手段。地图也是基于这种原因才产生出来的。这种可视化手段反映了地理 1 4 第三章g i s 与w 曲g i s 相关原理与技术 物体和现象的时空组合、分布和连线，揭示地理发展变化的有效途径。g i s 不 仅要有科学的可视化功能，而且也要及其重视发展这种功能。 3 区域性和多层次。g i s 以处理地理空间数据为主，而地理空间数据又通常是以 区域为单位组织的。因此，区域性是地理信息系统的另个重要的特点。另外 g i s 还具有鲜明的层次性，具体有两种含义的层次。一种是区域层次。地球上 的区域层次是很多的，小到一个县城，大到一个国家。另一种是专题层次。专 题层次就好比地图学中的专题地图，同一区域有好多种专题地图，比如成都市 的交通旅游图、环境保护图、土地利用图和城市规划图等。在g i s 中，不同专 题的地理空间数据也常常分别加以组织，形成同一区域的专题数据层次。 4 数据量巨大和注重空间分析。同一般信息系统相比，地理信息系统所涉及到的 数据量通常比较大，有的g i s 数据库非常大，以至于用“海量”、“超海量 这 样的词来描述。地理信息系统的数据量大，一是由于它的区域性、多层次，另 一方面是由于地理信息系统包括可视化表达涉及图形图像数据，这些数据一般 都很大。g i s 同别的系统一样，必须具有分析功能，以提取有用信息。该系统 除了具备一般系统所具有的系统分析功能外，还具有独有的“空间分析”功能。 它是g i s 中最核心、最重要的概念之一。空间分析指涉及空间位置要素的分析 或区域性分析，用以提取地理空间信息以及关于地物时空分布、组合、联系和 发展的知识。空间查询检索、空间操作、地图学分析、空间统计分析和空间分 析模型等，都属于空间分析的范畴。 3 2w e bg i s 基本原理极其相关技术 3 2 1w e bs e i c e s 原理及其相关技术 w 曲s e r v i c e s 简称w s ，是一种通过i n t e m e t 为用户提供各种服务的技术。w e b s e i c e s 的一个典型过程是：客户通过i n t e m e t 使用h t t p 的s o a p 协议来向特定 的u r l 上的服务提出请求，这个服务就会根据用户提供的参数，计算出结果然后 以x m l 语言的形式返还给用户。一个经常被应用的例子是机票查询服务，服务 请求的是某月某日从某地到某地的机票价格，用户输入相关参数提交查询。服务 根据用户输入的参数查询数据库，并将符合条件的航班信息返回给用户。这就是 一个最简单的w e b 服务的例子。w 曲s e n ，i c e s 的工作流程图如下图所示： 1 5 电孑科技大学硕士学位论文 服务项目 h t t p ：、矾、vu u d l o r g 客户端杏找w 曲 w s d l 文档的u r l 连接 u u d i 服务说明 h 印：w w w m y s e i c e c o l t i ， w e bs e r 、r i c e s m v s e r v i c e w s d l 客户端请求服务说明 客户端 返回服务说明 w 曲 - - s e r 、r i c 鹤 服务使用 服务器 客户端请求w 曲s e r v i c 嚣 返回服务响应 图3 1w 曲s e r 、，i c e s 处理请求过程 对于w 曲s e r v i c e s 的统一定义至今还没有。简单的说，w 曲s e i c e s 是符合 某些标准的分布式应用构件，这些标准使它们能够在外部被访问，并且解决行业 问题。 关于w 曲s e i c e s 的定义很多，但是还没有一个统一的标准，现阶段公认的 比较准确的w 曲s e i c e s 的定义是：它是用来解决点对点的程序间通信，它的体 系结构是一种分布式的、跨平台的，有一个功能叫u d d i ( 注册中心) ，服务请求者 ( r e q u e s t e r ) 通过这个注册中心来定位所需要的服务，该r e q u e s t e r 发送请求所使用 的协议是s o a p ( 简单文件传输协议) 。服务请求者还可以选择w s d l 来确定该服 务所要求的参数。所有的这一切都是要基于i n t e m e t 的标准协议，不然还是不能 达到共享信息的目的。随着软件技术的发展，一种叫做松散耦合的软件设计理念 随之产生出来，而w 曲s e r v i c e s 的出现正是这种技术的很好的体现。以前的系统 程序都是紧密耦合的。因此在程序员开发系统的时候，不但要注意客户端的接口， 而且要设计服务器端的接口，以及他们的通信协议。这就给程序员带来了很大的 麻烦。而松散耦合的软件设计理念，就不需要程序员关注这此东西，只关注与功 能的实现和系统的稳定性方面，这样就极大的提高了软件开发的周期。 由于现在的编程模式都是面向对象的编程方式，因此w 曲s e r v i c e s 为了更好 1 6 第三章g i s 与w 曲g i s 相关原理与技术 的适应这种编程语言，w 曲s e r 、，i c e s 的整个数据结构都由对象来表示。它将对象 的所有操作都抽象成服务的形式供别人调用，这种服务提供和服务请求的方式包 括了：服务请求者、服务提供者、服务代理。光提供这些还不够，还要提供在这 些概念上的操作。比如：服务提供者要有发布服务的操作( p u b l i s h ) 、服务请求者 能够在网络中找到该服务( f i n d ) ，而且服务提供者要在注册中心那里注册自己发布 的服务( b i n d ) 【2 6 1 。 w 曲s e r v i c e s 的三个主要服务如下： 服务提供者( s e r v i c ep r o v i d ：服务发布者就是设计这个服务的程序员或公 司，他提供这项服务来达到一种商业目的或是完成某项工程。 服务请求者( s e r v i c er e q u e s t 神：服务请求这就是那些需要这些服务来完成工 业或工程任务的公司或个人，如果光从软件的角度来考虑的话，他们就是用户所 使用的浏览器或客户端。 服务代理( s e i c eb r o k e r ) ：我们可以将服务代理比喻成一个服务数据库，服 务提供者将服务的描述信息和功能结构存储在里面，而服务请求者则可以通过这 个代理查找自己需要的服务，并根据描述的参数接口进行调用。 w 曲s e r v i c e s 的三种基本操作如下： 发布( p u b l i s h ) ：所谓信息发布就是将自己或公司所提供的服务存储在u d d i 服务器上面。在这里服务发布者要提供该服务所必要的描述和接口信息。而要完 成此类注册，需要u d d i 的合法用户才行。 查找( f i n d ) ：所谓查找服务就是服务请求者根据需要在注册中心那里查找自 己所需要的功能模块，由于服务发布本身已经提供了服务描述，所以这种查找就 如同数据库查找一样。这里主要有两种查找模式。一种是根据关键字精确查找。 这种查找模式的优点是速度快，但要求对服务描述有所了解。另一种则是对那些 服务描述不了解的用户，这就需要逐步缩小查找范围，直到找到所需要的服务【2 6 1 。 绑定( b i n d ) ：所谓服务绑定，就是服务请求者根据服务发布者所提供的服务 描述来配置自己程序的环境，这些配置信息包括：调用服务所需要的参数、访问 地址等。如果能够b i n d 成功，用户就可以顺利的接受该服务。 在w e bs e i c e s 底层有三个重要的协议，他们构成了w 曲s e i c e s 的通信核 心。它f 门是：s o a p ，w s d l ，u d d i 。 1 7 电子科技大学硕士学位论文 3 2 2w e b g i s 的实现方式 从网络技术的角度来看，h t e m 引i n 仃a 1 1 e t 可以看作是以t c p i p 为通信协议标 准、以d n s 域名服务器和s m t p 简单邮件传输协议为基础、以w w w 和f t p 服 务为支撑、实现多服务器和多平台的相互连接的计算机网络通信。目前i n t e m e t 已经成为了部门或企业内外各种信息管理和交换服务的平台。w 曲g i s 是以 1 1 1 t e m e t 为载体的，所以也可以说它实现了服务器端和客户端数据传输通信。 w 曲g i s 系统充分利用了b r o w 副s e r v e r 分布式体系结构的技术特点，是 b r o w 酬s e n ，e r 的一个典型实例。分布式体系结构是一种能够使客户端和服务器端 都具备提供功能强大、可执行进程的体系结构，可以真正的实现有效平衡客户端 与服务器端之间的处理负荷，实现计算分布和数据分布的目标，使系统具有可互 操作性，从而可以把数据量处理比较大的进程放在服务器端执行，在客户端则完 成一些简单操作比如，空间查询、专题地图生成等进程，这样就发挥了客户端和 服务器端的各自优点，最大限度地提高了系统的作用。w 曲g i s 系统的b s 结构 的体系结构使得系统具有良好的开放性，从而使得系统具有跨平台运行、数据多 重应用、软硬件资源共享、易于集成等特点。可以说，w 曲g i s 系统是一个建立 于i n t 锄e t i n t r a n e t 之上的采用开放式结构、具有统一标准和广泛适应性的网络应 用系统。 对于一般的信息系统会有两种解决方案，一种是胖客户端，一种是瘦客户端。 胖客户端顾名思义就是将系统的大部分操作放到客户端来进行，这就要求客户端 有较强的信息处理能力；瘦客户端则是将系统的大部分操作都放到服务器端处理， 这种构架对网络宽带的要求比较高。对于w 曲g i s 来说，人们根据图形数据存放 的位置不同，将其分为服务器端的解决方案和客户端的解决方案。但是也有些系 统是二者的混合体。 对于服务器端的解决方案，g i s 中的地图空间分析和输出等需要进行大量计 算的操作由服务器来完成，而客户端则只需要负责用户请求等简单操作。客户端 通过c g i 同g i s 服务器相连接，最后在客户端的浏览器上将结果显示出来。这种 模式的唯一缺点就是对网速的要求比较高。 对于客户端解决方案来说，就是将在服务器端的解决方案中的服务器所处理 的一些操作放到客户端来，比如上面所说的空间分析等。但是对于一些过于复杂 的、高级操作，客户端是没有能力去完成的，才去发请求给服务器。服务器处理 完成后将以矢量地图数据的形式发回给客户端。同之前的服务器端的解决方案相 1 8 第三章g i s 与w 曲g i s 相关原理与技术 比较，w 曲g i s 客户端解决方案能够有效减少服务器端的负荷和缓解网络堵塞。 但是需要在客户端安装体积庞大的插件。 w 曲g i s 系统开发最初采用通用网关接口技术，以及以后发展起来的a s p ， i d c ，i s a p i ，n s a p i 等技术，到后来又产生了被称为“插件”( p l u g i n ) 的应用技 术。几种比较常用的w 曲g i s 技术如下： 1 c g i 技术方法构建w 曲g i s 系统。c g i ( c o m m o ng a t e w a vi n t e r f a c e ，通用网关接 口) 的方法就是互联网络服务器( w 曲s e r v e r ) 通过调用外部应用程序的接口扩展 网络服务器的功能。这时c g i 的作用相当于在外部应用程序与h l t e m “i l l t r a i l e t 网络服务器之间架设一座桥梁，使网络服务器对客户端的请求作出响应。客户 端通过网络服务器激发c g i 程序的响应实现具体的操作，并将读取的数据信息， 通过服务器发送给客户端。c g i 的本质功能就是规范了网关程序和服务器的通 信规则。在服务器端，g i s 通过c g i 与w 曲服务器相连。当客户端程序向服务 器发出一个请求，s e r v e r 端就通过c g i 把该请求发送给后台的g i s 应用程序， 应用程序处理好之后，交还给s e e r ，s e n r e r 再将请求结果发回给客户端。其 工作方式如下图所示。 求发送给c g i 程序，然后 将输出传给客户端。 0 g i 请球 客户机 服务器 外部服务 1 c g l 程厅 厂 器 图3 2 c g i 的工作原理 2 利用服务器端应用程序接口建立w 的g i s 系统。服务器端应用程序接口技术的 出现是为了解决c g i 方法的低效率的问题而研制的。这种方法和c g i 的原理基 本上很相似，他们之间的差别就在于c g i 是单独能够运行的程序，而基于服务 器应用程序接口建立的程序必须要在特定的服务器上才能够运行。相比较c g i ， 1 9 电子科技大学硕士学位论文 服务器端应用程序接口的特点是运行速度比c g i 要快，这是由于该服务 应用程序接口一旦打开，就会一直处于运行状态，不像c g i 每次都要重新启动。 但是它也存在着缺陷，那就是服务器端应用程序只能够运行在特定的服务器上 和软件平台之上。例如，微软公司的i s a p l 只能在w i n d o w s 平台上面运行。因 此，相比较c g i 技术，虽然看起来有些落后，但由于其普遍性，可以在任何平 台下应用，而且任何语言都可以编写出c g i 程序，因此它现在的用途依旧很广 泛。许多商业化系统如e s r i 的i n t e m e tm a ps e e r ( i m s ) 仍然采用的是c g i 技 术。 3 利用p 1 u g i n 插件技术方法来建立w 曲g i s 系统。前面所讲的两种方式，服务 器应用程序接口和c g i ，虽然增强了用户端的交互性，使用户可以获得到各种 各样的地图和地理空间数据，但是用户接收到的信息依旧是静态的，不能够实 现地图的放大、缩小操作。因为服务器传送给客户端的地图是一个完整的实体。 任何对地图的操作，比如对地图的放大、缩小等都要交由服务器端来完成。这 就给网络宽带造成了很大的压力，当处于网络流量的高峰期时，用户的系统反 映就会变慢。通过把一部分服务器的功能移到用户端。这样不仅大大提高客户 端的反映速度，而且也避免了在网络高峰期造成的网络堵塞。p 1 u g - i n ( 插件法) 是由美国的网景公司( n e t s c a p e ) 研制开发的，该方法增加网络浏览器的功能。 p 1 u g i n 对外提供了一套应用程序接口( a p i ) ，可以用来开发与网络浏览器直接交 换功能的方法。该插件使w 曲页面提供者在现有标准支持下，可以加进新的内 容。这种方法构造w 曲g i s 系统的思路和原理与c g i 技术方法有很多相似之处， 但是两者所不同的是p l u g i i l 是在客户端的浏览器上添加了能识别矢量图形的 数据的插件。用户通过使用这种插件，就使得从服务器上发过来的矢量图形数 据不需要进过任何转换，就能直接在浏览器上实现浏览、查询、分析等功能， 从而大大解决了网络数据的传输量，解决了网络上图形数据信息传输的瓶颈。 同时，矢量图形与其属性数据已建立的对应、关联关系也易得到保存。将这一 技术应用到商业软件中的有美国的a u t o d e s k 公司的m a p g u i d e 就是基于这个原 理搭建的w 曲g i s 平台。 4 利用a c t i v e x 控件和d c o m 组件对象模型技术建立w 曲g i s 系统。a c t i v i e x 是 由美国的m i c r o s o r 公司开发的一种对象链接与嵌入技术( o l e ) ，它被广泛的应 用于1 1 1 t e m e t 的开发。它是以d c o m ( d i s t 舶u t e dc o m m o no b j e c tm o d e l ，分布式 组件对象模型) 为基础。d c o m 是一种技术标准，而不是一种编程语言。开发 人员通过d c o m 和a c t i v e x 技术来构造各种g i s 系统功能模块，并将这些技术 2 0 一 磊 第三章g i s 与w 曲g i s 相关原理与技术 同o l e ( 对象链接嵌入) 、s d e ( 空间数据引擎) 技术相结合，开发出功能强大的 w 曲g i s 系统。 3 3g i s 地理数据模型 3 3 1 地理数据模型的发展 地理数据模型是一系列数据对象的集合，这些数据对象能够显示地图、查询 信息、编辑和分析地图，这种模型是对现实世界的抽象。g e o d a t a b a s e 数据模型是 由e s r i 公司推出的，心c i n f 0 8 全面支持这种对象的数据模型。它能够准确的表 示空间物体，包括他们自身的属性和与其他物体的联系，这种对象模型对于整个 g i s 系统的发展起到了深渊的影响。为了能够更好的了解g e o d a t a b a s e 数据模型， 我们先回顾一下数据模型的发展历程。 1 运用c a d 对空间物体建模 最早的计算机制图系统使用的是阴极射线管的显示线绘制矢量地图、使用行 式打印机上的加印技术绘制栅格地图。以此为起源，1 9 世纪6 0 年代到7 0 年代出 现了精致的绘图硬件工具以及能够使用合理逼真制图技术将地图符号化的制图软 件。 这一时代，地图通常用一般的c a d ( 计算机辅助绘图) 软件来制作。c a d 数据 模型以表示点、线、面的二进制文件格式来存储地理数据。但是在这些文件中， 不能存储足够多的地图图层和注记标注等基本属性信息。 2 c o v e r a g e 数据模型 c o v e r a g e 数据模型是继c a d 空间建模的第二代空间数据建模模型。它最早 是由e s r i 公司于1 9 世纪8 0 年代推出的。它作为e s r i 第一款商业g i s 软件，在 整个空间数据建模史上有着重要的地位。这种模型有两个主要特点： 在c a d 数据模型中，只够存储物体的空间信息，而与之相关联的重要的属 性信息却没有办法存储，而这种模型克服了以上的缺点，实现了空间数据和属性 数据完美的相结合。在该数据建模中，将物体的空间数据信息存放在二进制索引 文件中，将其属性信息按照一般的信息存放方式，存放在关系表中，在两者之间 建立一个关联。 该数据模型不但存储物体的空间信息，也存储物体之间的拓扑关系。这就意 味着，面的空间数据信息包含了该面与哪些面有重叠，与哪些边相交，它的形状 2 l 电子科技大学硕士学位论文 等等的信息。 臻爱”。弘 ：。：疵。，荔， 图3 3 矢量元素在数据库中的存储形式 从上图可知，c o v e r a g e 数据模型将现实物体抽象为点，弧段，多边形等要素， 然后将这些物体的属性信息存放在关系表中，这些表和点，弧是一一对应的。 c o v e r a g e 数据模型还允许用户定义跟一般表一样的空间属性表，表格中的字 段名是用户自己定义的，除此之外，用户还能定义表与表之间的关联。 在c o v e r a g e 数据模型出现的时候，整个计算机的硬件和数据库软件的性能还 不是很强大，如果将空间数据存储在关系表中是不可能办到的事情。c o v e r a g e 选 择将物体的空间数据和属性数据分开存储，将存储空间数据的二进制文件和存储 属性数据的二维表关联起来。这样做使得对整个空间物体信息的查询很有效率， 因此这种模型在当时占据着统治地位。而c o v e r a g e 模型中的存储拓扑关系能更准 确的实现数据输入和操作。 虽然c o v e r a g e 数据模型有很多的优点，但它也存在很大的缺点。当将空间中 的物体都抽象成点、线和面的时候，我们就无法表示一些现实中的事物。比如道 路在c o v e r a g e 模型中会被抽象成一条曲线，而溪流也会被抽象成曲线，单从地图 上我们根本无法分变出它们。 c o v e r a g e 数据模型支持一种行为，它能够加强空间数据集的拓扑整合。比如 在c o v e r a g e 的数据模型中，如果我们在一条线上，画上另外的一条，则这两条线 就会交叉在一起。但是这种模型在现实世界中还是远远不够的。我们需要一种更 强大的数据建模，它能够很好的反映出真实世界对象的特殊行为。比如，有两条 从山坡上下来的溪流在某处会合，则会合的溪流的流量是上面两个溪流流量的和； 在现实世界中，如果两条道路交叉的话，他们要么是有个交叉口，如果不相交的 话，这会距离地面的高度不相等。这些空间特性在c o v e r a g e 模型中是很难完成的。 术 虽然在c o v e r a g e 数据模型中，e s r i 公司的工程师们已经取得了相当显著的 成果，例如他们利用a m l 语言编写宏代码来向要素添加某种行为，因此，这种 数据模型在很多复杂的，大规模的，特定的工业应用得到了成功建模与创建。然 而随着人们对软件的期望越来越高，人们希望软件能够做更多更复杂的信息处理。 在g i s 中，这种要求在c o v e r a g e 模型中是很难得到实现的，即使你编写再优秀的 代码也是不可能的。在这种背景下，亟待需要一种更新的空间数据建模来完成这 项工作，这个新模型，不但要能真实反映现实物体的行为，而且要求能够对其进 行关系表存储，以充分发挥数据库的高效性能。 3 g e o d a t a b a s e 数据模型 e s r i 公司在他们的升级版本的时c i n f 0 8 软件中，引入了第三代空间数据模 型g e o d a t a b a s e 数据模型，它是一种面向对象的数据模型。这种模型可以定义 图形要素的行为，使它更加符合作为自然界的一个真实物体的身份。在 g e o d a t a b a s e 中，还可以将图形中的某些要素关联起来。在g e o d a t a b a s e 数据模型 中，数据对象大都是用户在逻辑数据模型中定义的，比如业主、建筑物、宗地和 道路等等，这样就将数据的物体模型和逻辑模型联系的更加紧密了。 在以前的数据模型中，如果要定义空间物体的行为，程序员必须编写大量的 代码才能实现，而现在将空间中的物体通过g e o d a t a b a s e 数据模型方法建模，则 程序员就可以通过域、验证规则等g e o d a t a b a s e 提供的功能来实现这些物体的自 然行为。这就大大节约了程序的开发周期，可以使程序员专注于代码的实现上了。 因此自从有了g e o d a t a b a s e 数据模型，让那些不太会编程的人也可以定义物体的 自然行为了。 下面将举例说明g e o d a t a b a s e 数据建模是非常高效的。用户使用这个数据建 模可以根据需要自己定义对象类型，也可以定义对象之间的拓扑、空间和普通关 联，以及获取它们之间的相互作用关系，以便能够自如的表现地理信息。以下将 介绍g e o d a t a b a s e 数据模型的一些优点： 1 在g e o d a t a b a s e 中引入了数据仓库，g i s 中所有的数据都存储在统一的数据仓库 中进行集中化管理。 2 g e o d a t a b a s e 提供了智能验证功能，能有效的减少用户在数据输入和编辑过程中 所产生的错误。这也是上面大多数用户会选择使用g e o d a t a b a s e 数据建模的主 要原因。 3 用户更为直观地处理数据模型。有了准确的设计，g e o d a t a b a s e 包含了与用户数 据模型相对应的数据对象。操作g e o d a t a b a s e 的数据，与处理一般的点、线和 2 3 电子科技大学硕士学位论文 多边形要素不同，用户可以针对他们感兴趣的现实对象进行操作，比如变压器、 道路和湖泊等等。 4 要素具有丰富的关联环境。使用拓扑关系、空间表达和一般关联，你不仅可以 定义要素的特征，还可以定义要素与其它要素的关联情况。当与要素相关的要 素被移动、改变或删除的时候，用户预先定义好的关联要素也会做出相应的变 化。 上面所列举处理的g e o d a t a b a s e 的优点，对于c o v e r a g e 数据模型来说也是可 以实现的，但是这个是有条件的，它要求用户要编写大量的代码来实现c o v e r a g e 模型所没有实现的功能。这样对于软件开发来说是不利的，因为这样一方面影响 了整个软件的稳定性，而且需要花费大量的人力和时间在对象行为的处理上。而 g e o d a t a b a s e 正好将这些都做了，它给用户提供一个框架，程序员通过这个框架就 可以毫不费力的创建出智能化的图形要素，和与之相联系的自然行为。 3 3 2g e o d a t a b a s e 地理数据存储仓库 g e o d a t a b a s e 含有四种地理数据的描述方式： 矢量数据用于描述要素( f e a t u r e ) 栅格数据主要用于描述影像、专题格网数据和表面 不规则三角网络( t i n ) 用于描述表面 地址( a d d r e s s e s ) 和定位器( 1 0 c a t o r ) 用于地理寻址 g e o d a t a b a s e 利用现在比较流行的关系数据库来存储这些空间地理数据，比如 s q ls e n ，e r ，o r a c l e 等，将这些主流数据库的操作集成到心c i n f o 中，这样我们就 可以通过数据库来集中管理这些数据了。 g e o d a t a b a s e 的内部结构包括如下几个方面： 1 要素集、空间参考、对象类、子类、要素类，子类、几何网络、拓扑。空间参 考是维护这些要素之间拓扑结构的关键。这些要素需要在同一的坐标系中，这 是因为他们都是经由g e o d a t a b a s e 数据建模形成的空间要素，也定义了它们之 间的拓扑关系。空间物体对象、图形要素以及关联类都是存储在要素集中的。 要素中包括了空间实体，而对象不包括空间实体。要素类和对象类通过关联类 联系在一起。这里要特别说明的是，这些对象、要素和关联类可以直接存储在 g e o d a t a b a s e 中。不用非要存储在要素集中。一个对象类所包含的所有对象的类 型都是相同的。同样，要素类中所包含的所有对象的类型也是相同的。对象类 2 4 第三章g i s 与w 曲g i s 相关原理与技术 和要素类的主要区别在于对象类不包括空间信息，而要素类则包含了空间信息。 关联类顾名思义就是存储关系的。它存储了对象之间、要素之间、或要素和对 象类之间的关联信息。几何网络( g e o m “cn e 觚o r k ) 的主要作用是线性模拟， 比如城市交通网络、电缆沟网络等。它具有强大的网络拓扑跟踪和网络拓扑分 析功能。e s r j 公司推出的舡c g i s 8 3 以及以后的产品都支持网络拓扑功能，这 种拓扑图用于体现各个要素类之间的关联。它主要应用于分析和定义各种几何 类型的要素空间关系。 2 域、属性验证。域( d o m a i n ) 就是一个变量或对象所能允许赋予的合法值，这个 值可以是数字、也可以是日期，这个要根据程序员的定义。属性验证根据程序 员定义的域的范围，来检查该变量或对象的属性值是否合法，增强了数据的完 整性。 3 栅格数据集、栅格。栅格数据集( r a s t e rd a t a s e t s ) 主要用于表现普通的实物照片、 表面、地图某个环境因子采样数据的g r i d 。这些栅格数据具有多个波段。 4 不规则三角形网络数据集。不规则三角形网络数据集( t i nd a t a s e t s ) 是从表面上 采样高程点数据生成的不规则三角形。t 玳可以用于模拟地球表面，同时也可 用于连续性的环境因子的分布研究，比如用户用电分布。 5 地址( a d d r e s s e s ) 、x ，y 定位、邮政编码、位置名称、r o u t e 定位。地址包含很多 定位信息，这样可以利用这些信息创建要素，并且使用地图将这些要素显示。 在真实的世界中，任何物体都是有它特有的形状的，人们利用矢量数据来表 示物体的形状。矢量数据就是物体坐标的几何，但这些坐标是带有属性并且有序 的。心c i n f o 引入了这个概念，将它称为要素( f e a t u r e ) 。我们可以根据矢量数据提 供的几何操作来计算空间物体的长度和面积。同时还可以进行高级计算，比如， 线的相交、面的叠加等。矢量数据根据要素的尺寸分级： 1 点描述的是零维形状的