（信息与通信工程专业论文）地理信息系统中路径分析系统的设计与实现.pdf

国防科学技术大学研究生院学位论文 摘要 近年来，地理信息系统应用领域越来越广，路径分析的功能需求也越来越多，如公安 消防、交通管理、车辆导航等许多领域都有迫切需求。本文对地理信息系统中最短路径分 折系统的重要难题和关键算法进行了实验分析和研究改进。课题在下列方面取得了突破： 1 、出于拓扑关系在地理信息系统中的重要性和复杂性，拓扑构建问题一直是地理信 息系统领域国、内外研究的焦点，本课题根据m a p l n f o 城市道路网的数据特点，对拓扑关 系的断链和拓扑关系生成进行了研究探索，设计了拓扑关系构建的解决方案，成功地实现 了构建过程的商效率，解决了拓扑构建的自动化问题； 2 、对典型的最短路径分析算法进行了实验分析，选择确定了高效的最短路径算法， 实现了最短路径分析功能； 3 、使用v c + + 开发平台集成m a p x 进行二次开发，设计完成了一个高效的、能完全满 足应用需求的路径分析系统； 4 、通过m a p l n f o 的数据转换标准提取已有的地图数据，从最底层探索研究，成功设 计实现了另一套独立于m a p x 的路径分析系统，在地理信息系统的独立自主开发问题上进 行了有益的探索。 目前，课题所实现的系统，已成功投入1 l o 警情处理系统中运行，大大提高了警务单 位的快速反应能力和整体指挥作战能力。 【关键字】：地理信息系统，拓扑，最短路径，m a p i n f o ，d i j k s t r a 算法 第1 v 页 国防科学技术大学研究生院学位论文 a b s t r a c t i nr e c e n t y e a r s ，t h ea p p l i c a t i o n d o m a i no fg 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 ) h a s e x t e n d e di nal a r g ed e g r e e c o r r e s p o n s i v e l y , t h e r ea r em o r ea n dm o r ef u n c t i o nr e q u e s t st op a t h a n a l y s i s a n dt h e r e l a t e da t e a st h a th a v es u c h u r g e n tr e q u i r e m e n t sr a n g ef r o m t h ed e p a r t m e n t so f p u b l i cs e c u r i t y , f i r e f i g h t i n g ，t r a f f i ca d m i n i s t r a t i o nt o v e h i c l en a v i g a t i o na n dm a n yo t h e rs u c h d o m a i n s t h i st h e s i sf o c u s e so nt h er e s e a r c ho fas e r i e s o fi m p o r t a n tp r o b l e m sa n dk e y a l g o r i t h m so f t h es h o r t e s tp a t ha n a l y s i ss y s t e m ，w h i c hi s a ni m p o r t a n tp a r to f9 i s ，a n ds o m e e x p e r i m e n ta n a l y s i sa n di m p r o v e m e n t sh a v eb e e nd o n e i ni t t h ea c h i e v e m e n t sg a i n e df r o mt h i s s u b j e c t c a nb es u m m a r i z e d 够f o l l o w i n g ： 1 、s i n c et h ei m p o r t a n c ea n dc o m p l e x i t yo ft o p o t a x yi ng i s ，t h ep r o b l e mo ft o p o l o g i c a l b u i l dh a sa l w a y sb e e naf o c a lp o i n ti nt h eg i sr e s e a r c hd o m a i nd o m e s t i c a l l ya n da b r o a d b a s e d o nt h ed a t ac h a r a c t e r i s t i co fm a p l n f oc i t yr o a dn e t w o r k ，t h i st h e s i si n v e s t i g a t e st h ec l i pa n d g e n e r a t i o no ft o p o t a x ya n dp r e s e n t sa s o l u t i o ns c h e m eo f t o p o l o g i c a lb u i l d ，w h i c hs u c c e s s f u l l y r e a l i z e st h eh i g he f f n c i e n c yo fw h o l eb u i l dp r o c e s sa n ds o l v e st h ep r o b l e mo f t h ea u t o m a t i o no f t o p o l o g i e a lb u i l d 2 、t h i st h e s i sp e r f o r m se x p e r i m e n ta n a l y s i s0 1 1t y p i c a ls h o r t e s tp a t ha l g o r i t h m s ，t h r o u g h w h i c hi ts e l e c t sa n dd e t e r m i n e st h em o s te f f i c i e n ts h o r t e s tp a t ha l g o r i t h ma n dr e a l i z e st h e f u n c t i o no f t h ea n a l y s i so fs h o r t e s tp a t h 3 、u t i l i z i n gt h ev c + + d e v e l o p m e n tp l a t f o r m t h et h e s i sa c c o m p l i s h e sd e v e l o p m e n t o f p a t h a n a l y s i ss y s t e mb yi n t e g r a t i n gm a p x a n dd e v e l o p sah i g he f f i c i e n tp a t ha n a l y s i ss y s t e m ，w h i c h c a ns a t i s f yt h ea p p l i c a t i o nr e q u i r e m e n t sp e r f e c t l y 4 、t h r o u g hm a p l n f o d a t at r a n s f o r m a t i o ns t a n d a r d ，t h et h e s i se x t r a c t so u te x i s t e dm a pd a t a a n d p e r f o r m sr e s e a r c hw o r k f r o mb o t t o m m o s t b e s i d e s ，i tm a k e sm a n yb e n e f i c i a le x p l o r a t i o n si n t h ea s p e c to f t h ei n d e p e n d e n t d e v e l o p m e n t o f g i sa n ds u c c e s s f u l l yd e v e l o p sa n dr e a l i z e sa n o t h e r p a t ha n a l y s i ss y s t e mi n d e p e n d e n to fm a p x a tp r e s e n t ，t h eg i ss y s t e mr e a l i z e di nt h i st h e s i sh a sc o m ei n t os e r v i c ei nt h ep r o c e s s i n g s y s t e mo f1l oe m e r g e n c ya l e r ta r t di th a sg r e a t l yi m p r o v i n gt h ea b i l i t i e so fq u i c kr e s p o n s ea n d i n t e g r a lc o m m a n d i n g a n df i g h t i n go f p o l i c ea f f a i r sd e p a r t m e n t k e y w o r d s l ：g i s ，t o p o l o g y ，s h o r t e s tp a t h ，m a p l n f o ，d i j k s t r aa l g o r i s m 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：地矍筐皇丞统墅焦金堑丞纽的遮i 土盏塞理： 学位论文作者签名：刮约：目 曰期：口3 年r ，月，尹日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：地理篮! 垦丞统整焦金盘丞练啦遮盐生塞盈 学位论文作者签名：司啦圆 作者指导教师签名 日期：口) 年r ，月缈日 日期：工一年c f 月，仁日 国防科学技术火学研究生院学位论文 图标目录 图2 1 空间信息的栅格表示 图2 2 空间信息的栅格表示 表2 ，1 矢量数据结构和栅格数据结构的比较 表2 2 欧氏平面上实体对象所具有的拓扑和非拓扑属性 图2 3p o n r v r t 结构 图2 4m a p l n f o 的文件格式及数据关联机制 图2 5m a p l n f o 的索引文件格式及数据关联机制 图3 1 m a p x 空阊数据结构 图3 ，2 m a p x 模型结构 图3 | 3 系统整体研究设计流程 表3 1 邻接矩阵和邻接表优缺点比较 图3 4 路段属性信息表 图3 5 路网拓扑关系建立的基本过程流程图 表3 2 拓扑构建效率测试 表4 1 两种最短路径算法测试比较， 图4 1 系统实际应用测试 图4 2 拓扑网络结点与路段数测试 图5 ，l拓扑关系处理静态结构图 图5 2 路径分析系统演示图 第1 l i 页 墙 ! h 孔 控 m 药 拍 如 ” 弘 ” 鸵 娩 的 印 国防科技大学研究生院学位论文 第一章绪论 1 1课题背景 地理信息系统( 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 ) 是管理和研究空间数据的技术系 统，它在计算机软硬件支持下，可以实现对空间数据按地理坐标或空间位置的各种处理、 对数据的有效管理等等；通过对多因素的综合分析，它可以迅速地获取满足应用需要的信 息，并能以地图、图形或数据的形式表示处理的结果36 1 。目前，围绕着这项技术的研究、 开发和应用已经形成了一门交叉性、边缘性的学科，并取得了极大的发展。 g i s 现在已不限于地理学研究和应用的领域，目前己与各行各业和我们的同常生活产 生了千丝万缕的联系，应用领域不断扩大。而网络分析作为g i s 最主要的功能之一，在电 子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要 的作用。 本课题来自“佛山市1 l o 处警系统电子地图子系统”项目，目标是在1 1 0 处警( 警情 处理) 系统中实现路径分析功能，最短路径分析是地理信息系统中网络分析的一个重要内 容。所谓网络分析是运筹学模型中的一个基本模型，它的根本目的是研究、筹划一项网络 工程如何安排，并使其运行效果最好，如一定资源的最佳分配，从一地到另一地的运输费 用最低等。其基本思想则在于人类活动总是趋于按一定目标选择达到最佳效果的空间位 置。这类问题在社会经济活动中不胜枚举，因此在地理信息系统中此类问题的研究具有重 要意义。对地理网络( 如交通网络) 、城市基础设施网络( 如各种网线、电力线、电话线、 供排水管线等) 进行地理分析和模型化，是网络分析的主要目的。 网络分析功能通常包括路径分析、资源分配、连通分析、流分析等，其中最基本的问 题是最短路径问题，它作为许多领域中选择最优问题的基础，在交通网络分析系统中占有 重要地位。从网络模型的角度看，最短路径分析就是在指定网络中两结点问找一条阻碍强 度最小的路径。根据阻碍强度的不同定义，最短路径不仅仅指一般地理意义上的距离最短， 还可以引申到其它的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最 快路径问题、最低费用问题等。具体对于基于g i s 的城市1 1 0 系统来说，当警情发生时， 如何准确地确定报警点位置，自动通知周围有关单位，并快速生成通往现场的最短行车路 线是系统中关键性的问题之一，高效率的实现可以提高快速反应能力和整体指挥作战能 笫i 页 国防科技大学研究生院学位论文 力。 1 2课题研究的重点内容 本课题的重点是设计出实用、高效的路径分析系统，集中于路径算法的效率，从而促 进警务单位快速反应，更有效地打击犯罪，维护社会治安。在实际应用中，路经分析常用 于1 1 0 报警等各种城市应急系统，本课题对地理信息系统中基于城市道路网的最短路径分 析的各项关键技术进行了实验分析和研究改进，完成了一个能完全满足实际应用的系统。 在g i s 中多数网络都是有向带权图1 4 0 1 ，如道路有单双向问题，电流、水流都有方向( 如 果是无向图也可归为有向图的特例) ，且不同的方向可能有不同的权值。将实际的城市道 路网转化到地图的图层中时，必须充分考虑到这些情况，并且应方便于提取弧段和结点的 信息，从而构建出正确的网络模型。另外，g i s 中的数据( 如道路、管网、线路等) 要进行 最短路径的计算，就必须首先将其按点( 即结点) 和边( 即路段) 的关系抽象为图的结构， 这在g i s 中称为构建网络的拓扑关系。本课题的地图数据来源于m a p l n f o 平台m “1 ，鉴于 m a p l n f o 平台的自身特性，要进行最短路径等网络分析，首先需要对m a p l n f o 地图网络进 行拓扑的自动构建，进而实现最短路径分析，因此本课题需要重点研究拓扑的自动构建问 题，以及最短路径分析的实现等关键技术。 在实际应用中，特别是1 1 0 处警等紧急情况处理的应用中，对最短路径分析的实时处 理要求非常高，因此本课题研究的关键和主要技术难点也就集中在如何高效率地进行最短 路径分析，所以，最短路径算法的实现方法等极为重要。本课题在应用传统的路径算法研 究进行设计实现的基础上，结合近年来最短路径领域的一些研究成果，对最短路径算法进 行了一些实验性的探索研究。 1 3 论文组织结构 本论文共分为五章。 第一章是绪论部分，简单介绍课题的背景，主要内容以及论文的组织结构，成果形式 说明。 第2 负 国防科技大学研究生院学竹论文 第二章为地理信息系统的基础原理部分，简单介绍了地理信息系统的发展历史，重点 说明了与研究本课题、开发相关系统有关的g i s 空间数据管理、典型的g i s 拓扑结构等主 要内容，并对系统所涉及的平台m a p l n f o 进行了研究。 第三章为本课题的重要部分，简介了系统的开发方式和设计思想，综述了路径分析系 统需要解决的关键问题，说明了系统的主要功能模块。作为重点，本章详细探讨了如何高 效实现网络拓扑结构自动构建的问题。 第四章为最短路径分析的设计实现部分，作为系统的重要核心和关键点，本章论述了 经典的最短路径算法d i j k s t r a 算法基本思想，并设计实现了这一经典算法，并对d i j i k s t r a 最短路径算法的运行效率实验，分析了执行效率和时间复杂性，提出了改进策略，并对采 用的效率更高的改进的最短路径搜索算法的数据结构、设计实现进行了论述。 第五章介绍了采用独立开发方式，从最底层研究开始，设计实现的另一套路径分析系 统。因为不是本论文的重点，本章简单介绍了设计思想和拓扑问题。 论文最后的结束语部分，总结了本课题的突破点和不足，指明了下一步努力的方向。 第3 负 国防科技大学研究生院学位论文 第二章地理信息系统原理 2 1地理信息系统概述 2 1 1 基础概念 g i s 是计算机科学、地理学、测量学和地图学等多门学科的交叉，它是以地理空间数 据库为基础，采用地理模型分析方法适时提供多种空间的和动态的地理信息，为地理研究 和地理决策服务的计算机技术系统。 从表现形式来看，g i s 表现为计算机软硬件系统，其核心是管理、计算、分析地理坐 标位置信息及相关位置上属性信息的数据库系统。它表达的是空间位置及所有与位置相关 的信息，所以，g i s 又是地球空间实体的再现和综合，其信息的基本表达形式是各科 2 - 维 或三维电子地图。因此。g i s 也可简单定义为用于采集、模拟、处理、检索、分析和表达 地理空间数据的计算机信息系统。 人类的信息中有8 0 与地理位置和空间分布有关，所以g i g 具有非常广泛的应用。目 前，g i s 已经比较成熟地应用于军事、自然资源管理、土地和城市管理、电力、电信、石 油和天然气、城市规划、交通运输、环境监测和保护、1 1 0 和1 2 0 快速反应系统等。 今后，g i s 的应用将在市场分析、企业客户关系管理、银行、保险、人口统计、房地 产开发、个人位置服务等领域得到广泛的应用，这些领域将是g i s 产业发展的新的增长点。 实际上，g i s 的应用将加速度地深入人们的工作和生活的各个方面。 1 1 2 发展历史 从古代文明到现代社会，地理工作者、测绘工作者、航海家都致力于空间数据的收集 整理，制图工作者则以地图的形式表示这些数据。地图作为空间数据的载体长期为航海军 事及现代经济建设服务。 2 0 世纪以来，人们对地形图和各种专题图的需求量迅速增加。发展到5 0 年代，由于 计算机技术的发展，测绘工作者和地理工作者逐渐产生利用计算机汇总各种来源的数掘， 借助计算机处理和分析这些数据，最后通过计算机输出一系列结果作为决策过程的有用 信息。基于“要把地图变成数字形式的地图，便于计算机处理分析”这样的目的，2 0 世 纪6 0 年代，g i s 应运而生。 国外的g i s 研究起步较早。六十年代为最初的开拓发展阶段，此时计算机技术玎始用 第4 页 国防科技大学研究生院学位论文 于地图量算、分析和制作，对地图进行综合分析和输出的系统日益增多。 1 9 6 3 年，p ，f t o m l i s o n 首先提出了“地理信息系统”这一术语，并建立了世界上第 一个实用地理信息系统加拿大地理信息系统( c g i s ) ，用于自然资源的管理和规划，那 时的g i s 尚只注重于空间数据的地学处理。 随后，许多与g i s 有关的组织和机构纷纷建立并开展工作，如美国城市和区域系统协 会( u r j s a ) 在1 9 6 6 年成立，美国州信息系统全国协会( n a s i s ) 在1 9 6 9 年成立，城市 信息系统跨机构委员会( u a a c ) 在1 9 6 8 年成立，国际地理联合会( i g u ) 的地理数据遥 感和处理小组委员会在1 9 6 8 年成立等，并组织了一系列地理信息系统的国际讨论会。 这一时期，地理信息系统软件的研制主要是针对具体的g i s 应用进行算法尚嫌粗糙， 图形功能有限 到七十年代，g i s 得到进一步的巩固发展。世界上许多国家，包括美国、加拿大、英 国、西德、瑞典和日本等国，都对地理信息系统的研究均投入了大量的人力、物力和财力， 研究不同规模、不同专题、不同类型的各具特色地理信息系统。地理数据处理这一地 理信息系统方面的第一本专著也在1 9 7 2 年出版，许多大学也创建了地理信息系统实验室， 大力培养g i s 人才。这一时期，世界上发展了许多功能较强的地理信息系统，出现了大量 的数据库，人机图形交互技术得到发展。但图形功能扩展不大，数据管理能力也较小。 本世界八十年代，随羞计算机技术的迅速发展和普及，地理信息系统逐渐走向成熟， 并在全世界范围内全面推向应用。 九十年代，由于计算机的软硬件得到飞速发展，网络走入千家万户，地理信息系统已 成为许多机构必备的工作系统。社会对地理信息系统认识也普遍提高，国家级乃至全球性 的地理信息系统已成为公众关注的问题，例如：地理信息系统列入美国政府制定的“信息 高速公路”计划，美国副总统戈尔提出的“数字地球”战略也包括地理信息系统。这一阶 段，需求也随之大幅度增加，从而导致地理信息系统应用的扩大与深化。 国内相对起步较晚，自2 0 世纪8 0 年代初开始，以1 9 8 0 年中国科学院遥感应用研究 所成立全国第一个g i s 研究室为标志，经历了准备( 1 9 8 0 1 9 8 5 年，正式提出倡议，开始 组建队伍、组织实验) 、发展( 1 9 8 5 1 9 9 5 年，理论探索和区域性实验研究，并在此基础上 制定国家地理信息系统规范) 、产业化( 1 9 9 6 年以后，地理信息系统得到广泛的关注和研究， 并逐步和国民经济建设相结合，取得了重要的进展和实际应用效益) 3 个阶段。 第5 页 国防科技大学研究生院学位论文 地理信息系统目前已成功地应用到一百多个领域，由于地理信息在人类生活和国民经 济中的重要作用，g i s 在未来的几十年中将保持高速发展的势头，成为i t 高科技领域的核 心技术。例如用g i s 、r s ( r e m o t es e n s i n g ，遥感) 和g p s ( g l o b a lp o s i t i o n i n gs y s t e m ，全 球卫星定位系统) 技术建设数字城市，其中g i s 技术就是核心技术。 数字城市建设包括4 部分内容，即基础设施、电子政务、电子商务及公众信息服务。 而g i s 应用贯穿上述4 个部分和各个层面，从城市基础地理信息数据库到政府空间数据共 享、电子商务物流配送以及基于网络的公众地理信息服务，g i s 都发挥着不可缺少的作用。 从具体的应用来说，g i s 已经广泛应用于构成数字城市的众多行业，如城市规划、城市地 下管网、电力、电信、公安、消防、急救等等方面。 此外。随着g s m 移动通信技术的发展，g i s 的应用范围迅速扩展到人们的r 常生活 中。集成g i s 、g p s 、g s m 的技术已开始广泛应用于车辆安全防范系统和调度系统，为人 们提供车辆反劫防盗、报警、道路指引、医疗救护以及在此系统平台基础上扩展各种电子 商务增值服务。本课题设计的系统就属于这种应用，它是为1 1 0 警情处理进行服务的，并 可扩展到其他应用领域。 以医疗救护为例，当患者向监控中心请求急救时，监控中心可以从g i s 电子地图上查 看到患者的具体位置，并同时搜索最近的急救车辆，让最近的车辆前去接患者。患者进入 救护车后，监控中心可以通过双向通话功能，指导救护车上的医生实施救护治疗，同时通 过g i s 的最优路径功能，给救护车指引道路，使其以最快的速度到达医院或急救中心。而 在救护车行进的过程中，患者的家属可以通过互联网立即上网查询救护车的行进位置及患 者的状态信息。通过g i s ，并结合g p s 和g s m 无线通信及网络，使患者、家属、救护车 及医生之间建立了无缝沟通体系，最终使患者能得到快速、及时的治疗。 2 2地理信息系统空间数据管理 地理信息系统的最主要特点是能以电子地图的形式，直观地表现背景地物信息，并可 傲图文互查、综合分析等。因此，在系统开发的最初阶段，首要的问题就是准备地理信息 数据。信息的获取是一个g i s 建设的首要任务。一个g i s 建设，7 0 以上的工作( 费用) 将花费在空间信息的获取上面。 第6 负 国防科技大学研究生院学位论文 空间数据的获取方式有很多渠道，例如通过数据转换获取各种格式的现有数据 ( d x f e 0 0 m i f 等) 。本课题中应用m a p l n f o 平台，可以根据某些部门标准的原始数据文 件，进行数据格式转换，最终形成m a p l n f o 可以识别的数据格式。 此外还有遥感g p s 数据等商业性数据，通过数字测量形成的纸质地图或坐标点文件。 也可以利用已有的纸质地图，通过扫描仪等设备把图纸信息扫描后以栅格数据结构形式存 储，再经其它图象处理软件进一步处理改善图象质量，如图形拼接、降噪、细化等，并把 栅格数据转换为矢量数据格式。 2 2 1 空间数据库 数据库就是为一定目的服务，以特定的数据存储的相关联的数据集合，它是数据管理 的高级阶段，是从文件管理系统发展而来的。地理信息系统的数据库( 简称空间数据库或 地理数据库) 是某一区域内关于一定地理要素特征的数据集合。目前常用的空间数据库软 件有e s r i a r c s d e ，m a p l n f os p a t i a l w a r e ，o r a c l es p a t i a l 等等。 空间数据的特殊性决定了空间数据库的特殊性； 1 ) 数据量特别大，地理系统是一个复杂的综合体，要用数据来描述各种地理要素， 尤其是要素的空间位置，其数据量往往很大： 2 ) 不仅有地理要素的属性数据( 与一般数据库中的数据性质相似) ，还有大量的空间 数据，即描述地理要素空间分布位置的数据，并且这两种数据之间具有不可分割的联系； 3 ) 数据应用广泛，例如地理研究、环境保护、土地利用与规划、资源丌发、生态环 境、市政管理。 2 2 2 内部数据结构 数据结构( 也称数据模型) 指根据使用上的要求和事物的特征用概念化的语言和示意 图来描述现实世界。它是数据库系统中一种形式化的描述数据与数据间的联系以及有关的 语义约束规则的方法。数据结构可以分为概念结构、逻辑结构和物理结构。概念结构是对 真实世界的抽象，在g i s 中就是如何用点、线、面及其拓扑关系来描述一幅地图；逻辑结 构是对数据结构的抽象，在g 1 s 中就是如何组织、编码和操作点、线、面等地图图元及其 相互闻的拓扑关系；物理结构是对存储装置的抽象。 目前，主要有两类用于空间数据处理的通用数据结构：基于实体的结构( e n t i t y b a s e d m o d e l ) 和基于域的结构( f i e l d b a s e dm o d e l ) 。前者将空间信息表示成离散的、可标识的 第7 页 国防科技大学聊f 究生院学位论文 空间实体。后者处理的是空间分布信息，每种空间分布都可以表示成一个从空间框架 ( s p a t i a lf r a m e w o r k ) 到一属性域( a t t r i b u t ed o m a i n ) 的函数，地形高程、降雨量和温度 的分布就属于这种结构。在进行计算机图形处理中，这两种结构分别转化为矢量( v e c t o r ) 结构和栅格( r a s t e r ) 结构。 栅格结构 栅格结构是最简单最直接的空间数据结构，是指将地球表面划分为大小均匀、紧密相 邻的网格阵列，每个网格作为一个象元或象素由行、列定义，并包含一个代码表示该蒙素 的属性类型或量值，或仅仅包括指向其属性记录的指针。栅格结构是以规则的阵列来表示 空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。 下面的图2 1 包含有河流、山脉等地理实体，它非常形象地解释了空间信息的栅格表示原 理。 图2 1 空间信息的栅格表示【3 9 1 在栅格模型中，空间被规则地划分为栅格( 通常为正方形) 。地理实体的位置和状态 是用它们占据的栅格的行、列来定义的，因此栅格结构也常被称作网格( t e s s e l l a t i o n ) 结 构。空间事物就按其在网格中的行、列和取值来表示。每个栅格的大小代表了定义的空间 分辨率。一般地图是用点、线、面来表达空间事物，在栅格型的数字化地图中，点在网格 中占据一个基本单元，线由一系列单元联结成折线，面也是一系列基本单元的集合。事物 的空间位置就用其在网格中的行号、列号来表示，事物的属性用单元的取值来表示，这样 输入、输出、存储和处理都比较方便。 第8 页 国防科技大学研究生院学位论文 可以看出，栅格数据模型中的空间实体单元不是通常概念上理解的物体，它们只是彼 此分离的栅格。例如，道路作为明晰的栅格是不存在的，栅格的值才表达了路是一个实体。 道路是被具有道路属性值的一组栅格表达的，这条路不可能通过某一栅格实体被识别出 来。 栅格结构的数据结构简单，属性明显，定位隐含，支持影象代数运算，处理位置关系 容易，尤其容易实现多要素的重叠复合运算。栅格结构也可以有效地表示具有高度空间变 异性的地物。另外，栅格数据结构与基于网格的输入( 遥感图象数据、扫描仪数据) 相兼 容，非常有利于与遥感数据直接进行联合空间分析和匹配应用。栅格数据结构的缺点是数 据量大，特别是稀疏的空间数据，要浪费许多存储单元。另外，在栅格结构中，很难描述 空间实体间的拓扑关系，而且很难对单个空间实体进行操 乍。 矢量结构 矢量结构是指通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体，坐 标空间设为连续允许任意位置、长度和面积的精确定义，其精度仅受数字化设备的精度 和数值记录字长的限制，在一般情况下，矢量结构比栅格结构精度高得多。在矢量模型中， 现实世界的要素位置和范围可以采用点、线或面表达，与它们在地图上表示相似，每一个 实体的位置是用它们在坐标参考系统中的空间位置( 坐标) 定义。对于点实体，矢量结构 中只记录其在特定坐标系下的坐标和属性代码。线实体则用一串有次序的坐标表示，对精 度要求高的曲线可用多条很短的直线来拟合，也可用圆弧或更复杂的数学函数和直线混合 起来表示。面则是由线围起来的封闭的不规则多边形。 第9 页 国防科技大学研究生院学位论文 圈2 2 空间信息的栅格表示【” 由上述定义和图示不难看出矢量结构的特点：数据结构更加紧密，所需的存贮空间较 小，精度不受限制，原始地图的精度即是矢量化地图的精度；定位明显、属性隐含，容易 定义和操作单个空间实体，其中其定位是根据坐标直接存储的，而属性则一般存于文件头 或数据结构中某些特定的位置上；矢量数据结构能够进行有效的拓扑编码，便于进行空间 拓扑分析；在进行图形操作时，可以直接利用计算机图形学的许多算法，如长度、面积的 计算，图形编辑、集合变换等，操作效率高，精度高。 其缺点也很明显：图形运算的算法总体上比栅格数据结构复杂的多，有些甚至难以实 现，尤其是数据的编辑、更新和处理比较复杂；不能有效地支持图象代数运算，复合操作 很难实现，且要占用大量的计算时间：在表示具有高度变化的地物时也有困难，定位存取 性能较差，处理拓扑关系( 如相交、包含、邻接等) 相当困难，连续变化的空间数据不能 表示成矢量结构，这些都是矢量结构的不足。 栅格结构和矢量结构的比较 栅格和矢量是两种表达空间事物的基本结构。他们似乎是两种截然不同的空问数据结 构。 栅格结构“属性明显、位置隐含”，而矢量结构“位置明显、属性隐含”。 栅格数据操作总的来说比较容易实现，尤其是作为斑块图件的表示更易于为人们接 受；而矢量数据操作则比较复杂，许多分析操作( 如两张地图的覆盖操作，点或线状地物 国防科技大学研究生院学位论文 的邻域搜索等) 用矢量结构实现十分困难，矢量结构表达线状地物是比较直观的，而面状 地物则是通过对边界的描述而表达。 但无论哪种结构，数据精度和数据量都是一对矛盾，要提高精度，栅格结构需要更多 的栅格单元，而矢量结构则需记录更多的线段结点。 栅格结构在某些操作上比矢量结构更有效更易于实现。 栅格结构除了可使大量的空间分析模型得以容易实现之外，还具有以下两个特点：易 于与遥感相结合。遥感影像是以象元为单位的栅格结构，可以直接将原始数据或经过处理 的影像数据纳入栅格结构的地理信息系统；易于信息共享。在这两种数据结构中，空间信 息都是使用统一的单位表达。在栅格方法中，统一的单位是栅格( 栅格是不可再分的，其 属性用于表达对应位置物体的性质) ，而矢量方法中，统一的单元是点、线和多边形。 这两种结构都有各自的优缺点，下表对它们作了一些比较。 优点 缺点 矢量数据1 数据结构紧凑、冗余度低1 数据结构复杂 2 有利于网络和检索分析2 多边形叠加分析比较 困难 3 图形显示质量好、精度高 栅格数据1 数据结构简单1 数据量大 2 便于空间分析和地表模拟2 投影转换比较复杂 3 现势性较强 表2 1 矢量数据结构和栅格数据结构的比较 两者各有优、缺点，因此在矢量和栅格结构之间选择时应根据实际应用对象的特点来 决定。一般来说，对于大范围小比例的地图，例如自然资源、环境、农业、林业、地质等 区域问题的研究，城市总体规划阶段的战略性布局研究等，使用栅格结构比较含适。而对 于城市的分区或详细规划、土地管理、公用事业管理等方面的应用，矢量结构比较合适。 也可以把两种结构混合起来使用，并在矢量和栅格之间相互转换，或在同一屏幕上同时显 示两种方式的地图等等。 第1 1 页 国防科技大学研究生院学位论文 本课题所处理的主要是城市道路网，地图数据采用了矢量数据结构。 2 3典型的g i s 拓扑结构 g i s 的概念数据模型直接反映了人们对于客观世界的理解。g i s 作为一种信息系统， 是以现实世界为研究目标，以计算机内部的二进制数字世界作为存储载体的。而现实世界 极其复杂，一方面人们希望g i s 包含充足的数据，另一方面又期望从中能方便地选择所需 要的相关数据而撇开其它兴趣不大的数据。这就要求人们以一种高效的数据组织方式，将 两方面的要求兼顾，既尽可能地包含信息( 包括对未来潜在有用的信息) ，又要能方便快 速选取。 因此，在g i s 系统中，如何用地图上的几何对象来表示客观世界中的各种实体，就起 着至关重要的作用。要定义这些对象并研究它们之间的关系，就必然用到拓扑学的理论。 拓扑( t o p o l o g y ) 一词来自于希腊文，意思是“形状的研究”b s o 拓扑学是几何学的 一个分支，它研究在拓扑变换下能够保持不变的几何属性一拓扑属性。例如，在橡皮表面 有一个多边形，多边形内部有一个点。无论对橡皮进行压缩或拉仲，点依然存在于多边形 内部，点和多边形之间的空间位置关系不改变，而多边形的面积则会发生变化。前者则是 空间的拓扑属性后者则不是拓扑属性。拓扑属性描述了两个对象之间的关系，因此又称 为拓扑关系( t o p o l o g i c a l r e l a t i o n ) 。 下表列出了欧几里得平面( e u c l i d e a n p l a n e ) 内的弧( a r c s ) 、环( l o o p s ) 和区域( a r e a s ) 的拓扑和非拓扑特性。 拓扑属一个点在一个弧段的端点 性一个弧段是一个简单弧段( 弧段自身不相交) 一个点在一个区域的边界上 一个点在一个区域的内部 一个点在一个区域的外部 一个点在一个环的内部 一个面是一个简单面( 面上没有“岛”) 国防科技大学研究生院学位沦文 一个面的连续性( 给定面上任意两点，从一点可以完 全在面的内部沿任意路径走向另一点) 非拓扑两点之间的距离 属性一个点指向另一个点的方向 弧段的长度 一个区域的周长 一个区域的面积 表2 ，2 欧氏平面上实体对象所具有的拓扑和非拓扑属性 拓扑在g i s 系统中有两个主要用途：建立数据模型和进行空间分析。 所谓建立数据模型，就是建立点、线、面等空间数据类型并建立其相互关系。空间数 据实际上是一种矢量数据，最简单的是点。通过描述多个点及其连接关系。就定义了线。 进一步，通过描述多条线段连接产生的闭合线，又定义了面。其他的空间对象，如弧、圆 等，只是这三种基本对象的变形。空间对象建立后，还可以进一步定义其相互之间的关系， 这种相互关系被称为“空间关系”，又称为“拓扑关系”。 空间分析则是利用建立好的空间数据，进行有关空间关系的查询、分析、处理等操作。 比如，在城区地图上，通过“点面关系”，可以查询某指定的商业区范围内( 面) 的所有商 店( 点) ：通过“点线关系”，可以查询给定公交线路( 线) 上的所有车站( 点) ；通过“面面” 关系，可以查询与某绿地( 面) 相邻或相近的居民地( 面) 等等。本课题所研究的主要是“点 线关系”。 除了进行上面介绍的简单的空间分析，还可进一步利用拓扑关系，进行更复杂的空间 分析如本课题的路径分析，以及连通分析，资源分配分析等。所以，实现数据的拓扑关系 是一个非常基本的工作，综上所述，空间数据的拓扑关系在地理信息系统中占有极其重要 的地位。 典型的拓扑结构有两种，下文详细介绍。 2 3 1 p o l y v r t 结构( p o l y g o nc o n v e r t o r ) p o l y v r t 结构是由美国计算机图形与空间分析实验室( l a b o r a t o r yf o rc o m p u t e r g r a p h i c sa n ds p a t i a la n a l y s i s ，l c g s a ) 研制的矢量数据结构，是一种以弧段( a r c ) 为基础 的拓扑数据结构。这种数据结构以拓扑关系为基础组织和存储各个几何要素，其特点是 第1 3 页 国防科技大学研究生院学位论文 以点、线、面间的拓扑连接关系为中心，它们的坐标存贮具有依赖关系。它的基本元素 为“弧段”( 或“链段”) 。弧段在两端有结点，并伴有共享该段的左、右两个多边形的标 示，它由任意多个中间点组成。这一拓扑模型的结构如图2 3 所示。 早期的商品化地理信息系统软件如a r c t n f o 等大都采用了这种拓扑关系数据模型。在 拓扑数据模型的基础上，一些软件将空间数据和属性数据分开存放，如8 0 版以前的 a r e i n f o 将位置坐标数据存放在文件系统中，而将拓扑属性和其它属性存放在关系数据库 系统的二维表格中：另一些软件将坐标数据和属性数据统一存放在关系数据库的各种表格 中，一条记录对应一个点、线或面类型的几何要素( 不一定为完整独立的地理要索) 。 图2 3p o l y v r t 结构 p o l y v e r t 结构的主要优点是数据结构紧凑，拓扑关系明晰，系统中预先存储的拓扑 关系可以有效提高系统在拓扑查询和网络分析方面的效率，但也有很多不足： 首先，其对单个地理实体的操作效率不高。由于拓扑数据模型面向的是整个空间区域， 强调的是各几何要素之间的连接关系，另一方面，它对具有完整、独立意义的地理实体作 为个体存在的事实没有足够的重视，因此增加、删除、修改某一地理实体时，将会牵涉到 系列文件和关系数据库表格，这样不仅使程序管理工作变得复杂，而且会降低系统的执 行效率。 其次，该结构难以表达复杂的地理实体。由于拓扑关系组织的要求，一个完整的简单 实体在拓扑关系模型中有时需要被分解为多个几何要素( 比如一条公路本是一个完整的实 第1 4 页 国防科技大学研究生院学位论文 体，但为了记录其拓扑邻接信息，只有对其在与其它公路实体邻接的地方进行分段，这样 一个完整的实体就被分成多个几何要素。所有的实体都进行如此处理，所以我们说拓扑数 据模型是面向整个区域、面向不被分割的几何要素的，而不是面向用户眼中的地理实体) 。 复杂地理实体由多个简单实体组合而成，自然也常常被分解，拓扑数据模型的整体组织特 性注定了它不可能有效地表达这一由多个独立实体构成的有机集合体。 第三，难以实现快速查询和复杂的空间分析。由于在拓扑数据模型中，地理实体被分 解为点、线、面基本几何要素存储在不同的文件和关系表中，因而凡涉及到独立地理实体 的操作、查询和分析都将花费较多的c p u 时间，在大区域的复杂空间分析方面表现得尤为 明显。 第四，局部更新困难，系统难于维护与扩充。由于地理空间的数据组织和存储是以基 本几何要素( 点、弧段和多边形) 为单元进行的，系统中存储的复杂拓扑关系是g i s 工作 的数据基础，当局部一些实体发生变动时，整层拓扑关系将不得不随之重建，这样的系统 牵一发而动全身，在维护和扩充方面需要更多的精力，并且容易出错。 值得说明的是，p o l y v e r t 数据模型也能以面向对象的方式实现，但此时面向的对象 是不被其它要素从中间分割的几何要素，往