（计算机应用技术专业论文）空间拓扑关系表达方式间的转化与应用.pdf

重庆大学硕士学位论文中文摘要 摘要 在各类信息管理系统中，地理信息系统( g i s ) 是目前发展最快的系统之一，它 是一个有组织的计算机软件和硬件的集合。它可以高效地创建、操作、分析和显 示各种类型的地理或空间参照的数据，它能将图形与数据有机地结合起来，充分 地表达数据的地理图形信息。地理信息系统( g i s ) 在资源调查、评价、管理和监 测，在城市的管理、规划和市政工程、行政管理与空间决策、灾害的评估与预测、 地籍管理及土地利用，在交通、农业、公安等诸多领域得到了广泛的应用。 但是，g i s 中空间分析功能的发展显得比较落后，而空间分析是建立在空间 目标位置和属性表达以及目杯间复杂空间关系表达的基础上，要提高空间分析能 力，必须解决空间关系描述与表达。因此，空间拓扑关系的研究已成为g i s 研究 的重点和热点。结合定性推理、空间推理与人工智能产生的定性空间推理，已成 为人工智能的一个研究热点。近年来，定性空间推理的快速发展，也促进了g i s 的发展，地理信息系统成为定性空间推理最成熟也最广泛的应用领域。因此，研 究、分析、探讨定性空间拓扑关系，对促进地理信息系统的发展有重要的学术和 实用意义。 本文通过研究g i s 中的核心问题 石扑空i 日j 关系，分析了几种空间拓扑关 系表达方式的优劣，并通过分析的结果选择了一种基于层次的空间拓扑关系表达 方式，研究了其他表达方式向其转换的方法，并且研究了这种基于层次的空间拓 扑表达方式的一些应用。 论文首先介绍了定性空间拓扑关系表示的基本概念、研究背景、内容和现状， 确定了论文研究涉及的相关知识领域。 其次研究了空间拓扑关系表示方法，包括n 交集模型( 4 交集，9 交集，维拓 展4 一交集，维拓展9 交集) ，r c c 模型，分类不变量模型，c b m 模型以及h b m 模型，并分析了它们的优缺点，分别给出了其他表示方法向h b m 模型的转换方式。 再次，给出了空间拓扑关系层次组合表，提出了拓扑权值的概念，并给出了 使用拓扑权值的遗传算法框架。 最后，开发了拓扑关系转换及拓扑权值计算系统原型，验证了其现实性和有 效性。 关键词；空间拓扑表示模型，h b m ，拓扑权值，拓扑权值遗传算法 重庆大学硕士学位论文英文摘要 a b s t r a c t i nm a n yk i n d so f i n f o r m a t i o nm a n a g e m e n ts y s t e m ，g i s ( g e o g r a p h m a li n f o r m a t i o n s y s t e m ) i so n eo ft h em o s tq u i c k l yd e v e l o p i n gs y s t e m s i ti sa na r c h i t e c t o n i ca g g r e g a t e o fc o m p u t e rs o f t w a r ea n dh a r d w a r e i tc a ne f f i c i e n t l yc r e a t e ，o p e r a t e ，a n a l y s e sa n d d i s p l a ym a n i f o l dd a t ao fg e o g r a p h yo rs p a c er e f e r e n c e ，c o m b i n eg r a p h i c sa n dd a t a , e x p r e s st h ei n f o r m a t i o no fg e o g r a p h yg r a p h i c s g i s h a sb e e nw i d e l yu s e di nm a n y f i e l d s ， s u c ha sr e s o u r c er e s e a r c h ， e v a l u a t i o n ,m a n a g e m e n ta n di n s p e c t i o n ； c i t y m a n a g e m e n t , p r o g r a m m i n g ，a n dc i t ye n 舀n e e r i n ga d m i n i s t r a t i o nm a n a g e m e n t ，s p e c i a l d e c i s i o n ，d i s a s t e re v a l u a t i o na n df o r e c a s t ，g e o g r a p h i c a lm a n a g e m e n ta n du t i l i z a t i o n ，a n d t r a f f i c ，a 鲥c u l t u r e ，p u b l i cs e c u r i t y , e r e r e l a t i v e l y , t h ed e v e l o p m e n to fs p a t i a la n a l y t i c a lf u n c t i o no f g i si su n s a t i s f a c t o r y m e a n w h i l e ，t h es p m i mt a r g e tl o c a t i o n , a t t r i b u t i o ne x p r e s s i o na n dc o m p l e xs p a t i a l r e l a t i o ne x p r e s s i o nb e t w e e nt w ot a r g e t sp u tt h ef o u n d a t i o no fs p a t i a la n a l y s e s i no r d e r t o i m p r o v et h ec a p a b i l i t yo fs p a t i a la n a l y s e s ，w em u s tf i n das o l u t i o nt h a t c a r l a c c o m p l i s ht h ed e s c r i p t i o na n de x p r e s s i o no fs p a t a a ir e l a t i o n s h i p i nr e c e n ty e a r s t h e d e v e l o p m e n to fs p a t i a lr e a s o n i n gi sg r e a t ，a tt h es a m et i m ei tp r o m o t e st h ed e v e l o p m e n t o fg i st h a th a sb e c o m et h em o s tw i d e l ya n dm a t u r ea p p l i c a t i o nd o m a i no fs p a t i a l r e a s o n i n g h e n c e ，t h es t u d yo ft h es p a t i a lr e l a t i o n s h i pa n dr e a s o n i n gh a v ei m p o r t a n t a c a d e m i ca n dp r a c t i c a lm e a n i n gi na d v a n c i n gt h ed e v e l o p m e n to f g i s t h i s p a p e ra n a l y s e s t h e a d v a n t a g e s a n dd i s a d v a n t a g e sa m o n gt h e s p a t i a l t o p o l o g i c a lr e l a t i o n s h i pm o d e l sb ys t u d y i n g t h e k e yp r o b l e m o f g i s s p a t i a l t o p o l o g i c a lr e l a t i o n s h i p b a s e do nt h er e s u l to fa n a l y s i s ，w ec h o o s eh i e r a r c h y - b a s e d m e t h o da st h ec o m m o nm o d e l ，a n ds t u d yt h em e t h o d so ft h et r a n s f o r m a t i o n so fo t h e r m e t h o d st oh b m a tt h ee n d ，w er e s e a r c ho nt h ea p p l i c a t i o n so fh b m ( h i e r a r c h y - b a s e d m e t h o d ) f i r s t l y , t h i sp a p e ri n t r o d u c e st h eb a s i cc o n c e p t i o n ，i n v e s t i g a t i o nb a c k g r o u n da n d c o n t e n da n da c t u a l i t yo fq u a l i t a t i v es p a t i a lr e p r e s e n t a t i o no ft o p o l o g m a lr e l a t i o n s ，a n d c o n f i r mt h er e l a t e ds t u d yf i e l d s s e c o n d l y , r e p r e s e n t a t i o nm e t h o d sf o rs p a t l mt o p o l o g i c a lr e l a t i o n sa r er e s e a r c h e d ， i n c l u d i n g n - i n t e r s e c t i o n m o d e l ( 4 i m ，9 i m ，d e _ 4 i m ，d e _ 9 1 m ) ，r c cm o d e l ， c l a s s i f i c a t i o ni n v a r i a n tm o d e l ，c b mm o d e l a n dt h i sp a p e ra l s os t u d i e st h em e a n st o t h et r a n s f o r m a t i o nf r o mo t h e rm e t h o d st oh b mb a s e do nt h ea d v a n t a g e sa n d t i 重庆人学硕士学位论文 英文摘要 d i s a d v a n t a g e sa m o n gt h es p a t i a lt o p o l o g g c a lr e l a t i o n s h i pm o d e l s f u r t h e r , h i e r a r c h yr e p r e s e n t a t i o nm e t h o da n dh i e r a r c h yr e a s o n i n gm e t h o do f s p a t i a l t o p o l o g i c a lr e l a t i o n sa r ep r e s e n t e d ，a n dt h em e t h o do ft o p o l o g i c a lw e i 曲ti s r a i s e d ， w h i c hi su s e di nt ot h eg e n e t i ca l g o r i t h m f i n a l l y , a na r c h e t y p a ls y s t o nf o rt h et r a n s f o r mo ft o p o l o g i c a lr e l a t i o n s h i pm o d e l s i sb u i l t ，t o p o l o g i c a lw e i g h ti sc o m p u t e d a n dt h ec o r r e c t n e s so ft h es y s t e mi s v a l i d a t e d k e y w o r d s ：s p a t i a lt o p o l o g i c a lr e l a t i o n s h i pm o d e l s ，h b m ，t o p o l o g i c a lw e i g h t ， t o p o l o g i c a l - w e i g h tg e n e t i ca l g o r i t h m i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆盍堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：砸 签字日期：跏刁年月勿日 学位论文版权使用授权书 本学位论文作者完全了解重迭太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重庆太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 一力。 ( 请只在上述一个括号内打“”) 学位论文作者签名：扶逸 签字日期：笳7 年争月了日 一名：矸彳 签字日嘶6 月j 日 重庆大学硕士学位论文1 绪论 1 绪论 1 1 选题背景与研究意义 地理信息系统( 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 ) ，一般来说， 可定义为用于采集、存储、管理、处理、检索、分析和表达地理空间数据的计算 机系统，是分析和处理海量地理数据的通用技术”【2 】。随着地理信息系统在资源调 查、评价、管理和监测，在城市的管理、规划和市政工程、行政管理与空间决策、 灾害的评估与预测、地籍管理利，在交通、农业、公安等诸多领域的广泛的应用， 学术界与工程界都越来越关注地理信息系统的发展。由于g i s 在生产生活中的适 用性和具有广泛的应用空间，所以它不仅包括了对空间数据的存储、管理还包括 了对空间数据的进一步处理：空间查询与分析，其中空间查询与分析是地理信息 系统( g i s ) 的核心。 空间对象关系是空间查询与分析的基础。空间关系的描述与识别非常重要，一 方面它为地理信息系统数据库的有效建立、空间查询、空间分析、辅助决策等提 供了基础，另一方面可以将空间关系理论应用于地理信息系统查询语言，形成一 个标准的s q l 空间查询语言，从而实现通过应用程序进行空间特征的存储、提取、 查询、更新等。 空间拓扑关系是指在拓扑变换( 旋转、平移、缩放等) 下保持不变的空间关系， 即拓扑不变量。拓扑关系是不考虑度量和方向的空间实体之间的空间关系，由于 拓扑学是研究图形在拓扑变化下不变的性质，拓扑学己成为空间关系研究的基础， 为空间对象间的包含、覆盖、相离、和相接等空间关系的描述提供直接的理论依 据【1 1 ，是g i s 中最重要的一类空间关系。在g i s 中，地理空间中的点、线、面实体 之间存在着各种各样的拓扑关系，表示拓扑关系的数据是空间数据的重要组成部 分。 空间推理是指利用空间理论和人工智能a i ( a r t i f i e i a li n t e l l i g e n c e ) 技术对空间 对象进行建模、描述和表示，并据此对空间对象间的空间关系进行定性或定量分 析和处理的过程。目前，空间推理被广泛应用于地理信息系统、机器人导航、高 级视觉，自然语言理解、工程设计和物理位置的常识推理等方面，并且正在不断 向其他领域渗透，其内涵非常广泛。空间推理的研究在人工智能中占有重要地位。 是人工智能领域的一个研究热点 2 】。地理信息系统是空间推理应用得最为广泛的 领域之一，也是空间推理的研究热点之一3 】 定性空间推理是处理常识性空间知识的一种人工智能方法【3 】，已经成为g i s 的关键技术。由于空间知识本质上是定性的，所以研究空间推理的重点就是研究 l 重庆大学硕士学位论文1 绪论 定性空间推理。定性空间推理是空间推理的重要组成部分，关键问题有两个：一 个是我们怎样去加以表示空阃实体及其相互位置关系，即定性空间表示( q u a l i t a t i v e s p a t i a lr e p r e s e n t a t i o n ) ，另一个是与第一个问题紧密相关的，即是在一定表示方法 下的推理方法即定性空间推理( q u a l i t a t i v es p a t i a lr e a s o n i n g ) h 。这两个关键问题 对空问拓扑关系的表示提出了要求。 由上可知，研究、分析、探讨空间拓扑关系表示方法和定性空间推理技术， 对于提高我国各行业、特别是城市规划、建设、管理与服务的数字化水平，促进 地理信息系统的发展，有着重要的学术和现实意义。 1 2 国内外研究现状 近年来，在拓扑空间关系描述方面，人们已经作了许多工作，对确定性区域 间拓扑关系模型的研究取得了很大进展，也为不确定性区域间拓扑关系的研究奠定 了基础。目前主要有基于逻辑的公理化拓扑理论和传统的数学拓扑两大类方法， 其中最有代表性的是r c c 形式化模型和n 交集模型，另外还有许多学者提出的改 进方法i s 。 g u t i n g 以点集为基础，运用集合运算= 、n ，给出了相等( e q u a l ) ，不相等 ( u n e q u a l ) ，包含( i n s i d e ) ，相离( o u t s i d e ) 和相交( i m e r s e c t ) 等拓扑空间关系的定义【6 】。 p u l l a r 将点集方法加以扩充，运用拓扑学理论中点集的边界( b o u n d a r y ) 和内部 ( i n - t e r r i e r ) 的概念，给出了覆盖( o v e l l a p ) 和相邻( n e i 曲b o r ) 两个关系定义1 7 】。 w a g n e r 定义了相邻、相离、严格包含、相交四种拓扑空间关系胪j 。e g e n h o f e r 和f r a n z o s a 提出了一个四元组表达的拓扑空间关系描述框架 9 1 。e g e n h o f e r 引进了 点集的余，构造了一个由点集的边界、内部、余之间的交集组成的九元组，以此 作为描述两个点集间拓扑空间关系的框架【i o 】。c l e m e n t i n i 等人在e g e n h o f e r 所定义 的四元组基础上，运用维数扩展法( d i m e n s i o ne x t e n d e dm e t h o d ) ，即用两个空间目 标内部与边界之间交集的维数，作为描述两个点集阃拓扑空间关系的框架】。进 一步，他们给出了二维拓扑空间关系的最小集。这种方法形式化地描述了二维空 间目标之间的拓扑空间关系。c l e m i n t i n i 和f e l i c e 基于拓扑分类不变量给出了空间 拓扑关系的分类【”l 。 在国内，拓扑空间关系的描述一直是研究的重点和热点，中科院、国家基础 地理信息中心、浙江大学、武汉测绘科技大学等高校或科研机构都作过大量的研 究，廖士中等人针对基于4 交集模型难以推导出拓扑关系的完备集、概念邻域和 复合表等不足，以拓扑学为基础，提出了n 维实体间拓扑关系完备集的概念，建 立了拓扑关系的闭球模型，基于闭球模型可以直接推导出拓扑关系的完备集、概 念邻域以及复合表，闭球模型比4 交集模型更为简单、有刘乃】。郭薇、陈军提出 2 重庆大学硕七学位论文1 绪论 的基于点集拓扑学的三维拓扑空间关系形式化描述【1 】，潘云鹤等提出的基于 v o r o n o i 图的维扩展法来描述g i s 中的拓扑空间关系【l ”。虞强源、刘大有等人提 出了不确定区域的扩展蛋黄模型【l5 1 。邓敏、冯学智等人提出了利用不同的拓扑不 变量层次表达拓扑关系的形式化模型【l ”。 在拓扑空间关系描述发展的基础上，可将其研究结果应用于空日j 推理，能够 对空间推理的发展产生正向的推动。空间推理是指利用空间理论和人工智能a i ( a r t i f i c i a li n t e l l i g e n c e ) 技术对空间对象进行建模、描述和表示，并据此对空问对象 间的空间关系进行定性或定量分析和处理的过程。空间推理的研究起源于7 0 年代 初，最初是以量空间为研究对象的，多维的并且不能通过单一的纯量充分表示的 空间，只是在近年来才成为知识表示的一个重要领域。由于空间推理的研究对象 的转变，极大地扩展了空间推理的应用领域，使空间推理的理论和应用研究近年 来有了长足的进展。在国外，近年来成立了许多专门从事空间推理方面研究的协 会和联盟，如n c g i a ( n a t i o n a lc e n t e rf o rg e o g r a p h i ca n d m a l y s i s ) ，u s g s ( u s g e o l o # c a ls u r v e y ) ，欧洲定性空间推理网s p a c e n e t 以及匹兹堡大学的空间信息 研究组和慕尼黑大学空间推理研究组等等。国际知名期刊a r t i f i c i a li n t e l l i g e n c e 近 年来发表了许多篇空间推理方面的文章，而且呈逐年增长的趋势。 大量的空间推理文献、近年来召开的国际空间推理学术会议以及i n t e r a c t 网的 空问推理站点都表明，时空推理s t s r ( s p a t i o - t e m p o r a ls p a t i a lr e a s o n i n g ) 、定性空 间推理q s r ( q u a l i t a t i v es p a t i a lr e a s o n i n g ) 和地理信息系统是当前空间推理的研究 热点。地理信息系统成为空间推理最为重要的应用领域之一。 1 3 研究内容 本论文章节安排及主要研究内容如下： 第二章主要研究空间拓扑关系的表示方式以及他们的优缺点。第三章与第四 章是本文的重要章节。第三章先分析了h b m 的优点，然后分别研究了其它各种空 间拓扑关系表达方式向h b m 的转换。第四章先给出了h b m 的组合表，接着提出 了拓扑的权值，给出使用拓扑权值的遗传算法框架。第五章是原形系统的实现。 第六章是总结。 在本文中，所做的研究主要是其他空间拓扑表示方式向h b m 的转换方式，拓 扑权值的提出及使用拓扑权值的遗传算法框架。 3 重庆大学硕十学位论文2 空间拓扑关系表达研究 2 空间拓扑关系表达研究 空间对象之间通常有三大类空间关系：即度量关系、顺序关系和拓扑关系。 对象间空间关系的描述形式各不相同，且对象间的空间关系极为复杂多样，因此 在g i s 种对象i 日j 的空间关系研究是非常必要的，而其中拓扑空间关系是空问关系研 究的重点和难点。 首先从根本上来说，空间拓扑关系是g i s 中不可缺少的一种基本关系。空问拓 扑关系是指在拓扑变换( 旋转、平移、缩放等) 下保持不变的空问关系，即拓扑不 变量。拓扑关系是不考虑度量和方向的空间实体之间的空间关系，拓扑学是研究 图形在拓扑变换下不变的性质，因此拓扑学己成为空间拓扑关系研究的基础，为 空间对象间的包含、覆盖、相离、和相接等空间关系的描述提供直接的理论依据f l 】。 在g i s 中，地理空间中的点、线、面实体之问存在着各种各样的拓扑关系，因此表 示拓扑关系的数据是空间数据的重要组成部分。 其次，空间对象关系是空间查询与分析的基础。空间关系的描述与识别非常 重要：一方面它为地理信息系统数据库的有效建立、空间查询、空间分析、辅助 决策等提供了最基础的关系，另一方面是使空间关系理论应用于地理信息系统查 询语言，形成一个标准的s q l 空间查询语言成为可能。从而通过应用程序进行空间 特征的存储、提取、查询、更新等。 空间拓扑关系如此重要，许多学者在空间拓扑关系领域取得了研究成果，提 出了种类繁多的空间拓扑关系表达方式。为了更好的使用空间拓扑关系以及从中 找出各种表达方式之间的对应关系，我们首先应该对空间拓扑关系的各种表达方 式有充分的了解，因此，本章的主要内容是研究分析现有主要的表达方式，并对 各种表达方式的特性进行分析，为下一步研究打下基础。 2 1 拓扑及拓扑对象 2 1 1 拓扑的概念 拓扑学的英文名是t o p o l o g y ，直译是地志学，也就是和研究地形、地貌相关 的有关学科。 拓扑学是几何学的一个分支，但是这种几何学又和通常的平面几何、立体几 何不同。通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以 及它们的度量性质。拓扑学同对象的度量属性及方位属性等度量性质和数量关系 都无关，举例来说，在通常的平面几何里，把平面上的一个图形搬到另一个图形 上，如果完全重合，那么这两个图形叫做全等形。但是，在拓扑学里所研究的图 4 重庆大学硕士学位论文 2 空间拓扑关系表达研究 形，在运动中无论它的大小或者形状都可以发生变化，而且在拓扑学里没有不能 弯曲的元素，每个图形的大小、形状都可以改变，不讨论两个图形全等的概念， 只讨论拓扑等价的概念。 拓扑等价是比较容易理解且非常重要的一个拓扑性质。比如，尽管圆和方形、 三角形的形状、大小不同，在拓扑变换下，它们都是等价图形，换句话讲，从拓扑 学的角度看，它们是完全一样的。 2 1 2 g i s 中拓扑研究的对象一空间数据 在g i s 系统中，将被地理区域所界定、并具有和它相联系的不同属性或特征 的空间实体，称为空间对象；表示空间对象的数据称为空间数据。空间数据具有 空间相关、时间相关、语义相关的特点，比非空间数据有更高的复杂性。 空间数据记录的是空间实体的位置、拓扑关系和几何特征，这是地理信息系 统区别于其他数据库管理系统的标志：g i s 中的空间数据是指空间物体的位置、形 状和大小等几何特征，以及与相邻物体的拓扑关系。 位置和拓扑特征是地理或空间信息系统所独有的，空间位置可以由不同的坐 标系统来描述，如经纬度坐标、一些标准的地图投影坐标或是任意的直角坐标等。 人类对空问目标的定位一般不是通过记忆其空间坐标，而是确定某一目标与其他 更熟悉的目标问的空间位置关系，而这种关系往往也是拓扑关系，如一所学校位 于哪个路口或哪条街道。 在g i s 中主要有以下空间数据元素【1 7 】：点( p o i n 0 、线( l i n e ) 、面( r e g i o n ) 、 层( l a y e r ) 。它们的层次结构如图2 1 所示。在一个层中，包括面、线、点三类空 间数据类型。其中面由线构成，线由点组成。 图2 1 空间对象的层次结构图 f i g 2 1s p a t i a lo b j e c t sh i e r a r c h y 5 重庆大学硕士学位论文 2 空间拓扑关系表达研究 2 2 空间关系 空间关系是指地理实体问存在的一些具有空间特性的关系【l 引。空间关系形式 化模型的发展是空i 日j 推理、地理信息系统、计算机视觉等领域中的一个非常重要 的主题，越来越受到相关领域研究者的重视。空间关系对于在大型空间数据库中 进行空间检索以及在空间推理中推断新信息都是非常重要的【”l 。 在g i s 中，空间关系包括：度量关系、方位关系和拓扑关系等【l ”。度量空间关 系是用某种度量空间中的度量来描述的对象间的关系，如对象间的距离等。方位 空间关系是用来描述对象在空间中的某种顺序的关系，如前后、上下、左右、东 西南北等。拓扑空间关系是指拓扑变换下的拓扑不变量，如空间对象的相邻和连 通关系。一般说来，对象问的空间关系与目标的维数、形态、大小及其所在空间 的维数有关。各类空间拓扑关系也存在着一定的联系，对象间空间关系的描述形 式各不相同，因此对象间的空间关系是极为复杂多样的。 空间关系表示的基本任务是以数学或逻辑的方法区分不同的空间关系，给出 形式化的表示。其意义在于澄清不同用户关于空间关系的语义，为构造空间查询 语言和空间分析提供形式化工具。 空间对象间的拓扑关系是空间中最基本的关系，构成了空间推理的基本方面， 一些研究者甚至指出，对象间的空间关系与对象本身同等重要，有关拓扑关系的 研究在空问推理中占有重要的地位。 空间关系表示方法分为3 类：定量表示、定性表示、定性与定量结合表示。定 量表示方法是目前g i s 系统中普遍采用的方法。g i s 中，通过空间坐标来定位空 间点对象，通过线段、多边形来表示线和区域。空问数据数据库通过点表、边表 和多边形表来表示点、线及区域间的关系。定量表示的特点是用代数与数值分析 方法进行空间信息分析和处理的基础。如，计算两个空间对象问的距离，计算空 间对象的面积或长度等。然而，大量的空间信息和复杂的空间关系仅用定量方式 来描述是不够的。 定性表示是使用非定量的方法和技术来对空间对象及空间关系进行描述的方 法。大量的空日j 对象及其关系要通过定量的方法来表示它既不可能，也没有必要 而且，对空间对象( 如，山脉、海岸线) 的描述总是在一定程度上的近似表示，而不 可能获得准确值。 近年来，定性表示越来越受到研究者的重视，这与空间关系本质上是定性的【2 0 l 认识相一致。定性表示是空间对象及关系描述在更高层次上的抽象。它以空间对 象的本质特征为主而忽略次要特征，以空间关系的主要方面为主而抛弃一些枝节 的、对解决问题不重要的关系。由于空间问题固有的复杂性和不确定性，空间关 系的表示和推理普遍采用定性的方法【2 ”。定性表示获得的定性信息一方面可以满 6 重庆大学硕士学位论文 2 空间拓扑关系表达研究 足一定的应用需求，另一方面它为进一步更精细的定量表示和处理提供更可靠的 候选集。将定性表示与定量表示结合起来便成为定性与定量结合方法。 目前，空间对象拓扑关系的研究主要集中在两条主线上：( 1 ) 确定性区域间 拓扑关系的研究，主要体现在g i s 和空间推理的相关研究中【2 2 】；( 2 ) 不确定区域的 表示及其分析方法的研究，主要体现在地理分析、图像理解和计算机视觉的相关 研究当中【”j 。 对于确定性区域间拓扑关系模型，主要有基于逻辑的公理化拓扑理论和传统 的数学拓扑【2 2 1 两大类方法，其中最有代表性的是r c c 形式化模型2 5 2 6 1 和n 交集 模型【2 7 1 ，另外还有许多学者提出的改进方法 2 9 3 0 1 。不确定性模型主要有4 类； 精确模型：对确定性空间对象的关系模型进行转化，在一定的约束下处理 不确定性空间对象； 模糊模型：基于模糊集理论，主要建模空间对象间关系的模糊性； 粗集模型：基于粗糙集理论，通过空间对象的上、下近似来处理对象间关 系的不确定性； 概率模型：基于概率理论，主要建模位置和度量不确定性。 拓扑关系表示方法的完备性与互斥性是评价表示方法的主要依据。一种表示 方法称为是完备的，当且仅当该表示方法提供的关系集满足： 任一合理的空间关系都能由该关系集中的元素表示 关系集中的任意元素都唯一表示空间中的一个合理关系 一种表示方法被称为是互斥的，当且仅当该表示方法提供的关系集满足： 关系集中的任一元素不能由关系集中其它元素表示 任一合理的空间关系都能由该关系集合中的元素唯一表示 本章研究空间对象间关系的定性表示，在空间对象关系方面只涉及确定性空 间对象问拓扑关系。 2 3 现有空间拓扑关系表示方法 对空间对象拓扑关系分类，就是采用某种形式化描述模型，将大量的、复杂 的空间对象拓扑关系进行合理的分类，抽象出有限种空间拓扑关系。目前，在这 方面的研究已经取得许多成果。如：e g e n h o f e r 等人提出了4 交集模型和9 - 交集模型， r a n d e l l 等人提出的r c c 形式化模型，c i e m e n t i n i 等人提出的维扩展法和c b m ( c a l c u l u s b a s e dm e t h o d ) 分类法，其中c b m 是至目前为止最小的拓扑关系集。我 们将先说明几个基本概念，再分别研究以上几种拓扑关系表示模型。 2 3 1 几个基本概念 在具体分析空间拓扑关系表示方法之前，为了方便空间拓扑关系表示方法的 7 重庆大学硕士学位论文2 空间拓扑关系表达研究 描述，我们需要对几个常用概念进行定义。 在2 1 1 节中，提出了g i s 中三个基本的空间数据元素：点、线、面，且在g i s 应用中，地理对象通常表示为二维几何对象。因此，在本文中，我们主要考虑二 维空间对象的拓扑关系，因此对点、线、面的定义需要严格化，下面给出三者的 具体定义： 定义2 1 ：( 点) 点是没有空间尺度的表示空间位置或该位置地理要素的空间对象。 规定其拓扑维数为0 。 基于点对象，可以定义其它空间对象： 定义2 2 ：( 线) 线是连续映射f 【o ，l 卜 z 足2 的象，且满足：v t l ，t 2 0 ，1 】，当t 1 t 2 时，f 【t 1 ) f ( t 2 ) 。线没有宽度，约定其拓扑维数为1 。特别，当f ( o ) = f ( 1 ) 时称为简单闭 曲线。 定义2 3 ：( 简单区域) 简单区域指腰2 中规则的有界闭子集，且它的内部、外部均 是连通的，边界为简单闭曲线。规定它的拓扑维数为2 。简单区域在本文中简称区 域。 本文以点、线、区域作为空间基本对象，即： 空间对象= f 点，线，区域) 另外，除了点、线、面的概念之外，我们还要做出其他些约定：如果用p 、 l 、a 分别表示点、线、区域，约定：点的边界卯为空集，线l = f ( 0 ，l 】) 的边界为 轧= f ( o ) ，f f l ) ) ，区域的边界a a 是闭曲线，维数为1 。 定义2 4 ：( 内部) 对象九的内部表示为舻，定义为：九o = 九一觐 定义2 5 ；( 外部) 对象九的外部表示为圹，定义为：扩= z 酽一九 2 3 2 基于点集拓扑学的n 一交集模型 n 交集”模型是建立在点集拓扑学的基础之上的。拓扑学是几何学的一个分 支，它研究的是图形在同胚变化下不变的性质【3 “3 2 1 。拓扑学发展到今天，在理论 上已经十分明显分成了两个分支：代数拓扑学和点集拓扑学。其中，点集拓扑学 已成为g i s 空间关系的理论基础，为空间点、线、面之间的拓扑关系的描述提供了 直接的理论依据。n 交集模型的发展经历了4 - 交集，9 。交集以及在其基础上发展的 维扩展法。 4 交集( 4 i n t e r s e c t i o nm e t h o d ，4 i m ) 1 9 8 8 年，p u l l a r 和e g e n h o f e r t 7 1 首先描述了4 i m 用来分类瓜1 上一维区间对象之间 的拓扑关系。e g e n h o f e r 和f r a n z o s a 根据点集拓扑学的基本理论，在1 9 9 1 年提出 了一个四元组表达的拓扑空间关系描述框架【9 1 ，它通过判断两个空间对象边界和内 8 重庆大学硕士学位论文2 空间拓扑关系表达研究 部产生的四组交集是空( 用0 表示) 与非空( 用1 表示) 来确定。四组交集正好构成 一个2 行2 列的矩阵。 假设有两个空间对象九i 和九2 那么用它们的边界与内部的交集构成的四元矩 阵四元组4 i m 则可以表示： 洲c 札坳= ( 鬣1 旒7 鬣1 患7 ) 其中，觑。指k 的边界，九x o 指九；的内部。具体定义参照定义2 4 。 称m 4 洲( 九l ，k ) 为九l ，九2 间基于4 1 m 的拓扑关系。其中： b ( x ) = 拈：1 2 b ( x ) 称为点集x 的判别函数。 矩阵内的每一项都有空0 和非空l 两种可能性，这样m 4 蹦( x t ，k ) 就有2 4 = 1 6 种组合。见表2 1 表2 1 四元组模型的1 6 种组合及8 个基本的拓扑关系 t a b l e2 11 6c o m b i n a t i o n sa n d8b a s i c a l l yt o p o l o g i c a lr e l a t i o n s i n p so f 4 i m 序号 b ( 魏1 矾2 )b ( 觑i x 0 2 )b n o i 觑2 )b 0 , 。i 九6 2 ) 拓扑关系 0o0o0 d i s j o i n t ll 0 o o t o u c h 2 0ool 无意义 3l o o 1 e q u a l 40lo0 无意义 5l l o 0 无意义 600l1c o u t a i u 7l 01l c o v e r 8o0lo 无意义 9 l0lo 无意义 1 00l0ii n s i d e 1 1ll01 c o v e r b y 1 20ll0 无意义 1 3 ll l 0 无意义 1 40lll 无意义 1 5 ll1 l o v e r l a p 在这1 6 种组合中，有部分组合在几何上是不可能出现的。如，对九i 和九2 均为区 域时，( ：是不可能出现的。4 i m 能够分辨出的区域问空间拓扑关系数目见表 9 重庆大学硕士学位论文2 空间拓扑关系表达研究 2 2 ( a ) 能够分辨出的空间拓扑关系数目见表2 2 ( b ) 。4 i m 在群中包括了所有可能 的由点集交集按函数b ( x ) 确定的拓扑关系，具有完备性，可以很好地描述2 个空间 区域之间的拓扑关系。但是对于其他二元关系，例如线区域间的拓扑关系，则不 能较好的描述。 表2 2 ( a ) 4 i m 中区域间的8 种拓扑关系 嘲 阳嘲 嘲 ： 相离包含被包含相邻相等覆盖被覆盖交叠 d i s j o i n t c o n t a l nr e s i d et o u c h e q u a l c o v b l c o v e r b yo v e r l a p 表2 2 ( b ) 4 1 m 中拓扑关系的数目 t a b l e 2 2 ( b ) s u mo f 4 1 mt o p o l o g i c a lr e l a t i o n s m e t h o d 区域区域线区域点区域线线点线点点合计 4 1 m 81 l 31 6 3 24 3 9 交集( 9 i n t e r s e c t i o nm e t h o d ，9 1 m ) 为提高表达拓扑关系的能力，e g e n h o f e r 等a i 2 8 1 基于4 i m 引进了点集的外部，构 造了一个由点集的边界、内部和外部之间的交集组成的9 交集，称为9 n “： fb ( ：，x ln a 九：) b ( e 3 1n 九j ) b ( 0 x , n 九j ) 1 m 。m c 九- ，如，2 l 言 荛：袅：；言 嘉竺：；善 筹：笔；j 其中，a h 指h 的边界，九x o 指k 的内部，k 指舨外部。具体定义参照定义2 4 ， 定义2 5 。 称m 9 m ( 九i ，x z ) 为x 、y 间基于9 。交集模型的拓扑关系。其中： 鳅，= 器驾 m 9 洲理论上有2 9 = 5 1 2 种组合。排除不可能的组合，如九l 和也均为区域时， o 刁是不可能出现的，表2 ，给出了实际存在的组合数，。- m 中的s 种区域间拓扑 1 0 重庆大学硕士学位论文 2 空间拓扑关系表达研究 关系见表2 4 。 9 i m 通过引进点集的外部，改进了4 i m 的部分不足。但是9 i m 仅仅用“空”与“非 空”来区分两个对象的边界、内部、外部的交集，对区域区域、点点、点线、点 区域的拓扑关系描述仍很有限。如图2 2 所示的关系不能被9 i m 区分，它们有相同 的值。 表2 39 i m 表达的空间拓扑关系数 xy拓扑笑系数 点 点 2 点 线 3 点区域 3 线 线 3 3 线区域 1 9 区域区域 8 水，叫 ；1 匹b 日 图2 2t o u c h 拓扑关系 f i g 2 2t o u c hr e l a t i o n 四元组和九元组的拓扑空间关系描述框架能较好地形式化描述拓扑空间关 系，但在有些情况下它不能区分如两个面状对象有一个公共点和有一条公共边两 种情况( 如图2 2 所示，都属于相邻关系，但在该框架下它们的描述形式都是一样 的) 。为了更好的表示拓扑空问关系，在四元组和九元组的基础上发展了维度扩展 法用于描述四元组和九元组无法描述的拓扑关系。 表2 49 i m 中的8 种区域间拓扑关系 i ：0 ：0 ：1 odl 0101oll0 0lol llol ll l11oloo ol01 0tllololll oolll illloolooli lt l1 l 重庆大学硕士学位论文2 空间拓扑关系表达研究 续上表 相离 包含l 被包含l相邻 d i s j o m t c o n t a i n l i n s i d e t o u c h 相等 e q u a l 覆盖l 被覆盖l 交叠 c o v e i