（计算机软件与理论专业论文）二维空间区域物体反方向关系的研究.pdf

摘要 摘要 随着空间数据库技术的不断发展，定性的空间推理在地理信息系统中 的应用越来越丰富，方向关系研究一直是定性空间推理研究领域的热点， 其应用的复杂性在不断增加，因此有关方向关系推理的理论也在不断地补 充和完善。二维空间区域物体的反方向关系有着十分广泛的应用前景，是 空间推理的重要手段，但目前该反关系的研究还处于起步阶段，没有完整 的理论成果，本文对基于m b r 的反方向关系和基于真实物体的反方向关 系进行了研究和探索。 首先，本文分析了区间代数和矩形代数理论，指出了区间代数表示能 力的不足，把它扩展到了间断区间，总结出了间断区间关系与a l l e n 区间 关系的对应关系，完善了定性空间推理工具。 其次，在基于m b r 的主方向关系模型上，结合反方向关系的定义， 分析了反方向关系的特点；提出了一种将方向关系与矩形关系代数相结合 的方法，很好地将矩形代数良好的计算性质应用于空间方向推理中，简化 了方向推理地难度；总结出了基于m b r 反方向关系的运算方法，求出了 主方向关系和反方向关系的对应表。 最后，分析了m b r 的方向关系模型表示真实物体时存在表现能力不 足的问题，对该模型进行了扩展，提出了基于真实物体的主方向关系模型； 给出了真实物体形状的表示方法；对比了两种模型下物体问方向关系的差 异；提出了基于真实物体反方向关系的求解方法。 以上反方向关系的研究丰富了空间方向关系推理和网络一致性检验的 手段，也为基于形状的反方向关系的深入研究奠定了基础。 关键词空间数据库；主方向关系；反方向关系：最小边界矩形：方向关系 运算 燕山大学工学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p i n go f t h es p a t i a ld a t a b a s et e c h n o l o g y ，t h ea p p l i c a t i o n so f q u a l i t a t i v es p a t i a lr e a s o n i n gi nt h ea r e a so fg e o g r a p h i ci n f o r m a t i o ns y s t e ma r e m o r ea n dm o r er i c ha n dc l o r f u l ，t h ed i r e c t i o nr e l a t i o ns t u d yi so n eh o t s p o ti n t h er e s e a r c ha r e ao fq u a l i t a t i v es p a t i a lr e a s o n i n g ，a n dt h ea p p l i c a t i o n sa l s o b e c o m em o r ea n dm o r ec o m p l e x ，s ot h a t ，t h et h e o r ya b o u td i r e c t i o nr e l a t o ni s a l w a y s r e i n f o r c e d t h er e a s o n i n go fi n v e r s ed i r e c t i o nr e l a t i o no nt w o d i m e n s i o n a lr e g i o n si sv e r yu s e f u li nt h ef u t u r e ，i ti st h ei m p o r t a n tm e a s u r ei n s p a t i a lr e l a t i o n i n ga r e a b u t ，t h es t u d yo ni n v e r s er e l a t i o ni si n c h o a t ea tp r e s e n t a n dt h e r ei sn o tp e r f e c tt h e o r y , s ot h i sp a p e rc a r r i e do ns t u d i e sa n de x p l o r e si n t h ei n v e r s ed i r e c t i o nr e l a t i o n sb a s e do nm b ra n dr e a lo b j e c t s f i r s t l y , t h i sp a p e ra n a l y s e dt h et h e o r yo fi n t e r v a la l g e b r aa n dr e c t a n g l e a l g e b r a ，p o i n t e do u tt h ed i s a d v a n t a g eo fi n t e r v a la l g e b r ai ne x p r e s s i o n ，a n d e x t e n d e di tt od i s c o n n e c t e di n t e r v a l ，s u m m a r i z e dt h er e l a t i o n sb e t w e e n d i s c o n n e c t e di n t e r v a lr e l a t i o n sa n di n t e r v a lr e l a t i o n s ，t h et o o l si na r e ao f q u a l i t a t i v es p a t i a lr e a s o n i n gh a v eb e e np e r f e c t e d s e c o n d l y , w i t ht h ed e f i n i t i o no fi n v e r s ed i r e c t i o nr e l a t i o n , t h i sp a p e r a n a l y s e di t sc h a r a c t e r i s t i c sb a s e do nt h ec a r d i n a ld i r e c t i o nr e l a t i o nm o d e lo f m b r ，am e t h o dh a sb e e np u tf o r w a r db yc o m b i n i n gt h et h e o r yo fi n t e r v a l a l g e b r aa n dr e c t a n g l ea l g e b r a t oe x p r e s sc a r d i n a ld i r e c t i o nr e l a t i o n su s i n gt h e r e c t a n g l ea l g e b r ao fp r o j e c t i v ei n t e r v a l s t h i sm e t h o di si nf a v o ro fd i r e c t i o n r e l a t i o n sr e a s o n i n go p e r a t i o na n dr e d u c i n gt h ed i f f i c u l t ya n dc o m p l e x i t yo f c a r d i n a ld i r e c t i o nr e l a t i o n sr e a s o n i n g w es h o w e do u rm e t h o do fc o m p u t i n gt h e i n v e r s ed i r e c t i o nr e l a t i o n sb a s e do nm b ra n dr e p r e s e n t e dt h et a b l eo fc a r d i n a l d i r e c t i o nr e l a t i o n sa n di n v e r s ed i r e c t i o nr e l a t i o n s f i n a l l y ，t h i sp a p e rs t u d i e dt h ep o w e rl i m i t i o n si ne x p r e s s i n gr e a lo b j e c t so f a b s n a c t t h em o d e lb a s e do nm b r ，a n de x t e n d e dt h i sm o d e l ，t h em o d e lo fc a r d m a l d i r e c t i o nr e l a t i o nb a s e do nr e a lo b j e c t sh a sb e e nc r e a t e d ；t h ew a yh o wt o e x p r e s st h es h a p ei sg i v e n ；t h i sp a p e rc o m p a r e dt h ed i f f e r e n to fo n e s d i r e c t i o nr e l a t i o n sb e t w e e nm b rm o d c la n dr e a lo b j e c t sm o d e l ；a n dr e s e a r c h e d t h ep r o c e d u r eo f c o m p u t i n gt h ei n v e r s ed i r e c t m nr e l a t i o n s t h ea b o v er e s e a r c ho fi n v e r s ed i r e c t m nr e l a t i o ne n r i c h st h em e a s u r eo f c a r d i n a ld i r e c t i o nr e l a t i o n s r e a s o n i n g a n d c o n s i s t e n c yc h e c k i n g ，a n d i t e s t a b l i s h st h ef o u n d a t i o nf o rf a r t h e rr e s e a r c ha b o u ti n v e r s ed i r e c t i o nr e l a t i o n b a s e do no b j e c t ss h a p e k e y w o r d ss p a t i a ld a t a b a s e ；c a r d i n a ld i r e c t i o nr e l a t i o n s ；i n v e r s ed i r e c t i o n r e l a t i o n s ；m i n i m u mb o u n d a r yr e c t a n g l e ；o p e r a t i o no f d i r e c t i o n r e l a t i o n s i i i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文二维空间区域物体反方 向关系的研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立 进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人 和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承 担。 作者签字! 参与_ 7 毳日期：声。辱钥学日 作者签字参与套 日期：弘。辱钥学日 燕山大学硕士学位论文使用授权书 二维空间区域物体反方向关系的研究系本人在燕山大学攻读硕士 学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大 学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人 完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有 关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权 燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文 的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密呱 ( 请在以上相应方框内打“”) 作者签名：名名：1 龟 日期：王。f 年4 月对日 导师签名：锄 1 鼻由 日期：妇6 年弘月蜀r 白 第1 章绪论 1 1 引言 第1 章绪论 地理信息系统( 简称g i s ) 是一个能够收集、存储、处理和显示地理空 间信息的计算机系统。地理信息系统既是管理和分析空间数据的应用工程 技术，又是跨越地球科学、信息科学和空间科学的应用基础学科【l 】。它被 广泛应用于科学调查、军事、资源管理和发展规划等领域。 地理信息系统是为了解决资源与环境等全球性问题而发展起来的技术 与产业，世界上第一个地理信息系统管理系统于1 9 6 4 年产生于加拿大f c 地理信息管理系统) ，它是针对加拿大丰富的土地资源，为农业服务而开发 的。它的出现，为以后地理信息系统应用于其他国家和领域奠定了基础。 7 0 年代末8 0 年代初，欧洲的大多数国家也相继开发了地理信息系统管理 软件，这些软件的特点是技术新颖、通用性强、简单实用。地理信息系统 的应用领域发展迅速，已成为了一个新兴的技术产业【2 1 。 我国的地理信息系统研究始于7 0 年代。1 9 9 4 年4 月中国地理信息系 统协会的成立，标志着我国的地理信息系统技术和产业发展进入了一个新 的阶段。1 9 9 6 年以来，武汉测绘学院、中国科学院、地理研究所、遥感 应用研究所、南京大学、国家测绘局测绘科学研究所等单位，相继研制了 g i s 基本功能软件，包括数据采集与编辑、数据存贮与管理、数据处理和 变换、空间分析和统计、产品制作与显示软件等。目前，地理信息系统在 我国的诸多领域已取得了很大的发展。 空间数据库是g i s 的核心，也是他最具特色的一部分，其基本功能包 括两个方面，一是对空间数据的存储，二是对空间数据查询的支持。空间 数据查询既有属性查询，也有空间查询，还可实现空间与属性之间的交叉 查询。空间查询与分析是g i s 最重要的功能，也是g i s 区别于其他信息系 统的本质特征，它使地理空间信息以及各种专业信息的利用深度和广度大 燕山大学工学硕士学位论文 大增强。用户可以从中获得很多派生的信息和新知识，可用来实现经济建 设、环境和资源调查中的综合评价、规划、决策、预测等任务。 空间推理是指利用空间理论和人工智能技术对空间对象进行建模、描 述和表示，并据此对空间对象间的空间关系进行定性或定量分析和处理的 过程p j 。当描述一个空间配置或对这样的配置进行推理的时候，要获得精 确、定量的数据通常是不可能的或不必要的。在这种情况下，就要用到关 于空间配置的定性推理。定性空间推理( 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 ，q s r 、 是地理信息系统领域、人工智能领域及多媒体领域针对空间问题的研究方 向【4 j 。作为定性空间推理的重要部分，定性的空间方向关系的研究受到越 来越多的重视。目前，对于空间方向关系许多世界著名大学教育机构都在 进行空间推理的研究，但关于空间方向关系的一些基本问题目前还没有一 个为大家共同接受的标准，致使其基本上还处于尝试和探索阶段。在国内， 则仅有少数专家对其进行理论研究，研究成果甚微。 1 2 本课题的国内外研究现状 空间推理理论和应用研究近年来有了长足的进展，国内外大量研究机 构在相关领域取得了可喜成果。 1 2 1 空间推理概况 在国外，成立了许多专门从事空间推理方面研究的协会和联盟，如欧 洲定性空间推理网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 近年来发 表了许多篇空间推理方面的文章，而且呈逐年增长的趋势，这可以从这本 期刊近年来的总目录中看出。在一些大学里，不仅有越来越多的研究人员 从事空间推理方面的研究工作，而且还在大学生和研究生中开设了空间推 理方面的相关课程。近几年来，空间推理方面的学术会议也越来越多。空 间推理是地理信息系统、人工智能、多媒体等学科处理常识性空间知识的 一种常用方法。 第l 章绪论 大量的空间推理文献、近年来召开的国际空间推理学术会议以及 i n t e r n e t 网的空间推理站点都表明，时空推理s t s r ( s p a t i o t e m p o r a ls p a t i a l r 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 ) $ n 地理信息系统 ( g i s ) 是空间推理的研究热点【2 】。其中的定性空间推理主要包括空间拓扑推 理、空间方向关系推理及距离推理，总体而言，拓扑推理和距离推理方面 的研究较多，空间方向关系推理的研究还处于起步阶段。 1 2 2 空间拓扑推理 1 9 8 8 年g u t i n g 以点集为基础，给出了相等、不相等、包含、相离和 相交等拓扑空间关系的定义。p u l l a r 在1 9 8 8 年将点集方法加以扩充，运用 拓扑学理论中点集的边界和内部的概念，给出了覆盖和相邻两个关系定义。 w a g n e r 在1 9 8 8 年定义了相邻、相离、严格包含、相交四种拓扑空间关系。 e g e n h o f e r 和f r a n z o s a 在1 9 9 1 年提出了一个四元组表达的拓扑空间关系描 述框架。1 9 9 3 年，e g e n 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 所定义的四元组基础上， 运用维数扩展法，即用两个空间目标内部与边界之间交集的维数，作为描 述两个点集间拓扑空间关系的框架。进一步，他们给出了二维拓扑空间关 系的最小集。他们的方法形式化地描述了二维空间目标之间的拓扑空间关 系【5 】。在国内，拓扑空间关系的描述一直是研究的重点和热点，中科院、 国家基础地理信息中心、浙江大学、武汉测绘科技大学等单位都作过大量 的研究，如郭薇、陈军提出的基于点集拓扑学的三维拓扑空间关系形式化 描述【6 】，潘云鹤等人提出的基于v o r o n o i 图的维扩展法来描述g i s 中的空 间拓扑关系【5 j 。 1 2 3 空间方向关系推理 空间关系是指地理实体之间存在的一些具有空间特性的关系 7 】，空间 关系同样是g i s 中基础理论和方法研究的热点和重点。由于受人们认知的 影响，致使人们往往用空间关系术语来描述空间关系，如“东”、“南”等 燕山大学工学硕士学位论文 这种用术语( 词语) 来描述空间关系的方式称为定性表达。定性表达的关键 在于找到空间对象关系特征和空间关系术语之间的映射关系。由于映射的 方式不同，从而产生了不同的描述方法。在方向关系的表达方面，则以基 于投影和锥形的方法为代表。 目前关于方向关系推理的研究主要有最早由g o y a l 和e g e n h o f e r 所提 出的推理理论【8 】，文献 8 最近提出的模型已证明是目前较合理、较好的模 型，本文的研究建立在该模型的基础上。还有后来s p i r o s 和m a n o l i s 的理 论【9 与l i g o z a t 的理论【4 】。但是g o y a l 和e g e n h o f e r 的理论被s p i r o s 和m a n o l i s 证明是不完善的，而s p i r o s 和m a n o l i s 的合成问题研究是基于方向关系谓 词的不能直观的表示空间区域之间的方向关系，所以需要使用合理的方向 关系模型既能用来表示各个空间区域的方向关系又能使用该模型进行方向 关系的各种推理的运算。 随着研究的深入，近几年人们逐渐认识到，空间推理本质上是定性的， 空间推理的关键是形状的定性表示，并且也逐渐认识到上述空间推理一般 框架和研究方法存在着局限性。因而，完善空间推理现有的研究方法，并提 出定性与定量相结合的一般框架和研究方法是一项有意义的研究工作。 方向关系模型分定量的方向关系模型和定性的方向关系模型，这里主 要关注定性的方向关系模型。人们主要提出的方向关系之间的模型有点模 型 1 0 1 2 】、点线模型【m 16 1 、区间模型【1 7 , 1 8 1 、最小边界矩形【1 9 , 2 0 l 、方向关系矩 阵模型【2 ”、v o r o n o i 图形模型瞄1 等，各种模型在表述能力方面各有优缺点。 方向关系合成就是通过已知的空间区域的方向关系来推出未知的方向 关系。通过多年的研究，人们在不同的模型基础上形成了不同的合成算法， 比如：基于方向关系矩阵的合成算法，还有s p i r o ss k i a d o p o u l o s 和m a n o l i s k o u b a r a k i s 的基于谓词的方向关系合成算法【9 】等，但普遍存在对真实物体 的表现能力不足的问题。 给定一系列空间物体以及它们之间的主方向关系，判断这一系列主方 向关系所形成的空间网络图关系是否一致，即能否找到一组或一组以上的 解来满足这些空间方向关系所形成的网络，这是方向关系的一致性检验问 题斟】。s p i r o ss k i a d o p o u l o s 和m a n o l i sk o u b a r a k i s 在别人的基础上做了大 4 第1 章绪论 量的研究并取得了一些的成果。 由于空间数据库中数据是海量的，为了减少数据的冗余，如何以最少 的数据量包含最大的空间信息成为了空间数据库领域研究的一个热点，再 者，空间数据查询、空间数据推理时，也需要从已知的信息中推出未知的、 隐含的信息。空间物体的方向关系直接反映的是目标物体相对于参考物体 的位置关系，由方向关系的自反性可知，这种关系中同时也包含了参考物 体相对于目标的位置关系。对空间反方向关系的研究正好可以在一定程度 上解决空间信息推理的需要，关于反方向关系目前还没有文献进行深入的 研究，s p i r o ss k i a d o p o u l o s 和m a n o l i sk o u b a r a j d s 只是给出了基于m b r 的 反方向关系的定义【2 3 1 ，并没有进行更深入的研究，反方向关系的描述及反 方向关系的运算都有其自身的特点，这一领域的研究目前还处于空白，本 文中若无特别说明，反关系等同于反方向关系。 1 2 4 拓扑、方向及距离相结合推理 拓扑、方向、距离等各种空间关系从不同角度刻画了空间实体间的关 系，所有类型的空间关系在本质上应该是统一的。这些关系的研究并不是 完全孤立的，它们之间存在着一定的关系，合理有效地运用这些关系可以 帮助判断一些隐含的空间关系( 如拓扑空间关系) 或排除一些不可能的空间 关系，从而在模糊不确定的空间关系的基础上去除不可能的关系，得到较 为精确的结果。比如己知三个空间对象a ，b ，c 之间的拓扑关系，通过 拓扑关系的复合运算，可以得到a ，c 之间可能的拓扑关系。很多情况下， 得到的拓扑关系很多，需要进一步求解。这种情况下，若知道a ，b 与c ， b 或a ，c 的方向关系，就可以将方向关系作为拓扑空间关系判断的依据， 从而更好地进行空间分析。 在实际应用( t l 如g i s 的空间查询) 中，综合考虑多种空间关系的情况 十分普遍。2 0 0 2 年，a l f o n s o 研究了结合拓扑和尺寸信息的空间表示和推 理方法。他采用了r c c 拓扑关系理论从r c c 8 中去掉p o 后得到r c c 7 ， 指出r c c 一7 也是n p 完全的。对尺寸绘出了定性和度量两种描述，并分别 同拓扑关系相结合。a l f o n s o 原工作从“计算”而不是“表示”的角度研究 燕山大学工学硕士学位论文 多种空间关系的综合同题。尺寸和拓扑两个原本已研究得比较透彻的空间 关系，将它们结合在一起就会产生如此多的新问题。不仅空间关系分为多 种类型，对时间的建模方式和角度也多种多样。将这些时态和空间关系中 的部分甚至全部结合起来，是一项非常艰苦又十分有意义的工作，也是时 空推理的研究重点和热点之一【2 5 j 。 1 3 研究空间方向关系推理的意义 通过对时空推理研究工作进行总结和比较可以发现，空间推理是人工 智能以及地理信息系统、时空数据库等相关领域的热点研究方向。本文认 为时空推理有以下几个方面的意义。 ( 1 ) 空间方向关系理论完整性的需要空间方向关系推理是空间关系 方向理论不可或缺的重要组成部分。缺少了方向关系推理的空间关系理论， 就不能或不能很好的对空间信息进行分析、加工和优化。在地理信息系统 g i s 的实际应用中，人们不能满足只对空间信息进行存储和简单的位置描 述，需要对已有的地理信息进行分析和处理，空间方向推理研究可以很好 的支持对未知空间信息的推导和对已有信息正确性的检验。 ( 2 ) 空间查询的需要空间查询是g i s 中应用最多的功能之一。现在流 行的a r c i n f o 等g i s 软件，其查询功能基本上是基于空间距离和拓扑关 系，基于空间方向关系的查询很少涉及。空间方向关系具有自反性和传递 性，其具备空间推理的条件。空间方向推理理论的研究正好满足了这一空 白，实现高效的空间推理算法可以为预处理空间查询以及对需要搜索空间 的提前剪枝 2 3 提供了快捷可行的方法。 ( 3 ) 新一代g i s 研制的需要新一代g i s 的一个显著特征是语音功能 的增加，即g i s 和用户可以进行语言的直接交流，这种语言交流的语法规 则就要依据空间概念的形式化描述。而空间推理则是这种空间概念描述的 具体执行者，系统通过空间推理算法才可以得到人们所预期的正确结果。 定性的空间推理对人们日常生活来说是至关重要的。例如：人们布置 家具，规划建筑。所以信息系统提供处理复杂的空间推理功能是非常必要 第1 章绪论 的。方向作为一个重要的空间关系，已经用在了很多领域，例如：空间数 据库、人工智能、人工推理等。于是关于方向关系的推理研究是十分重要 的，对其进行深入、系统地研究是具有深远意义的。 1 4 本文的主要研究内容及组织结构 本文的研究内容为二维空间区域物体反方向关系，主要研究工作有： ( 1 ) 对时空代数进行了研究，在区间代数和矩形代数理论的基础上，对 区间代数进行了扩展，使之能表示间断区间之间的关系。 ( 2 ) 利用区间代数和矩形代数理论，在九区域方向关系模型上，对基于 m b r 的反方向关系进行了研究，提出了反方向关系的求解方法，给出了基 于m b r 的反方向关系与主方向关系的对应表。 ( 3 ) 对方向关系模型进行了扩展，使之克服了原模型表示真实物体方向 能力的不足，研究了真实物体方向关系推理过程中的不确定性。 ( 4 ) 在扩展方向关系模型上研究了基于真实物体的反方向关系，详细分 析了反方向关系求解的基本运算，给出了真实物体的反方向关系的求解方 法，并结合实例对方法的正确性进行了验证。 本文的结构安排如下。 第1 章绪论介绍了本课题的研究背景及意义，讨论了什么是空间方向 关系以及什么是空间推理。重点介绍了空间推理中的方向关系的研究与发 展，最后给出了本文的研究内容及组织结构。 第2 章空间方向概述及模型详细分析了方向关系模型的研究现状，以 及各种模型之间的比较，提出了目前现有的方向关系模型表达能力的种种 不足并给出了方向关系的分类以及进行空间方向关系推理研究所需要的一 些基本概念和基础知识。 第3 章时空代数的研究介绍了区间代数和矩形代数理论。指出了区间 代数表示能力的不足，扩展了区间代数，给出了间断区间代数关系的表示 方法，分析了间断区间代数与a l l e n 区间代数之间的关系。 第4 章基于m b r 反方向关系的研究在基于m b r 主方向关系模型上， 燕山大学工学硕士学位论文 介绍了m b r 反方向关系的定义，分析了这种反关系的特点，给出了空间 方向关系向矩形代数关系转化的有关定义、定理，讨论了基于m b r 的主 方向关系求反关系方法，通过实例演示了反关系的求解过程，给出了主方 向关系及其反关系的对应表。 第5 章基于真实物体反方向关系的研究分析了由物体形状带来的空间 推理的不确定性，根据真实物体的特点，提出了基于真实物体的主方向关 系扩展模型，介绍了该模型上方向关系的原子主方向关系、基本主方向关 系的定义，给出了真实物体反方向关系的定义，比较了基于m b r 的反关 系和基于真实物体的反关系，阐述了扩展模型上方向关系矩形化和析取的 基本思想，给出了基于真实物体反方向关系的求解方法。 最后是本文的结论，并对下一步的研究工作进行了展望。 第2 章空间方向概述及模型 第2 章空间方向概述及模型 方向是空间对象在空间关系研究中经常使用的词汇，方向关系描述的 是空间对象间的一种顺序，如：前、后、左、右、东、南、西、北等。方 向确定了空间主方向的划分，不同的方向关系表示模型得到的方向也是不 尽相同的。 方向是人们日常生活中常用的定性词汇，试看下面的例子。 ( 1 ) 西藏自治区在中国的西南，通州区在北京市东方； ( 2 ) 黄河以北，长江以南； ( 3 ) 在图书馆左前方是第一教学楼。 这些都是定性方向描述的例子，从这几个例子中得到以下结论。 ( 1 ) 方向相对要描述一个方向需要两个对象，一个是参考对象，另一 个是目标对象。方向是目标对象相对于参考对象的方向。 ( 2 ) 参考对象具有多样性可以是区域、线或点。前面的例子分别以区 域、线、点作为参考对象。 ( 3 ) 参考对象与目标对象的关系存在多样性在上面例子中，第一个中 目标对象包含在参考对象中，第二个中目标对象与参考对象相接触( 拓扑关 系为t o u c h ) ，第三个中的目标对象与参考对象分离( 拓扑关系是d i s j o i n t ) 。 ( 4 ) 方向的划分不同第二个例子中仅使用北与南两个方向，第一个和 第三个中则使用两个以上的方向。 方向关系描述了一个对象相对于另一个( 或几个) 对象的关系。人们一 般用三个基本概念定义方向关系：目标对象、参照对象和参考系，由于参 考系的不同方向关系有很多种表示方法，可以分为基于投影的和非基于投 影的两类。 方向关系模型的表示能力在研究地理信息系统里面是至关重要的【2 7 】。 在将来地理信息系统将会提供多种用户界面应用模型，提供语音查询等多 种功能【2 8 1 。例如用户可以使用自然语言询问，“查找中国长江以北的所有 9 燕山大学工学硕士学位论文 的河流”，地理信息系统将会具有这个功能提供查询结果。这种空间推理任 务对人类的智能来说是非常容易的，但是为了使用计算机的帮助来完成这 些任务，则需要正式的空间概念模型。本章回顾了现存的各种方向模型并 给出了本文所使用的方向模型。 2 1 空间方向关系 空间关系体现了空间物体间的相关位置的信息p ”，是g i s 研究中的一 个重要课题。在定性空间关系推薹3 ( q s r ) 中，主要有3 种类型的空间关系： 空间拓扑关系，空间方向关系以及空间距离关系。 主方向关系捕获了物体间相互关系的信息。例如a 在b 的北方。物体 间的主方向关系不依赖于物体内部的结构、观察者和所处空间的尺度，但 是他却依赖于他们的形状以及相互的位置、他们的大小。例如，如果a 在 b 的北方，a 在空间放大和缩小的情况下仍然在b 的北方。但a 的形状和 大小的改变却可以引起a 与b 方向关系的改变。 对于主方向关系推理，在理论研究中分为定量的空间推理和定性的空 间推理两种。定量推理主要应用于已知空间物体具体坐标的情况，而定性 推理则是人们对空间位置一种概念上的认知。本文主要讨论定性的主方向 关系的空间推理，下面来详细的介绍空间中的方向关系以及方向关系模型。 2 2 空间方向的性质、特点 空间方向有5 个性质，可以概括如下。 ( 1 ) 传递性在所使用的参考框架f 里面，假设其主方向的集合为 d = d 1 ，d 2 ，d n ，n = 2 k + l ，k 2 1 目标为o i 空间方向计算函数为f ，若对空间 方向三元组有f r 0 1 ，0 2 ，f ) = d i 、f ( 0 2 ，0 3 ，f ) = d i 则必有f ( o a ，0 3 ，f ) = d i 成立， 此为空间方向的传递性。 ( 2 ) 反射性若对空间方向三元组有f ( a ，b ，f ) = o i 则必有f ( b ，a ，f ) = d n ，1 成立，此为空间方向的反射性。 第2 章空间方向概述及模型 ( 3 ) 完整性空间方向是全圆方向的覆盖，此为空间方向的完整性。 ( 4 ) 平等性 空间方向没有大小的区分是一种平等关系，此为空间方向 的平等性。 ( 5 ) 相对性这包括两层意思，一是空间方向是相对于参考框架的，参 考框架变化它也发生变化；二是空间方向是相对于目标指向的，指向关系 改变空间方向也会发生变化。 空间方向的两个特点如下所示。 ( 1 ) 多样性由参考目标到源目标的空间方向往往不能用一个角度值 或一句简单的方向描述性语言东、南、西、北等来表达。如我国内蒙古和 东北三省用传统的4 、8 、1 6 或3 2 方向定义的基本方向术语都无法完备地 描述二者的方向关系，需要寻求新的表达手段对空间方向多侧面进行描述。 ( 2 ) 复杂性空间方向关系的判断求解并不像看上去那么简单，而是一 个复杂的空间思维和运算过程且和目标的位置、形状、大小、距离、拓扑 等有关。人们对空间方向的判断是多因素“合力”作用的结果。 2 3 方向关系模型 2 3 1 定量的方向模型 在地理应用中目标点的方向主要使用的是相对于一个参考点的方位角 来定义的。方位角是一个通过参考点的子午线以及通过参考点到目标点的 连线( 测量线) 之间的角度，如图2 - 1 所示。子午线上所有的点相对于参考 点来说在正北方向，也就是角度为0 0 。对所有的其他的点方位角是由顺时 针方向从子午线的北方滑到测量线的角度，角度值为 0 ，3 6 0 。可用公式 ( 2 1 ) 来计算。 ，、 a = t a n 4 f 三丛 ( 2 1 ) 对于那些大于3 6 0 0 的角则循环映射到这个区间。例如3 6 0 0 映射为0 0 4 5 0 0 映射为9 0 0 。 燕山大学工学硕士学位论文 a 图2 - 1 方位角定义 f i g 2 - 1d e f i n i t i o no f a z i m u t ha n g l e 两个点之间的定量的方向关系使用方位角的角度来测量。它们的值可 以近似用在某些领域中。例如点b 相对于点a 的方位角可能为4 3 0 3 4 ，4 5 ”。 可以应用在例如陆地测量或者是机器设计等领域。然而空间数据库中的查 询语言使用的是定性的方向而不是定量的方向。因此本文重点介绍的是定 性的方向关系。 2 3 2 定性的方向模型 定性的方向关系相对于定量的方向关系来说是对方向关系的一种更为 粗糙的近似，并且使用更少的符号集来记录方向关系的信息。例如区间 【o o ，3 6 0 0 会被划分为四个或者是八个方向区域，每一个区间表示一种方向 关系i lo j 。四个区域的系统使用首要的方向东、南、西、北。八个区域的系 统使用首要的方向东北、北、西北、西、西南、南、东南、东。人们经常 使用的定性的空间推理而不是定量的空间推理，主要是因为定性的方向关 系足够人们用来交流信息，而且定量的信息例如t a n l 在人们的头脑里不能 很快的得到结果。而且不容易理解。在人们使用g i s 的时候很少会使用像 “查找与北京方位角为4 3 0 3 4 4 5 ”的所有的湖泊”这样的查询。而是经常使 用类似“查找所有位于北京西北方向的湖泊”这样的查询。 下面就方向模型进行详细讨论。 ( 1 ) 基于锥形的点物体间的方向模型基于锥形的方向模型系统把参 考点周围的空间划分为互不相交的分别间隔为9 0 。或者4 5 0 的四个部分或 第2 章空间方向概述及模型 八个部分 3 2 , 3 3 】，见图2 - 2 。其中四方向系统使用定性的方向北、东、西以 及南，而八方向系统还要使用额外的东南、东北、西南、西北四个方向。 如果目标物体与参考物体重叠称为与自身相同。包括与自身相同方向关系 在内，四方向系统区分了五种方向关系，八方向系统区分了九种方向关系。 目标物体相对于参考物体的方向关系有目标物体占据参考点的方向区域决 定。例如图2 2 中，在四方向系统中a 与b 的方向关系为北，八方向系统 中a 与b 的方向关系为东北。 b ( a ) 4 方向系统( b ) 8 方向系统 ( a ) f o u r - d i r e c t i o ns y s t e m ( b ) e i g h t d i r e c t i o ns y s t e m 图2 - 2 锥形法模型 f i g 2 - 2c o n e - b a s e dm o d e l ( 2 ) 基于投影的点物体问的方向模型基于投影的方向模型使用通过 参考物体的垂直线和水平线来划分空间。一条水平线把空间划分为北与南 两部分，而一条垂直线把空间划分为东与西两部分。同时使用水平线与垂 直线则把空间划分为东南、东北、西南、西北四个部分。参考框架中包括 表示四种方向的四个区间以及四条线，一个点。四个区间表示东南、东北、 西南、西北四个方向，四条线代表东、南、西、北而中心点则表示与本身 相同方向关系。 基于投影的模型如图2 3 所示，相对于锥形表示模型的优势有：基于 投影的模型类似于地图中的经度纬度l ”】；相对于基于锥形的模型该模型有 大量精确的合成推论【”】；因为基于锥形模型划分空间的角度问题，基于投 影的模型相对来说更容易在数据库中实现。但是基于锥形的模型更容易被 扩展用来支持更多的方向划分，例如划分为1 6 或者3 2 个方向区间。但是 燕山犬学工学硕士学位论文 人们日常使用的表示方向关系的方向划分很少会多于9 种，所以本文所使 用的方向模型主要是基于投影的。 图2 - 3 基于投影的点物体的方向模型 f i g ，2 - 3p r o j e c t i o n - b a s e dd i r e c t i o nm o d e lf o rp o i n to b j e c t s ( 3 ) 点物体与线物体之间的方向模型f r e k s a 和z i m m e r m a n n 提出了 一个框架来表示点物体相对于线物体的方向关裂h 16 1 。一个点物体相对于 一个线物体可以是任意的1 5 种不同的方向关系中的一种，如图2 4 所示。 c i c 2 c 3 - c dc 5c 6 a c 7 c b c 9 - c l oc h bc 1 2 一 c 1 3 -c 1 4 _ c js 图2 - 4 相对于线a b 点c 有1 5 种不【司的位置 f i g 2 - 4p o i n tcc a nb ei n15d i s t i n c tl o c a t i o n sw i t hr e s p e c tt ot h el i n ea b 这个模型不包含任何外部方向关系而且线物体相对于x 轴可以处于任 意的角度。这个模型并不使用任何近似来处理点物体相对于线物体的方向 关系，这是这个模型的一个非常有用的特性。然而该模型对于区域物体来 说并不适用，因为：线物体并不总是与外部参考框架的水平线平行因此不 能用来表示主方向关系；目标物体必须近似于一个点；这种方法不适用于 区域物体。 ( 4 ) 一维平面上的间隔关系模型a l l e n 提出的间隔关系模型1 1 7 】表示了 一维空间中的空间方向关系信息。共存在1 3 种不同的关系，叫做时域间隔 1 4 第2 蕈空司方向概述及模型 关系或者一维间隔关系。f r e k s a 把这些关系推广到半间隔关系3 4 1 ，半间隔 关系描述物体的开始端或者结束端，并不描述物体的所有部分。1 3 种关系 如图2 5 所示。 h 卜b 马目口曰 e 宁 j j 卜上二| h h 卜_ 一卜与_ _ 图2 - 5a l l e n 的一维空司的1 3 种时空l 司隔关系 f i g 2 - 5a l i e n st h i r t e e nt e m p o r a li n t e r v a lr e l a t i o n si nl - d i m e n s i o n ( 5 ) 最小边界矩形m b r 使用物体的最小边界矩形之间的空间关系 来表示物体之间的方向关系称作m b r 方向关系。m b r 在x 轴和y 轴投 影的推理可以使用前面介绍的一维间隔关系得到。例如，在图2 - 6 中，b 在x 轴的投影与a 在x 轴上的投影的关系为b e f o r e ，b 在y 轴的投影与a 在y 轴上的投影的关系为b e f o r e 。 y 卜一卜一 x 一- 图2 - 6 两个最小边界矩形之间的空间关系 f i g 2 - 6s p a t i a lr e l a t i o nb e t w e e nt w om i n i m u mb o u n d i n gr e c t a n g l e s 所以物体a 与物体b 的m b r 的方向关系为( b e f o r e ，b e f o r e ) 。使用这个 方法，可以唯一的确定物体m b r 之间的关系。因为在每个轴上都有1 3 种 关系，所以，使用这个模型共有1 3 1 3 = 1 6 9 种关系。最小边界矩形m b r 是方向关系模型的基本方法。m b r 方法常作为空间对象的几何近似，一个 燕山大学工学硕士学位论文 对象的m b r 定义为完