（地图制图学与地理信息工程专业论文）基于超图的海底地貌数据对象模型研究.pdf

声明 本人郑重声明： 本论文是在导师的指导下，本人独立进行研究工作所取碍的成果，撰写成该 硕士学位论文基于超图的海底地貌数据对象模型研究。 在撰写本论文魄过程中，为了能够及对高质量的完成，我翻阅了许多的专著、 期刊和文献资料，包括g i s 理论方面、g i s 应用方面、数据库方面和编程语言 方面等。在学习研究这些文献资料的基础上，经过本人的组织、整理、设计实践 等工作，完成了本论文的内容。所有被引用的专著和文章都已经列在参考资料里 面，特此对作者们表示感谢，除此之外，本论文中不包含任何未加明确注明的其 他个入或集体已经公开发表或未公开发表的成果。 本人的研究主要内容与成果，应用的关键技术、解决的关键问题等，都已经 详细明确地写在论文中。该部分内容不包含任何其他个人或集体已经公开发表或 未公开发表的成果。 本声明的法律责任由本人承担。 学位论文作者签名：杨斌 2 0 0 5 年1 月4 日 苍勺斌 一 摘要 2 i 世纪是海洋的世纪，g i s 在海洋方面的应用前景将会越来越广阔，对其功能上的要 求也会越来越高。对于海洋g i s 而肓，传统的数据结构和数据模型有很多不足，对它们的 研究是g i s 重要的研究课题之一， 本论文对超图理论、超图数据结构、建模步骤和方法等内容做了深入的研究。并结合 海洋研究和应用的需要，以超图方法和面向对象的方法为指导，展开数据建模工作，详细 地给出了概念设计和逻辑设计方案以及物理实现思路。另外，本文中，还研究了相麻的空 间数据库的存储方案，设计了表基本结构。最后简要探讨了为支持基于超图的海底地貌数 据对象模型而建立空间数据引擎的必要性和可能性。 【芙键词】超图理论，超图数据模型，基于超圈的海底地貌数据对象模型，空间数据引擎 a b s t r a c t 2 1c e n t u r yi sac e n t u r yf o ro c e a n t h ep r o s p e c to f 0 1 s a p p l i c a t i o nj no c c 自ow i l lb eb r i r g h 蛔 a n db r i l 8 b i e r a tt h es a i l l et i m e , t h e r ew i l lb em o r ea n dm o r er e q u i r e m e n t sf o rg i s a sf o rm a r i n e g i s t r a d i t i o n a ld a t as t t u c t t t t c sa n dm o d e l sa d e f i c i e n t , s ot h es t u d yf o rt h e mh a sb e c o m eo n eo f t h em o s t i m p o r t a n tt h e m e s t h i st h e s i sm a k e sas t u d yo ft h eh y p e t g r a p ht h e o r y , t h eh y p e r g ：r a p hb a s e dd a t as t r u c t u r e ， m o d e l i n gp r o c e d u r ea n dm e t h o d i nt e r m so fr e q u i r e m e n t sf o ro c e a ns t u d ya n da p p l i c a t i o n ， m o d e l i n g w o r ki sc a r r i e do u tu n d e rt h ed i r e c t i o no f t h e h y p e r g r a p ha n do b j e c t - o r i e n t e dm e t h o d s ， a n dc o n c e p t u a la n dl o g i c a ld e s i g ns c h e m e sa n di d e a lf o rp h y s i c a lr e a l i z a t i o na r ep r e s e n t e di n d e t a i l w h a t sm o r e t h et h e s i ss t u d i e ss t o r a g es c h e m e sf o rs p a t i a ld a t a b a s ea n d p r e s e n t st h et a b l e s t r u c t u r e f i n a l l y , n e c e s s i t ya n dp o s s i b i l i t yf o rt h es p a t i a ld a t ae n g i n ew h i c hi s t o s u p p o r tt h e o b j e c t - o r i e n t e dm o d e l o f s u b m a r i n et e r r a i nb a s e do n h y p e r g r a p ha r ec o n c i s e l yd i s c u s s e d k e y w o r d s lh y p e r g r a p h ，h y p e z g r a p hb a s e dd a t as t r u c t u r e ，o b j e c t - o r i e n t e dm o d e lo fs u b m a r i n e t e r r a i nb a s e do n h y p e r g r a p h ，s p a t i a ld a t ae n g i n e 同济大学硕士研究生学位论文笫一章绪论 第一章绪论 1 1 研究背景和问题的提出 1 1 1 海洋的重要性 作为一种陆地生物，人类思想中相对于海洋的认识比对土地的认识要肤浅许多。这是 由两方面冈索造成的。客观上，海洋是一层厚达几公里甚至十儿公里的水体和其f 的地层 所组成，它相对掩藏了大多数可见的现象。而在主观上，人类由于不具备在水中生活的器 官，不能直接通过自身的感觉技能获得对水下自然现象的认识。所以，所谓人类征服自然 的一部发展史基本上是与陆地单方面打交道的历史，人类儿千年创造与积累的物质和精神 文明基本上也是一种大陆文明。但人类自有史以来对于来自神秘浩瀚的海洋的诱惑以及由 此引来的探索欲望却从来没有间断和泯灭，中国最早的地理著作山海经就已经把陆地 和海洋并列作为了研究对象。传统的太极阴阳鱼图也可以视为中华文明最初对地球海陆分 布及其相互演化的一种抽象的解释也可理解为对海洋生物生态系统彼此协调演化的形象 认知。或许是由于人类作为一种生命形式，其最初的起源就是来自海洋深处的原始生命现 象，海洋是孕育一切生命包括人类的场所，人类从认识陆地发展到最终探索海洋，开发利 用海洋，获得对海洋全方位深层次的认识，可能是人类自我发展历程上的一个必然回归。 海洋文明将是新世纪新文明的一个重要体现。 海洋在人类意识以及认识上体现出的重要性随若人类历史古往今来的演进越来越突现 出来。无论是在自然界还是社会政治经济领域，海洋的地位日益显若。1 5 到1 6 世纪一系 列重大的自然地理发现，包括美洲“新”大陆的开拓以及地“球”形状的直接证实都和 人类航海技术的进步息息相关。现今全球环境问题的热点如厄尔尼诺和南方涛动的“跷跷 扳”现象，以及由此引发的系列国际性的重大问题也完全是和海洋环境密切相关的。当 今世界的政治经济舞台全球化的趋势在日益加剧。二次大战结束至今，牵涉列国家乃至 撼个民族生存发展的各种重要自然资源已经被雅尔塔协定划定的现有国际边界所限定，激 烈的国际竞争迫使世界各国不约而同地逐渐把目光转向了资源极其丰富的广阔的海洋。 2 一 1 1 2 数字地球与数字海洋 1 9 9 8 年，美国前副总统戈尔在加利福尼亚科学中心举行的演讲中首次提出了“数字地 球”( d i g i t a l e a r t h ) 一个建立在计算科学、丈规模存储器、卫星遥感、宽带网络、互 操作性以及元数据等技术基础之上的新一代信息高速公路。在题为展望2 1 世纪我们这颗 星球的开创性演讲中，戈尔宣称“我们处于一个将滔滔洪水般巨量的原始数据转变为关 j 二我们社会及我们星球可理解的信息的绝好时期。这些数据将不仅仅包含地球的高分辨率 星影像、数字地图和经济、社会与人口信息。如果我们得以成功，它将会在诸如教育、 为可持续未来制定决策、土遗利用规划、农业芽 l 危机处理等方面取得广阔的社会和经济教 益。数字地球t 程使我们敢于承担人为的或自然的灾害，联合起来真面长期的环境挑战。” 在开放式地理信息系统协会( o g c ) 上，戈尔还指出：“我们需要个数字地球，即一种 可以嵌入海璧地理数据的、多分辨率的和三维的地球的表示。可以在其上添加许多与我e j 所处星球有关的数字数据。”如同“信息高速公路”一样，“数字地球”自提出就引起了全 球的广泛关注。实质上“数字地球”就是信息化的地球，它包括全部地球资料的数字化、 网络化、智能化和可视化，其核心思想就是片 数字化手段整体性地解决地球问题，并最人 限度的利用信息资源。“数字地球”如同互联网一样，是通过研究和建设实践不断形成共识， 制定标准和规范需要逐步形成，也就是说是在各行各业、各个地区的信息化的基础上形 成的，包括“数字国土”“数字农业”，“数字海洋”，“数字城市”等领域。 数字地球早已上升为实现国家战略的重要手段我国国家领导人也多次提出要建设我 国的数字地球，而作为“数字地球”的重要纽成部分“数字海洋”毫无疑问也是当前以及 未来的关键工作。 1 1 3 地理信息系统概述 地理信息系统 随着计算机技术和互联网技术的毽速发展，人类正进入以信息化为主的知识经济时代， 信息化的浪潮正在席卷全球。与空间信息相关的数字化和信息化的关键技术就是地理信息 系统。地理信息系统( 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 ) 是一种采集、存储、管 理、分析、显示与应用的计算机系统，是分析和处理海璧地球空间信息数据的通用技术 从实际应用中的作用和地位来看，目前对地理信息系统的认识可归纳为三个相互独立 而又相互关联的观点【1 】： 1 一 1 )地图观点，强调地理信息系统作为信息载体与传播媒介的地图功能。 2 )数据库观点，强调数据库系统在地理信息系统中的重要地位。 3 ) 分析工具观点，强调地理信息系统的空间分析与模型分析功能。 所以g i s 是一门多学科综合的边缘学科，但其核心是计算机科学，基本技术是数据序、 地图可视化及空间分析。g i s 技术把地圈这种独特的视觉化效果和地理分析功能以及般 的数据库操作( 查询和统计分析等) 结合成一体，从而区别于其他的信息系统。成为一门 处理空间信息的现代综合性学科。 地理信息系统的组成 一个典型的地理信息系统应包括三个基本部分：计算机系统硬件、软件、数据和用户。 嗤卜1 地理信息系统的组成 硬件包括各类计算机处理机及其输入输出和网络设备，软件是支持信息的采集、处理， 存储管理和可视化输出的计算机程序系统，鼗据刚包括图形数据和菲图形数据、定性和定 嚣数据、影像数据及多媒体数据等，用户是地理信息系统所服务的对象。数据处于核心地 位，用户通过软件和硬传操纵数据。可见，数据就如同发动机的汽油一般，没有汽浊的发 动机是不能工作的，没有数据就谈不上g i s 。 地理信息系统的基本功能 1 )数据采集与编辑。g i s 的核心是一个地理数据库，所以建立g i s 的第一步就是把 属性及图形数据输入到数据库中。 2 )数据管理。地理数据通过数据采集与编辑以厉，送入到计算机的外存设备上。 4 型塑幽型坐l 兰堂l 3 ) 制图功能。g i s 的最早发展源自于地图制图和地籍管理，冈而g i s 的主要功能之 一是用于地图伟图。 4 ) 空间查询和分析。可以从g i s 目标之间的空间关系中获取派生的信息和新的知识， 用以回答有关空间关系的查询和进行空间分析。 5 ) 地形分析。空间地形起伏变化的数字表示称为数字高程模型( d 酬) 。g i s 提供构 造模型的软件包及地形分析的功能模块。 地理信息系统的发展动态和趋势 近年来g i s 技术发展迅速，其主要的原动力一方面来自应用领域日益广泛和深入对g i s 不断提出新的要求，另一方面，计算机科学的飞速发展为g 1 s 提供了先进的工具和手段， 许多计算机领域的新技术，如面向对象技术、三维技术、图像处理和人工智能技术都可直 接麻用到g i s 中。目前。国际g i s 技术的发展趋势，主要体现在两个方面一是综合 ( i n t e g r a t i o n ) ，二是分化( f r a c t i o n a t i o n ) 。 1 ) 首先是g i s 技术的综合主要表现在与其他信息技术的结合，我们通常所说的“3 s ” 技术，即g i s 、r s ( r e m o t es e n s i n g ) 和6 p s 的一体化，此外g i s 技术又与c a d 、 多媒体、通信、i n t e r n e t 、办公自动化、虚拟现实等多种技术结合，形成了一fj 综合的信息技术。综合已经成为g i s 技术开发莉i 应用的一个重耍方向。表卜l 说 明了g i s 与有关信息的结合。 表卜l 地理信息系统的综合 c a d 即为计算机辅助制图和设计，是- - i 空间设计技术，用以在地球上进行 g i s c a d 各种设计：g i s 是一门空间管理技术。用以管理地球信息。二者结合将为我 们提供一个设计和管理地球信息的工具。 早期的g i s 往往与遥感联系在一起。广义地讲，遥感是g i s 的重要组成部 分，作为g i s 的一种重要信息源。同时，g i s 的应用也提高了遥感数据的提 g i s 一遥感 取和分析能力。随着高精度遥感技术的发展和遥感动态网络的出现，g i s 与 遥感的结合会更加密切。 g p s 被认为是2 l 世纪影响人类社会的1 2 大技术之一。然而，对于进一步的 g i s g p s 应用，g p s 亦离不开g i s ，必须与g i s 相结台。智能化汽车和道路系统( i v h s ) 的建设，则是为6 i s 和g p s 的结合应用的一个范例。 g i s i n t e r n e t8 基于i n t e r n e t 技术的g i s 即w e b g i s 已经成为g i s 技术发展的重要动向， 一 i 技术乖j 嗣珊w 发布空间信息和提供各种应用，是g i s 进入千家万户的重要途径。 - g s 也是一种重要的媒体。g i s 与多媒体结合已经成为现实，在多媒体系统 6 i s 一多媒体 中嵌入g i s 功能，或在g i s 系统增加多媒体功能，极大地增强了二者的功 技术 能。 g i s 一虚拟现 g i s 与虚拟现实技术结合，提高了g i s 恻形显示的真实感和对l 茎l 形的操作性。 实技术 2 ) 其次是分化。g i s 软件的发展经历了从早期的功能处理模块，发展到组件式g i s 和 w e bg i s 的过程。目前，组件式g i s 帮w e b g i s 已经成为许多大型g i s 公司产品的开发方向。 组件式g i s 的最大好处是能够使g i s 功能嵌入其它软什，或将其他软件功能引入到g i s 中 来。i n t e r g r a p h 公司已经进入了组 牛式时代。e s r i 在组件式方蕊作出了叛探索，推出了以 m a p o b j e c t s 为代表的新一代g i s 。m a p l n f o 公司投入巨资开发m a p x ，具有很好的发展前景。 所谓w e h g i s 是g i s 在i n t e r n e t 信息发布、数据共享、交流协作基础之上实现g i s 的在线 查询和业务处理等功能。具体地讲，在榔的任意一个节点上人们可以浏览检索w e b 上的各 种地理信息和进行各种地理空间分析与预测，空间推理和决策等。w e b g i s 已经是当今g i s 技术发展的重要方向，成为g i s 的竞争焦点。世界各大g i $ 专业公司都推出了各自的产晶， 如a u t o d e s k 公司的_ a p g u i d e ，e s r r 公司的i n t e r n e tm a ps e r v e r i n t e r g r a p h 公司的 g e o 赫e d i aw 幽m a p ，m a p l n f o 公司豹p t o s e r v e r c 班及b e n t l e y 公司豹m o d e l s e r v e r d is c o v e r y 等o 3 。 1 1 4 课题的提出 地瑾信息系统( g i s ) 作为支持空阀定位信息数字亿获取，管理和应用的技术体系， 随着计算机技术、空间技术和现代信息基础设施的e 速发展- 在全国经济信息化进程中的 重要性与日俱增。特剐是当今“数字地球“概念的提出，使得人 f j 对g i s 的重要性有了更 深的了解。 科学技术的不断发展，人类认识自然，改造自然的愿望越来越强烈。作为地球上丰寓 的资源一一海洋资源，借助g 1 s 以及其他科学技术，掌握和控制它，更好地为人类使用和 服务成为了今后人类社会发展的一个重要任务，2 1 世纪是海洋的世纪，海洋的研究与管理 在我国可持续发展战略中将占据越来越重要的位置，因此，g t s 在海洋方面的庵用前景将 6 一 一 会越来越广阔，对其功能上的要求也会越来越高。 在这种情况下基于7 0 8 0 年代技术基础上的g i s 系统正面临着巨大的挑战。如g i s 数据的分布式处理、海量空间数据的动态管理，g i s 空间数据的自动综合、顾及时态属性 的g i s 空间版本关联数据的动态计算、综合和管理3 维g i s 的空间建模和矢景一栅格一 体化空间解算模型等。应用的深化对g i g 相关技术又提出了新的要求，最基本的要求则是 g i s 空间数据模型完备性和适应性问题。一般丽言传统的g i s 模型存在如下的问题“： 1 )概念模型没有时态版本定义和分布式对象标识定义等： 2 )一些扩充了时态属性，分布属性的空间逻辑模型与g i s 核心结构难为一体。 3 )面向对象的模型用于g i s 空间模型( 包括概念模型、空间逻辑模型) 虽在一定程 度上解决了一些问题，但缺乏相应的构造空间模型和关系模型的指导模型。 4 )地理要素自动综台所要求的定义、空间关系建立和部分算法在g i s 空间数据模型 的建立中未予充分考虑，难使这些要素成为g i s 空间模型的一部分。 除了上述问题以外，海洋g i s ( m g i s ，m a r i n eg 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 在描述和管理海洋特征及相关数据时存在一些困难，如“： 1 )水深数据与属性数据的关联。海洋里的主要特征是海底山脉和海底。它们没有明 确的边界也就很难把它们与属性数据进行关联。 2 )多分辨率。水深数据的分辨率不是固定的。由于历史上对近海的数据需求较高， 因此近海的数据分辨率高而深海的数据分辨率低。 为了适用于海洋研究和应用环境，在数据模型设计方面，还有很多的地方值得研究和 探索。随着g i s 应用的不断深入，数据模型与数据结构理论和技术的成熟，图形学理论、 数据库理论及其他相关计算机技术的进一步发展，以及科研和工程应用上的需求，新一代 g 1 s 、m g i s 数据模型和数据结构的研究就成了地理信息系统中的重要课题。 本论文作为国家自然科学基金资助项目韵一部分，将会研究应用于海洋环境下的一种 新的数据模型。 7 一 型型幽型坐l 生业l 1 2 论文研究内容和意义 1 2 论文磺究的内容 海洋里的主要特征是海底山脉和海底平原等它们也是海洋g i s 的研究对象。在海洋 g i s 中，水深数据则经常被用为空间分析的基础信息。这些数据也经常被表示成规则格两 ( g r i d ) 和不规则三角网( t i n ) 等。所以，正如上文所提到的基于海洋g i s 应用和分析的 需要，采用一种合适的空闻数据模型来组织海洋信息，描述海底地貌楚本论文的研究霹标。 法国数学家c l a u d eb e r g e d 对圈论进行了推广，于1 9 7 3 年提出了超图( h y p e r g r a p h ) 的概念。另夕 一位法国数学家f r a n c o i sb o u i l l e 在t 9 7 8 年首先提出在制图和模拟中应冀l 超 圈方法的数据结构( h b d s ) 。超图和超图数据结构的提出，为海洋g i s 的空间建模引山了 薪思路。 本论文拟尝试利用超图和面向对象方法对海洋环境的空间表示概念空间数据结构进 行研究和探索。超图模型的基本数据单元有；类、对象元素、类属性、对象元素属性、类 笑系、对象关系。类之间和类对象元素之间可有多种关系这种关系可能是层次性的，也 可是1 f 层次性的。超图类之间的层次关系表示了超i 璺| 类的纵向关系，明晰地展现了面向对 象模型的类继承、联合和聚集等。超图模型的菲层次关系则表示了空闻超圈类的全方位横 向关系。因此基于超图的对象模型所表达的空间关系远较一般的对象模型的数据抽象所 表返的关系丰富。可见，秘崩基子超图的对象模型来表述关系错综复杂的现实 j = 界无疑具 有极大的潜力和优势。 本论文的主要研究内容如下： i )用超图方法来研究和建立海底地貌数据模型，并尝试用以组织海洋特征及相关属 性， 2 )以面向对象的方式来设计这个基于超图的模型，实现其概念设计和逻辑设计以及 物理设计思路，在这过程中，使用一些建模工其来辅助完成部分设计工作。 3 )在关系数据库管理系统中设计该模型的存储方案， 这其中，所涉及蓟的关键理论和技术有： i )超图与超图数据结构 - 8 一 一 2 ) 数字地面模型( 1 ) 1 3 4 ) 和数字高程模型( d 脚) ； 3 )面向对象方法，统一建模语言( 嘶l ) ： 4 ) 空间数据库技术。 1 2 2 论文研究的意义 基丁超图的海底地貌数据对象模型将提供一种崭新的方法来描述海洋特征，这种表述 的优点有： 1 )虑用层次和图形结构，根据拓扑特征米组织海洋特征并关联其属性： 2 )对海洋目标描述的改进和基于拓扑特征的查询，搜索与提取； 3 ) 灵活的子层次表示。 在此，应该提到，论文对于模型研究和设计所展开的上作，目的不在于设计出一个包 容完接的海洋环境信息、海底地貌信息，全面而“完美”的模型。真正的而且作者认为更 为重要的目的在于，以通过设计一个基于超圈的数据对象模型，从而实现一种崭新的方式 来描述海洋特征、增强海洋环境中数据的管理能力等具体的需求作为例子，走通基于超图 方法的对象模型从概念设计一逻辑设计一物理实现以及数据库存储支持的整条路线，表达 其中的建模思想和设计思路，展现超图方法在建模方面的优越性和潜力。 对于超圈模型，现在g 1 s 界的研究还不是很多。丽且，直0 现在g i s 界有关基于超 图模型的g i s 空间数据模型的研究仍然主要是利用超图模型的思想，换句话说，仅建立了 超图模型的概念模型“”。因此，论文的研究上作将会在超图的建模方面做出有菇的探索， 为超图的进一步应用引出新的思路。 。9 旦塑幽些墅l 王型型业 2 1 超图 第二章超图与超图数据结构 超图是离散致学中最复杂的结构。离散数学中的圈其不过是超图的一种特殊情况。 2 ，t 1 起圉的定义 超圈的概念是图的概念的一个扩张。在图g = ( v x ) 中，x 的每一个元素可以看作 是v 的个二元子集，两在超淘中，考虑任意的子集。 定义1 ：设v 2 ( v l ，v 2 ，v p ) 是一个非空的有限集。令x = x l ，x 2 ，x a ) 是v 的q 个子集组成的一个集族，则称二元组h = ( v ，x ) 为一个超图”，若 x ，i = l ，2 ，q 0 一= y p = y l 称为超圈h 的“酚”，日8 x k 称为h 的“秩”，i a , f br ( t t ) ，y 的元素称为t f 的 “顶点”，而j 的元素称为h 的“边”。 顶点和边在图和超图中的用法有所不同，若在超图h 的每一条边元素的数丑相同，则 称h 是一致的。 一个超强也可以用一个图解来表示，用平面上的一些凡何点来代表h 的顶点，若k l 2 - 用一条封闭的线把，的元素围起来；若k l 2 2 ，则用一条曲线连结x ，中的两个顶点； 若k l = l 。则用一条封闭的曲线连结薯中的唯一的一个顶点和它自身。例如：对予超蛰 h = ( v ，x ) ，顶点集v = a ，1 3 ，c ，d ，e ，f ) ，超边集x = f a ，o ，凸，凸，岛岛) 。 毋= a ，b ，c j ，岛= f 1 3 ，e ，d ，e ；，凸= e ，d ，e ，凸= 徊，f ，e 5 = a ，a = e ， f 1 ，其图形表示如图2 1 。 镁设，j l t f ! th = ( v ，r ) 有m 条边，n 个顶点。划超图b l = ( v ，r ) 的入射矩阵( g 。) 如下： 如果 1 0 型型些型丝j 塑堂坚煺 ，7 7e 5 e 1 (i 图2 - i 超图h 的表示 v j p ；，则乜。二l 芒e ，则吩2 0 其中j = 1 ，2 ，m 。 按照定义，超图的每一个项点至少属于一条边，即没有“孤立的顶点”，若超图的任意 两条边均不相同，则称h 是箍单的。若h 的一条边同时含有蕊个顶点，则这弼个顶点称为 邻接；若h 的两条边至少有个公菇顶点，则称这两条边是邻接的：若v ，x ，则称顶 点q 和边x ，是关联的。 如图2 2 ，入射矩阵为a 日。m 2 ，1 2 起匿蛉二都图 a = 11 o1 o o oo 10 oo l0 11 11 0l 0 0 0 0 oo 1o 1o 01 0 o 】1 圈2 - 2 超图h 的入射矩阵 一个超i ! l 也可以用一个二部图来表示。对于超图h = ( v ，x ) 对应的二部豳是指，以h 的顶点集v 和超边集e 作为顶点集，当h 中的v ，x 。时，则= 部图顶点v j 与顶点x ，有边 + 1 l 一 4，一、 旦。，憎， 、牝、， 1 f【lfll j 、 c， 、j - l 。 一 相连。h 对应的二部图用g ( h ) 表示。二部图g = ( v l ，v 2 ；e ) ，其中v 1 = v v 2 = x ， v k 和x 邻接，当且仅当v x 。上面图2 - 1 中的超图h 的二部图表示g ( h ) 如 图2 - 3 所示： 2 2 超图数据结构( h b d s ) 2 - 3 超圈h 的二部图 2 2 1 空间数据结构的基本类型 通用数据结构包含以下基本类型： i ) 层次结构( h i e r a r c h i c a ls t r u c t u r e ) 层次结构即树状结构。主要表达数据元素之间的层次关系，即i 对多( i ：n ) 的 关系。每一层的数据与卜一层中的多个数据元素相关。树状结构中只有一个根结点称 为主人其余若干结点称为成员。 2 ) 关系结构( r e l a t i o n a ls t r u c t u r e ) 在关系结构中，关系表是一个二维数据，数据单元之间是线性关系。实体的层次 关系是用行列来表示的。每一个数据单元只有一个直接前趋和一个真接后继。 关系结构是一个二维结构，建立的二维表称为关系表。一个实体由若干关系组成。 二维表的集合就构成关系结构。 3 1网络结构( n e t w o r ks t r u c t u r e ) 网络结构与层次结构不同，网络结构的成员可以有多个“主人”，羁此是多对多( n ： ，j j|。 ， 、 钆11f。j一、d 、 y ，h卜l叮_=弋 t j 。 ， 素纠n b 、 散_卜1卜a 塑幽型坐l 兰鲤塑燮坠 m ) 的关系。类似在拓扑结构中所使用的多对多的关系。 以上是最常用的数据结构类型。一个地理信息系统的设计，往往采用多种数据结 构的结合。各种数据结构模型尽管已经发展了许多年，而且目前许多g i s 中仍然使用， 但它们在结构方面存在着许多弱点： 1 )以上数据结构，持别是树状结构适合丁反映层次等级信息，网状结构适合丁非等 级、非层次结构，但是事实上并不完全如此，因为一个现象本身会同时存在等级 和非等级的关系。 2 ) 具体数据结构模型总的来说是考虑从属于该数据集的相关关系，但是相关关系集 的元素本身包括了数据和非数据因此必须考虑这一点。对于真正的数据，也 就是说一个由带有特征的数据所组成的集，应该代表其它要素属于同一集或其 它榘的相互关系，而这一点在传统数据结构中无法反映。 3 )关系结构中的关系运算是通过连接运算来实现的，而连接运算的效率较低。关系 中有连接关系的隐含关系，隐含关系在关系表中并没有加以说明。冈此关系表本 身缺乏完摧表达所有关系的能力。 4 ) 空间分析方法一以层次分析作为目标定向的分析层次分析方法本身正在走向 综合化，具有综合的、系统的分析能力。但是以上两种结构对综合分析是很薄弱 的。 从以上的初步分析，可以看出，需要发展一种新的数据结构，超图数据结构研究 就是在这样一个背景下提出来的，它是以目标定向为基础发展起来的数据结构，避免 了上述弱点，开拓了崭新的数据结构的新思路。 2 2 2 超图数据结构的起源 法国巴黎大学f r a n c o i sb o u i l l e 教授上世纪八十年代初向欧洲航天研究发展局提交的超 图数据结构( t h eh y p e r g r a p hb a s e dd a t as t r u c t u r e 一一h b d s ) 报告中提出了新的数据结 构理论。该理论以超圈和数据巢理论为基础，使原有数据结构理论面目一新，引起了国际 上的广泛重视。在b o u i l l e 的倡仪下，在里斯本召开了第一次国际h b d s 会议。1 9 8 1 年在 i c a 东京会议上举行了上作小组会议。这两次会议主要侧重于h b d s 理论与方法的研究。 1 9 8 4 年在美国召开第二届国际h b d s 会议，来自美、欧、亚、澳等州的1 0 0 多位代表提交 了论文报告，内容转向了建立h b d s 数据库。在第三届h b d s 国际研讨会上，除了继续阐 一】3 褂济大学硕士研究生学位论文 第二章超图与超图数据结构 述h b d s 的理论研究以外，不少论文论述了发展专题信息系统、知识库和智能化专家系统 等方面的问题。上世纪9 0 年代在h b d s 实用化方面义有了新的发展：法国全国l ：5 万和 1 ：1 0 万的h b d s 地图数据库1 9 9 2 年完成，美国u s g s 在研制和完成空间数据转换系统 ( s d t s ) 的设计中也应用了h b d s 的概念模型。从整体上讲，一方面h b d s 的实用研究 需要进一步深入，而另一方面它的核心。如概念模型又作为个理论支柱发展了如o o g i s ( 面向对象的地理信息系统) 等新的理论框架。 2 2 3 超图数据结构的基本理论 从超图理论和集理论为基础引进了抽象数据类型( a b s t r a c td a t a t y p e 一一a d t ) 。有4 种抽象数据类型。即 ：= i j j 在此基础上b o u i l l e 把上述关系发展成为h b d s 理论集的4 个基本成分”：类别 ( c l a s s ) ，目标( o b j e c t ) ，属性( a l l d b u t e ) ，联接( l i n k ) 。 ：； 1 i l ：= l ：= 表2 - 1 集合、图和超圈理论的比较 集理论内容h b d s 理论图论支持内容 集( s e t )类别( c l a s s )超图的边缘 要素( e l e m e n t ) 目标( o b j e c t ) 超图的端点 特性( p r o p e r t y ) 属性( a t t r i b u t e )端点，边缘赋值 相关关系( r e l a t i o n s h i p ) 相关( r e l a t i o n )联接( l i n k ) 这里要注意的是，b o u i l l e 由于h b d s 模型没有能够区分存在于现实世界的“实体”与 数据库表达现实世界的“实体”，因此，最近几年阁更加撰括的术语“f e a t u r e ”来覆盏客观 现象与判图实体同样，“e n t i t y ”也用来描述客观现象或者数据库中的实体，或二者兼而 有之。 r d r u g g 教授和崔伟宏教授在1 9 8 6 年和1 9 8 9 年的研究中将f e a t u r e 和e n t i t y 分副 - 1 4 一 作为h b d s 中“c i s ”和“o b j e c t ”的同义词，也就是说将f e a m r e 和e n t i l y 均等地用丁- 奔 观现象及g i s 中的表达式。这种表达方式即是将h b d s 作为一个空间数据结构。它包括6 种抽象数据类型( a d t ) ，即：实体( o b j e c t ) ；类别( c l s ) ；实体属性( a r r i b u t eo f o b j e c t ) ； 类别属性( a t t r i b u t e o f c l s ) ：实体间的连接( l i n kb e t w e e n o b j e c 协) ；类别间的连接( l i n k b e t w e e nc 1 a s s e s ) 。 前面提到，h b d s 既适合于层次结构，也适合于非层次结构。那么h b d s 如何发展 层次和非层次结构模型呢? 超图数据结构的层次结构模型 假设有一棵树( 层次结构) a 。，属于c 的端点是c 。，它是一个从根到结点的指向图( 图 2 - 4 ) a c 图2 - 4 赋以a c 作为反方向。该幽定义为： c = ( c ) ， s = ( c ? c j ) c 2 ，c i 5 c j = c 。c j ) p = 吖c ) e c 2 ，c i c j = c 。，c j ) a c = ( c ，s a c = 每个端点c 是赋以值a j 的集。 图2 - 5 表示的是超图h 。 o 是端点集对每一个端点c i ，端点的 编号为n 。假设，o i 作为o 集的一部分。o 是边( e d g e ) ；o i “是顶点或叫端点，q2 o i ”) 。 图2 5 从图上可以看出，c 被边0 i 所包围，每一个o i “端点具有a p m 值( a i “) 的集( 图2 6 ) 。 其中：a i d m 是端点o i 。的特征值；c 同样具有a 【集该集是与o i m 相对应的，o ，隐含地带 有a i “的特征值。 图2 - 6 ；卜 在h b d s 中，c i 的子集称为类别即c l a s s ；o i m 端点称为类别的目标即o b j e c t ：a i ， 和a i d m 分别称为类别的属性和目标的属性。 b o u i l l e 所发展的h b d s 层次结构模型如图2 - 7 所示。 - 1 6 ，；| 固仨王3 。? 图2 7 超图数据结构的非层次结构模型 在h b d s 中。类别c 可以参加另外一个类别c j 它们之问通过一个或几个i 乱缘联接， 称为相芙。 k 相关可以用砥。来表示，联接用。来表示。两个类别可能有几个联接，其中一个 类别也可能是循环。 这样一个指向的带值的图可以按以下定义： c = t c i ，k = p o = ，k 这里，g 。是多图，是类别的联接，c 是类别l 。是联接。 类别c ，可以参加c j 。这就是多对多的关系( 图2 - 8 ) 。 这种情况是类别循环。这样的弧在h b d $ 中称为“类剐间的联接”a 类别间的联接是 g c ic ； 2 8 1 7 l 。 g c l 堕 _ 堂堂塑堂堂l 墨型必业 通过目标间的联接实现的。这种关系我们不能写成：c 。民。c ，。 只能写成：o i “r ，。o j ”。 这里，o 是目标，o i m 和o j 。之间用弧( a r e ) 来联接，即：r f ( ；r u 4 ) 这个联接称为“目标间的联接”，并形成一个对称的圈。 多联接、超类、超联接和超多联接 多联接( m u l t i l i n k ) 一一在两个类别之间有时超过1 5 个联接。与此同时类别的目 为5 个l i n k m u n l l l n k 幽2 - 9 标可能超过1 5 个不同的关系。因此定义一个 图g c 。 如果在c ；和c j 之间有5 个联接，这是 带有5 个关系的联接。此时该图是多值的简 单的图，而不是多国。图2 - 9 中的上圄可用 下l 璺| 代替。 囡此多联接是一个带有赋值关系的多值的弧。换句话说，多联接可以理解为不同 的类别被相同的关系所联接。这种情况下应该用类的分区( p a r t i t i o n ) 分别来实现。 图2 1 0 表示为两个类别集被同一关系r 所联接。这个被同一关系r 所联接的类 别集称为超类( h y p e r c l a s s ) 。 这个叫类别成分的新超类的端点的联接则成为从一个超类到另一个超类，这样的 联接叫超联接( h y p e r l i n k ) ( 图2 - 1 1 ) 。 超多联接( h y p e r m u l t i l i n k 一一h m l ) 也可称多超联接( m h l ) 。两个超类被两 个以上超联接所联接，叫超多联接( 翻2 - 】2 ) 。它是一个多值的弧。 1 8 - 型塑幽型燮l _ 苎墨婴趔燮l 三十叠曩蕞 图2 - 1 1 超联接 叠五联蕞趣英h c 2 圈2 一l o i h y 辨r 髓u i 吐嘶k 圈2 - 1 2 超多联接 h b d s 结构化属性 属性( a t t r i b u t e ) 是集理论中特性( p r o p e r t y ) 的一个特别方面。 在b o u i l l e 的定义中，类别的属性是指集的特性。目标的属性是被称为目标的要素 特征的特别值。 一个类别可能有若干属性，一个目标的属性可能没有值。这些类别属性和目标属 性同样被超图所结构化。超图结构化的属性是指在超图数据结构下属性的结构化。 可以定义某些特殊盼子集a i 。，妒，a i 。 a i 是类别属性的集：砩是给定属性类别目标a 十的属性值# a i ”是目标所有的属性 值：a l 是，a l “的综合是所有类别、所有目标的所有属性的集a 在h b d s 中属性只有简单属性和复合属性两个基本方面。 简单属性可能属于以下类型之中的一种：一个单值：一个任意维数的矩阵：一个 算法；一个结构。综合属性可能是比较简单的。它是由若干数量的属性组成的一个组， 而组成属于同一类别的属性组，可能是简单的，也可能姓综合的。 t 9 一 同济大学硕士研究生学位论文第二章超圈与超i 璺i 数据结构 2 3 超图的应用 从上面超圈、超图数据结构的相关概念可以看出，超酗不但可以表达数据之问的层次 关系而且可以表示数据之间的横向关系。正由于超图拥有极强的描述能力，所以它被r 泛地应用于强多领域。如：利崩超图研究关系数据库理论，超图在自动化控制中的应用， 超图在g i s 中的应用等。 自从法国数学家c l a u d eb e r g e d 提出超闰的概念、b o u i l l e 提出在制图和模拟中廊用超 图方法的数据结构( h b d s ) 以来，二十多年的时间肉，关于理论以及应用的研究在不断 的进行。已有不少人把超图理论应用于专题信息系统、知识库羊智能化专家系统等方面。 目前，在国内外的地理信息系统领域，关于超图的研究也在不断的深入。 本章小结 本章主要介绍了超图、超图数据结构( h b d s ) 的基本概念以及超图的发展和应用的 情况。 2 0 - 同济大学硕十研究生学位论文 第三章建模的步骤和方法 第三章建模的步骤和方法 广义的模型，就是人们对世界的一种简化了的抽象认识。人类在几千年自身思想意识 的进化过程中，以及对世界的认识不断发展的过程中，自然而然地形成了把复杂的问题加 以适当地简化，去掉一些次要的成分，而把和问题直接相荚的重要部分突出出来进行研究 的方法，也就是当今广泛采用的模型方法。模型方法能够抓住问题的本质和核心有利于 复杂问题的解决。随着科学技术的日益发展模型法的重要性越来越被无数的科学事实所 证实。 在正式探讨基于超图的海底地貌数据对象模型的设计之前，有必要首先研究一下建模 的步骤和方法，选择一个先进的建模技术手段才能达到建模的最终目的。否则建模就 陷于空谈。 3 1 建模的步骤和基本内容 建立模型总是离不开采用一些特定有效的建模方法和步骤的，这是每一次建模工作必 须首先考虑的问题。拿画家写生作画作个比方，写生作画其实就是为现实世界中的一个客 体在画布上建立一个视觉模型的过程，或许可以叫做“视觉艺术建模”过程。这时，画家 往往面对的是一个处在特定条件下的一个复杂的客体，既要再现客体表面的光影明暗和色 调以反映山三维体积感，又要表现客体自身表面组成材