（计算机应用技术专业论文）空间数据库空间关系的关键理论研究.pdf

摘要 空间数据库空间关系的关键理论研究 摘要 空间关系是指地理实体之间存在的一些具有空间特性的关系，如拓扑关 系、方向关系和距离关系等，是空间数据组织、查询、分析和推理的基础。 由于空间数据的不确定性、认知的不确定性和空间关系具体分析处理的不确 定性，使得空间关系的不确定性具有多样性和复杂性，不确定的空间关系的 描述和表示及关系模型的建立具有相当大的难度。已有的研究方法无法处理 对象点具有不确定隶属( 含有未知隶属信息) 信息的含糊区域间的空间关 系，为了表示和处理复杂的含糊区域及区域间的多样的空间关系，本课题基 于v a g u e 集和交集模型矩阵等描述和研究了边界和内部区域对象点具有特殊 不确定性质的含糊区域间的空间关系。已有的针对空间对象的空间关系的研 究成果主要集中在空间点对象、线对象和区域对象的空间关系的表示和推理 等方面；对空间网络的研究主要集中在空间网络中移动对象关系、网络结构 与性质及空间网络上移动点查询等方面。没有进一步对复杂的空间网络间的 空间关系进行系统的研究，研究成果无法处理空间网络间的空间关系的表 示、分析和推理等问题。为了弥补已有方法的不足和空白，本论文详细研究 了空间网络间的空间关系表示和空间关系推理等内容。 针对不确定的复杂的含糊区域关系和空间网络间的空间关系，本课题的 创新工作主要集中在以下几点： 1 基于能表示和处理大量不确定信息的v a g u e 集定义了v a g u e 区域、 v a g u e 区域带、无核v a g u e 区域和含核v a g u e 区域等基本概念：分别详细研 究了同一平面和不同平面中的静态与动态的无核和含核v a g u e 区域关系；给 出了无核和含核v a g u e 区域间的动态转变关系，提出了子区域间的蕴含定理 和蕴含算法。 2 为了描述内部含有洞的复杂v a g u e 区域及处理复杂的含洞不规则 v a g u e 区域间的空间关系，将含洞不规则v a g u e 区域分成原子域，研究了原 子域问的空间关系，提出了基于v a g u e 集的区域关系表和子区域关系问的蕴 涵定理和算法；联合原子域关系，给出了含洞不规则v a g u e 区域关系的表示 方法。 3 基于v a g u e 集对v a g u e 方位关系及方位关系和空间区域关系的复合 关联推理进行了详细研究。基于v a g u e 集对v a g u e 方向点和v a g u e 方向空间 哈尔滨理工大学工学博上学位论文 进行了表示和分析，提出了v a g u e 方向关系的交集矩阵表示方法；讨论了 v a g u e 方向关系的动态邻接性，引入了同一推理簇的概念，提出了v a g u e 区 域关系和v a g u e 方向关系的复合关联推理方法。 4 提出了空间网络间的空间关系的谓词关系表示和交集模型表示方 法，详细研究了空间网络间的空间关系模型的特征条件式和蕴涵条件式。 5 提出了空间网络间的空间关系转换图；对空间网络间的空间关系推 理进行了详细研究，提出了空间网络间的空间关系的推理相斥规则和推理蕴 涵规则，基于推理相斥规则和推理蕴涵规则得出了空间网络间的空间关系推 理组合表。 本课题的研究成果为复杂的v a g u e 区域关系和空间网络间的空间关系在 空间数据库中的应用和研究奠定了基础。 关键词空间关系；拓扑关系；方向关系；空间推理；v a g u e 集 r e s e a r c ho n t h e 之 r e l a t i o n s i n k e yt h e o r y o ft h es p a t i a l t h es p a t i a ld a t a b a s e a b s t r a c t t h es p a t i a lr e l a t i o n sa r et h er e l a t i o n sb e t w e e nt h es p a t i a lo b j e c t sw i t hs o m e s p a t i a lc h a r a c t e r i s t i c s ，s u c ha st h et o p o l o g i c a lr e l a t i o n ，t h ed i r e c t i o nr e l a t i o na n d t h ed i s t a n c er e l a t i o ne t c t h e ya l et h eb a s i so ft h es p a t i a ld a t ao r g a n i z a t i o n ，q u e r y , a n a l y s i sa n dt h es p a t i a lr e a s o n i n g 1 1 1 eu n c e r t a i n t yo ft h es p a t i a lr e l a t i o n s a le d i v e r s i t ya n dc o m p l e x i t yb e c a u s eo ft h eu n c e r t a i n t y o ft h es p a t i a ld a t a ，t h e u n c e r t a i n t yo fc o g n i t i v e a n dt h eu n c e r t a i n t yo ft h es p a t i a la n a l y s i s t h e r e p r e s e n t a t i o no ft h ei n d e t e r m i n a t es p a t i a lr e l a t i o n sa n dt h ec o n s t r u c t i o no f t h e s p a t i a lm o d e la r eg r e a td i f f i c u l t t od e a lw i t ht h es p a t i a lr e l a t i o n sb e t w e e nt h e a m b i g u o u sr e g i o n sw i t ht h eu n c e r t a i nm e m b e r s h i pv a l u e s o ft h ep o i n ti nt h e r e g i o n sa n dt oa n a l y z et h ec o m p l e xa m b i g u o u sr e g i o n sa n dt h ea m b i g u o u s r e g m n r e l a t i o n s ，t h i sp a p e l d e s c r i b e da n da n a l y z e dt h ec o m p l e xr e g i o nr e l a t i o n sb e t w e e n t h ea m b i g u o u sr e g i o n sw i t ht h eu n c e r t a i ni n f o r m a t i o nb a s e do nt h ev a g u e s e ta n d t h ei n t e r s e c t i o nm o d e lm a t r i x t h ee x i s t i n gr e s e a r c ho nt h es p a t i a lr e l a t i o n so f t h e s p a t i a lo b j e c t sw e r em a i n l ya b o u tt h er e p r e s e n t a t i o no f t h es p a t i a lr e l a t i o n sa n d t h es p a t i a lr e a s o n i n go ft h es p a t i a lp o i n to b j e c t s ，l i n eo b j e c t sa n dr e g i o no b j e c t s a n dt h er e s e a r c ho nt h es p a t i a ln e t w o r kw e r em a i n l ya b o u tt h er e l a t i o n so ft h e m o v i n go b j e c t si nt h es p a t i a ln e t w o r k ，t h es t r u c t u r ea n dt h ep r o p e r t i e so ft h e n e t w o r ka n dt h eq u e r yo ft h em o v i n go b j e c t si nt h en e t w o r k 1 1 1 er e s e a r c h a c h i e v e m e n to ft h ep r e v i o u sw o r kc a nn o td e a lw i t ht h er e p r e s e n t a t i o n ，a n a l y s i s a n ds p a t i a lr e a s o n i n go ft h ec o m p l e xs p a t i a ln e t w o r k s t or e m e d yt h ed e f e c t so f t h ee x i s t i n gr e s e a r c h ，t h i sp a p e rd i s c u s s e ds y s t e m i c a l l yt h er e p r e s e n t a t i o na n dt h e r e a s o n i n gf o rt h es p a t i a ln e t w o r kr e l a t i o n s t ot h eu n c e r t a i nc o m p l e xa m b i g u o u sr e g i o nr e l a t i o n s a n dt h es p a t i a l n e t w o r kr e l a t i o n s ，t h ei n n o v a t i o nw o r kw e r em a i n l ya sf o l l o w s ： f i r s t l y , t h ec o n c e p t i o n so ft h ev a g u er e g i o n s ，v a g u er e g i o np a r t i t i o n s ， 哈尔滨理工大学工学博士学位论文 v a g u eh o l er e g i o n s ，v a g u ed i r e c t i o np o i n t sa n dd y n a m i ci m p l i c a t i v er e l a t i o n s w e r ed e f i n e db a s e do nt h ev a g u es e t s t h i sp a p e rd i s c u s s e dt h ev a g u er e g i o n r e p r e s e n t a t i o na n dt h ev a g u er e g i o nr e l a t i o n sa b o u tt h ev a g u er e g i o n sw i t hk e r n e l a n dw i t h o u tk e r n e li nt h es a m ep l a n ea n di nt h ed i f f e r e n t p l a n eb a s e do nt h e v a g u es e t s t h ed y n a m i ct r a n s f o r m a t i o nr e l a t i o n sf o rt h ev a g u er e g i o n sw i t h k e r n e la n dw i t h o u tk e r n e lw e r es t u d i e d ，t h ea l g o r i t h ma n dt h et h e o r e mo ft h e r e l a t i o nr e a s o n i n gf o rt h ev a g u es u b r e g i o n sw e r ea l s og i v e n s e c o n d l y , t h er e g i o nr e l a t i o n so ft h ei r r e g u l a rv a g u er e g i o n sw i t hh o l e s w e r ed i s c u s s e dd e t a i l e d l yb a s e do nv a g u es e t s t h ei r r e g u l a rv a g u er e g i o nw i t h h o l e sw a sd i v i d e di n t os o m ea t o m i c r e g i o n sa n dt h es p a t i a lr e l a t i o n so ft h e a t o m i c r e g i o n sw e r es t u d i e ds y s t e m i c a l l y , t h ea l g o r i t h m a n dt h et h e o r e mo ft h e r e l a t i o nr e a s o n i n gf o rt h ev a g u es u b r e g i o n sw e r ea l s og i v e n b a s e do nt h es p a t i a l r e l a t i o n so ft h ea t o m i c r e g i o n s ，t h ei r r e g u l a rv a g u er e g i o nr e l a t i o n sw i t hh o l e s c o u l db ep r e s e n t e d t h i r d l y , t h ev a g u er e g i o n _ r e l a t i o n sa n dt h ed i r e c t i o nr e l a t i o n s w e r e s y s t e m a t i c a l l ya n a l y z e db a s e do nt h ev a g u es e t sw h i c hc a nd e a lw i t hag r e a td e a l o fu n c e r t a i n t yi n f o r m a t i o n b a s e do nt h ev a g u es e t s ，t h ei n t e r s e c t i o nm a t r i c e sa n d t h er e p r e s e n t a t i o nm o d e lo ft h ev a g u er e g i o n sw e r eg i v e n t oh a n d l et h e u n c e r t a i n t yo ft h ed i r e c t i o nr e l a t i o n sw h i c hi sc a u s e db yt h ea m b i g u i t yo ft h e v a g u er e g i o n s ，t h ev a g u ed i r e c t i o np o i f i f sa n dt h ev a g u ed i r e c t i o ns p a c ew e r e d e f i n e db a s e do nt h ev a g u es e t sa n dt h et h ei n t e r s e c t i o nm a t r i c e so ft h ed i r e c t i o n r e l a t i o n sw e r es t u d i e d 1 1 h ed y n a m i ca d j a c e n c yt a b l eo ft h ev a g u ed i r e c t i o ns p a c e w e r eg i v e na n dt h er e l a t e dr e a s o n i n go ft h ev a g u er e g i o nr e l a t i o n sa n dt h ev a g u e d i r e c t i o nr e l a t i o n sw e r es t u d i e da l s o f o u r t h l y , r e p r e s e n t a t i o na n dr e a s o n i n go ft h es p a t i a ln e t w o r kr e l a t i o n sa r e f o c u so fr e s e a r c ho nt h es p a t i a ld a t a b a s e t h er e p r e s e n t a t i o no ft h ep r e d i c a t i o n a n dt h ei n t e r s e c t i o nm o d e lf o rt h es p a t i a ln e t w o r kr e l a t i o n sw e r ed i s c u s s e d s y s t e m i c a l l y t h e c h a r a c t e r i s t i c - c o n d i t i o n - f o r m u l a sa n dt h e i m p l i c a t i o n - c o n d i t i o n - f o r m u l a sw e r ea l s op r e s e n t e d ，f u r t h e r m o r e ，t h et h e o r e ma n dt h e c o r o l l a r yt od i s t i n g u i s ht h es p a t i a ln e t w o r kr e l a t i o n sw e r eg i v e n f i f t h l y ，t o f o r e c a s tt h es p a t i a lr e l a t i o n s ，t h et r a n s f o r md i a g r a m so ft h e s p a t i a ln e t w o r kr e l a t i o n sw e r ea l s op r e s e n t e d t h em e t h o d so ft h er e a s o n i n gf o r t h es p a t i a ln e t w o r kr e l a t i o n sw e r es t u d i e ds y s t e m i c a l l y t h er e a s o n i n ge x c l u d e d r u l e sa n dt h ei m p l i c a t i o nr u l e sw e t ed i s c u s s e d d e t a i l e d l y b a s e do nt h en l l e s t h e r e a s o n i n gc o m p o s i t et a b l 懿w c i ea l s op r e s e n t e d t h ep r o d u c t i o ni n t h i s p a p e rl a yt h ef o u n d a t i o nf o rt h ea p p l i c a t i o n sa n d - r e s e a r c ho ft h ev a g u er e g i o nr e l a t i o n sa n dt h es p a t i a ln e “r kr e l a t i o n s i nt h e s p a t i a ld a t a b a s e y w o r d s t h es p a t i mr e l a t i o n ；t h e t 。p 。l 。g i c a lr c l a t i o n ；t h ed i r e c t i 。n r e l a t i 。n ； v a g u es e t v 哈尔滨理工大学博士学位论文原创性声明 本人郑重声明：此处所提交的博士学位论文空间数据库空间关系的关 键理论研究，是本人在导师指导下，在哈尔滨理工大学攻读博士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包 含他人己发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集 体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 哈尔滨理工大学博士学位论文使用授权书 空间数据库空间关系的关键理论研究系本人在哈尔滨理工大学攻读 博士学位期间在导师指导下完成的博士学位论文。本论文的研究成果归哈尔 滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全 了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有 关部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工 大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或 部分内容。 本学位论文属于 保密口，在3 年解密后适用授权书。 不保密口。 ( 请在以上相应方框内打) 作者签名：李般 导师签名：菩佑季 日期：名o 。7 年夕月日 日期：”r 7 b 第l 章绪论 第1 章绪论 1 1 本课题研究背景、目的及意义 世界上绝大部分信息资源都与地球的空间分布有关。如今，对海量的复 杂的空间信息进行集成、表示、存储、查询、检验、计算、加工和管理越来 越需要地理信息系统( g i s ) 的支持。地理信息系统是计算机科学、地理 学、测量学和地图学等多门学科的综合技术，它在资源的调查、评价和监 测；在城市的管理、规划和市政工程；在空间分析、空间挖掘与空间决策； 在灾害的预测、评估及救助；在地籍管理与土地利用；在林业、农业和渔 业；在考古和环保；在交通、电业、金融和通讯等诸多领域都得到了广泛的 应用。地理信息系统正成为地球信息科学技术的关键，成为地理信息产业的 核心工具。地理信息系统的核心和基础是空间数据库，空间数据库管理的不 仅是地理空间数据，也管理着与其相关的大量非空间信息。其中，对空间关 系的分析和处理是空间数据库的主要功能。目前，针对基本的空间对象( 如 点、线和区域) 的数据信息，已有的空间数据库和地理信息系统具有较强的 数据输入、存储、检索和显示能力，但缺乏对空间关系进行分析和处理的能 力。目前，空间关系理论的研究进展极大的影响着空间数据库的空间查询、 空间分析和空间推理的能力，此外，空间关系表示和分析在制图综合、地图 理解、机器人学和人工智能等领域也具有重要的作用。因此，研究和发展空 间关系的理论成为科学研究的重点和热点，也是本课题工作的主要内容。 空间关系是指地理实体之间存在的一些具有空间特性的关系，如拓扑关 系、方向关系和距离关系等，是空间数据组织、查询、分析和推理的基础。 按从基础到应用的顺序，空间关系的研究可分为空间关系的语义问题、空间 关系描述、空间关系表达、空间关系推理和基于空间关系的查询分析等。空 间分析建立在空间目标位置和属性表达以及目标间复杂空间关系表达的基础 上，若要提高空间分析能力，必须解决空间关系的描述与表达问题。形式化 的空间关系语义描述与表达是设计空间查询语言的关键，是实现有效空间查 询的前提，也是空间分析的基础，它直接影响到空间分析获取的信息量及其 有效性。空间关系描述的基本任务是以数学或逻辑的方法区分不同的空间关 系，给出形式化描述，为构造空间查询语言和空间分析提供形式化工具。定 哈尔滨理工大学工学博士学位论文 性空间关系推理是空间关系理论和应用的一个重要方面，定性空间关系推理 主要是指利用空间对象的空间关系理论，由已知的空间关系推知可能成立的 未知的空间关系。定性空间关系推理的一个重要特征是需要与人的空间关系 认知相符合。近年来，定性的空间关系推理的理论发展得非常迅速，国内外 的各种研究团体和科研单位都对它进行了高度的重视。 空间关系可细分为拓扑关系、方向关系和距离关系等。其中拓扑关系是 指在拓扑变换下的拓扑不变量，即在拓扑变换( 旋转、平移、缩放等) 下保 持不变的空间关系。空间方向关系就是在一定的参考框架下，以一个空间对 象目标到另一个空间对象目标的指向。因而，空间方向关系的定义必须包含 三个要素：参考框架、参考目标和源目标。在拓扑关系和方向关系研究方 面，目前已建立了一些形式化的描述模型，如基于空间逻辑的r c c 模型、4 元组模型、9 元组模型、v 9 i 模型、4 交差模型、锥形法、投影法和方向关 系矩阵等，然而这些模型都是相对独立的，单纯使用这些独立模型来定性表 示空间对象的空间关系和空间分析等操作的精度还有待提高。距离关系是度 量关系的一个主要方面，度量关系是指用度量空间中的某种度量尺度来描述 目标之间的关系，如目标间的距离、远近等。在距离关系方面，目前的研究 热点主要集中在空间数据的距离关系查询方面，对空间数据库的距离关系查 询的研究可分为点查询、范围查询、窗口查询、连接查询和最近邻查询等多 种类型。空间关系表达了空间数据之间的一种约束，其中距离关系对空间数 据的约束最为强烈，而方向关系次之，拓扑关系最弱。通常，距离关系属于 定量关系，拓扑与方向关系则属于定性关系，但是定性的关系和定量的关系 不是绝对的，而是可以相互转化的，在分析复杂的空间关系时，定性的方法 和定量的方法往往需要联合运用。如何表达空间对象的空间特征及其相互关 系是利用g i s 进行地理信息分析，探究现实世界物理意义、空间分布和地 理变化规律的基础。而且，已有的对空间关系的描述和模型大都是各自独立 的，但人们对空间目标间关系的认识通常是同时考虑目标间的拓扑、方向和 距离关系的，因此这种以相互独立的模型来描述有着内在联系的目标间空间 关系的3 个方面是不符合人类认知逻辑的，必须将这些独立的模型结合起来 形成一个统一的空间关系的表达和推理模型。因此，研究分析空间拓扑关 系、方向关系、距离关系和空间关系推理，以及它们的结合有着重要的学术 和应用意义。 当前有关空间数据库的研究成果主要针对确定性空间对象，即要求空间 对象具有精确的空间位置、边界以及确定的空间关系。然而，现实世界中大 第1 章绪论 量的空间对象的位置、形状、边界、大小往往是不确定的，如污染区域、绿 洲分布以及动植物的繁衍地带等等。又由于空间数据信息的获取方式和表现 形式等原因，所得的空间数据往往具有不确定性( 如含糊性、随机性、不完 整性和不精确性等) 。显然，用精确的处理方式去分析不确定的空间数据信 息是远远不能满足需要的，因而，对空间数据信息的不确定性处理在空间数 据库领域具有相当的重要性，必须对空间对象的位置不确定性、属性不确定 性以及空间关系的不确定性的表示和处理作深入研究。由于空间数据的不确 定性、认知的不确定性和空间关系具体分析处理的不确定性，使得空间关系 的不确定性具有多样性和复杂性，不确定的空间关系的描述和表示及关系模 型的建立具有相当大的难度。空间关系的不确定性表现出了空间关系的复杂 性，是现实世界中地理现象或环境复杂性在空间数据库中的具体表现。空间 关系的不确定研究的主要内容包括：不确定性的描述、分析处理方法；不确 定空间关系与精确空间关系的统一描述与处理；不确定性空间关系的推理方 法等【1 l 。当前，有效的分析和处理不确定的空间关系成为设计不确定性空间 数据库和实现智能空间关系查询的关键。 1 2 国内外在该方向的研究现状及分析 空间关系理论的研究与发展正日益受到空间数据库、地理信息系统 ( g i s ) 、人工智能和计算机视觉等相关领域研究者的重视。空间关系的表示、 和分类对于在空间数据库中进行空间检索、空间定位、空间存储以及空间推 理等都是非常重要的。国内外学者对空间关系的研究主要集中在拓扑关系、 方向关系和距离关系等方面，取得了一系列的研究成果，为空间数据的组 织、查询、分析和推理奠定了坚实的基础。 由于空间对象的复杂性、模糊性、动态性和多样性，且国内外学者对空 间关系研究的角度有很大差异，因此，已有的研究成果依据所分析的空间关 系的特点和所用的研究方法又可分为许多类别。例如，若依据空间对象的形 状、大小、位置和内部对象点等要素的确定与否划分，对空间关系的研究可 分为对确定性的空间关系的研究和不确定的空间关系的研究两大类；若依据 空间对象所在空间的维数划分，则可分为2 维平面中的空间对象的空间关系 研究和3 维立体空间中的空间关系研究；若依据目标空间对象的动态与否， 则可分为静态空间对象关系研究和动态空间对象关系研究；若依据目标空间 对象的复杂性划分，又可分为简单空间对象的空间关系研究和复杂空间对象 哈尔滨理工大学工学博士学位论文 的空间关系研究；若依据空间目标对象的组合类别划分，国内外的研究又可 分为单一空间关系分析和组合空间关系分析两类。等等。本节主要以确定性 空间关系和不确定性空间关系为主线，分别对国内外学者在拓扑关系、方向 关系和距离关系等方面所做的工作进行讨论和分析。 1 2 1 空间拓扑关系 1 2 1 1 确定性空间拓扑关系研究 拓扑关系是空间关系中最重要的基本关系，它是空间关系领域中研究的 最深入和最广泛的一类空间关系。两个空间对象间的拓扑关系是指在拓扑变 换下保持不变的空间关系，如空间对象的包含和相接关系。空间拓扑关系是 空间关系中约束较弱的一类，确定性的空间拓扑关系的主要表达方法有区域 连接法、点集拓扑法、拓扑度量参数法和v o r o n o i 图法等。 1 区域连接演算( r c c ) 在定性的空间关系表示和分析中，基于关系代数理论的区域连接演算 ( r c c ) 理论具有重要的地位。r c c 理论是r a n d e l l 等人为了实现定性空间表 示和推理于1 9 9 2 年在c l a r k e 的个体连接演算理论基础上提出来的【2 1 。r c c 理论可由多类逻辑l l a m a 进行表达，该理论中涉及的主要类别为 r e g i o n ，s p a t i a l 和n u l l 2 1 。r c c 理论的基础是一个基本二元关系： c ) ( 读作区域x 和区域y 连接) 。即r c c 理论以空间中的区域为对象，而 不是几何学中的无维度的点，用“连接”来表达空间对象间的基本关系。基于 c 0 ，r a n d e l l 给出了一套基本的二元关系，其定义如表1 1 所示。 表1 - 1基于c ( x ) 定义的二元关系 2 1 t a b l e1 1b i n a r yr e l a t i o n sb a s e d0 1 1c 仅。们 空阃关系空间关系定义 空间关系空间关系定义 l d c ( x , v ) - i 瞰 81 1 p p “p p ( x , v ) a3 z e c ( z , r ) a e c ( z y ) 2 p 伍纠 v z 【0 ( = 力c ( ：19e c 4 x 。v ) c 瓴力 - i 【o 删 3 p p ( x , y ) 琢力人1 p o l on t p p ( x 。v )p p ( x 4 , ) a 1j 砸c ( z 力a e c ( z 。v ) i 4e q ( x o ) p ( x 。f ) 人p ( y 力l li r l ) p ( y 力 5啪)jz p ( z , x ) 人【p ( z 力】 1 2 p p ( x )p p ( y , x ) 6p 0 x l )啡) 八1 p ( x o , ) 人1 p ( y 力1 3t p p l c x )1 1 p p 沙力 7d r ( x o , ) - io ( x , v ) 1 4n t p p 1 g i ，) n 1 1 p p ( y 力 基于r a n d e l l 的r c c 理论，确定性的空间区域关系可分为比较著名的 两类r c c 8 和r c c 5 。r c c 5 所能表示的关系数要少于r c c 8 ，r c c 5 和 第1 章绪论 r c c 8 的关系如图1 1 所示。基于r c c 8 ，g o h n 研究了区域关系之间的动 态关联性，给出了区域关系的概念邻居【3 】，如图1 2 所示。 d 脚p ( ) p p ( x 。v ) 么i e c ( x , v ) 一n t p p ( x o , ) 。夕p f m d ( 淞力p 0 协力t p p o 力 i，n r p p 阮力 p p - l ( x # )e q ( x , y ) d c | 卜唧g 办一p 吣) ，甏_ e 咿) ： 1，如p - l ( x ) t p p l 蛳) n t p p 1 0 力啉) 1p r1 协 图1 - 1r c c 5 和r c c 8 的关系图1 2r c c 8 的连续转换关系 f i g 1 1r c c - 5a n dr c c - 8f i g 1 2c o n t i n u o u sc o n v e r s i o nr e l a t i o no fr c c - 8 g o t t s 等基于c “，) ，) 进一步定义了许多谓词( 例如c o n 、f t p p 、i t p p 、 s p p 和i c o n 等) 来表示和区分具有简单孔洞的实体区域( d o u g h n u t ) 附】。m e g e n h o f e r t 6 】也给出了含洞空间区域间的空间关系表示方法。为了能表 示和分析区域的凸壳关系，g o h n ( 1 9 9 5 ) 7 】等基于r c c 增加了一个基本函数 e o n v ( x ) ，定义了一个有关凸壳区域的新的谓词c o n v ( x ) ，在此基础上给出 了一系列的处理区域的凸壳关系的谓词。g o t t s 和g o h n 等人的研究成果对 r a n d e l l 的r c c 理论是一个很好的补充，极大的增强了用谓词逻辑表达空 间不规则对象关系的能力。但是，传统的r c c 模型不可计数且对空间区域 不能有限的表示，为此，l is a nj i a n g 等致力于从有限的模型中层次性的构 建r c c 模型，取得了良好的效果【s 】。r c c 主要是定义在连续空间中的，为。 了将其应用到离散空间中，近年来，许多学者进一步对其进行了扩展。r o y 。 和s t e l l t 9 】基于连接代数对r c c 5 和r c c 8 的定义进行了修改，扩展了r c c 理论以分析离散空间中的区域关系。l i s a n j i a n g 和y i n gm i n g s h e n g t lo 】基于 “部分”和“连接”这两个基本概念给出了g r c c 理论模型，g r c c 把连续空间 中的r c c 和离散空间中的r c c d 归纳到一个框架下。p h i l p p eb a l b i a n i t l l l 基 于关系语义和拓扑语义进一步发展了r c c 理论，b a l b i a n i 的理论具有更广 泛的适用性。r c c 模型主要是通过逻辑运算来描述拓扑关系，但r c c 模型 仅适合描述空间面目标对象间的拓扑关系，不支持混合维的空间对象的空间 关系操作，对有关点和线目标对象间的空间关系无效。 2 点集拓扑法 点集拓扑法在表示和分析空间对象关系方面具有重要的地位，它具有统 一和简洁的形式，是一种形式化的表达方法。基于点集拓扑学的交集模型是 分析空间对象关系的一个重要方法，交集模型的基本思想是：将空间实体划 哈尔滨理工大学工学博士学位论文 分为几个部分，利用两个实体的各个部分的交集的组合判定空间关系。 e g e n h o f e r 在1 9 9 1 年基于点集拓扑学讨论了点集拓扑关系，利用两个点集对 象的边界( a ) 和内部( o ) 的4 交集组成4 交模型来描述拓扑空间关系【1 2 】。4 交模 型可以较好的描述空间对象之间的连接和包含等拓扑关系，但在描述邻接和 相离等面对象不相交的拓扑关系方面还有较大的缺陷，例如，4 交模型无法 区分交于一点和交于两点或交于一条线段的两个简单多边形的邻接拓扑关 系。e g e n h o f e r 在1 9 9 3 年引进了点集的余( ) ，构造了一个由点集的边界( a ) 、 内部( o ) 、余( 。) 之间的交集组成的9 交模型，以此作为描述两个点集间拓扑空 间关系的框架【1 3 】。设两个空间对象为彳口，则4 交模型可由一个2 x 2 的矩阵表 示如图1 - 3 ( a ) ；9 交模型可由一个3 x 3 的矩阵表示如图1 3 ( b ) 。 。n 雪。彳。n 亨、1厂4 。n 君。 a o n o b 彳。n 妒1 = iit r 4 = 一n b 。i g ana b a | n 矿l l n b 。a n f j【、彳。n 矗。a na ba n f j ( a ) 4 交模型矩阵( b ) 9 交模型矩阵 图i - 34 交模型矩阵和9 交模型矩阵 f i g 1 - 3 4i n t e r s e c t i o n - m o d e l - m a t r i xa n d8i n t e r s e c t i o n m o d e l m a t r i x 相对于4 交模型，9 交模型能区分更多的拓扑关系类型。但e g e n h o f e r 的 交集模型并没有进一步考虑目标对象点集的度量特性，该模型所能描述的空 间关系语义较为粗糙。e g e r t h o f e r 的方法仅仅用空和非空来区分空间对象间 的边界、内部和外部之间相交情况，没有说明相交细节，从而在表示和分析 复杂的空间对象间的关系时具有很大的局限性。c l e m e n t i n i 等人于1 9 9 3 年在 e g e n h o f e r 所定义的四元组基础上运用维数扩展法【1 4 1 ，作为描述两个点集间 拓扑空间关系的框架。c l e m e n t i n i 的方法能够很好地将两个空间目标的交集 是空、点、线或面4 种情况区分开，但在分析诸如具有度量和方位差异的相 离关系和邻接关系等方面依然有很大的不足，依然存在有大量的维数扩展法 所不能区分的拓扑关系。邓敏【1 5 1 在2 0 0 8 年基于空间划分和目标分解的思 想，利用点集( 拓扑学) 理论中的邻域概念详细分析和描述了带孔洞面目标的 点集拓扑分量，层次的分析和区分简单面目标与带孔洞面目标问的拓扑关 系。为了分析和处理由多个点，多条线，多个面所构成的复杂点，复杂线和 复杂面间的空间关系，s c h n e i d e r 等人基于九交模型针对复杂对象空间关系 做了一系列的研究工作 1 6 , 1 7 , 1 8 , 1 9 】。m a r k u ss c h n e i d e r 等人的研究成果极大的增 强了交集模型表示复杂空间对象空间关系的能力，具有较好的应用前景。 第1 章绪论 3 拓扑度量参数法 由于空间对象形体和关系的复杂性，交集模型描述空间关系的能力是有 限的。经典的交集模型描述目标间空间关系主要存在3 个缺点【2 0 】：a ) 外部的 范围太大，9 交模型描述的空间关系较为粗略，不能更准确的描述；b ) 容易 受误差或不确定性的影响；c ) 不适合动态信息分析的需要。为了能综合分 析目标间的各种类型的空间关系信息，一些学者在拓扑关系的基础上纳入度 量信息来表达空间对象间的关系。 e g e n h o f e r 和s h a f t f f 在交集模型的基础上针对线面拓扑关系提出了分割 度和接近度两个度量参数，从而可更精确的分析拓扑关系【2 l 】。s h a f t 蹲【2 2 1 在 1 9 9 8 年将度量关系和拓扑关系相结合进行空间关系的描述，提出了一个线一 面空间关系语义的精细化描述模型，给出了一组描述线目标间拓扑关系的不 变量。但s h a f t f r 等给出的不变量与目标方向关系密切，与拓扑不变量的特性 有时会产生冲突。2 0 0 7 年，n e d a s 和e g e n h o f e r 给出了平面上线与线之间的分 割度量参数( s m ) 和接近性度量参数( c m ) t 2 3 1 ，从而将线线关系进一步细化区 分。但该方法没有从整体上度量目标对象之间的偏离程度，难以综合描述目 标对象间的各种复杂类型的空间关系信息。为了弥卒b c l e m e n t i n i 和s h a d 行等 人方法的不足，邓敏和李志林等在2 0 0 7 年以线目标为研究对象，基于分解与一 组合的思想，提出了一种线线目标空间关系的集成表达方法【2 4 】，在2 0 0 8 年 又进一步研究了线与简单面目标拓扑关系的描述和区分方法【2 5 1 ，给出了线 与面间的1 6 种基本拓扑关系。 为了处理空间关系的多重表达问题，e g e n h o f e r 等人【2 6 】给出了多尺度表 达中区域之间