（计算机应用技术专业论文）线型物体方向关系推理的研究.pdf

摘要 摘要 定性的空间推理是空问数据库和地理信息系统应用研究中必不可少的 组成部分，而定性空间推理中的方向关系研究直足定性空间推理研究领 域的热点。作为定性方向推理研究领域的重要组成部分，线型物体方向关 系推理有着十分广泛的应用前景，因此本文在线型物体方向关系推理方面 进行了研究和探索。 本文就已存在的空间方向关系模型进行了研究总结，在区域物体最小 边界矩形模型基础上，提出了线型物体的主方向模型。在建立线型物体主 方向模型的基础上，对线型物体主方向关系进行了深入研究，并结合区间 代数和矩形代数理论，提出了用投影区间矩形代数表示线型物体基本主方 向关系的方法，有利于线型物体主方向关系的推理运算和网络一致性检验 的实现。 本文深入研究了线型物体主方向关系之间的取反运算、求交运算和合 成运算，给出了相应的定义、定理，具体分析了投影区间关系、基本主方 向关系和多基本主方向关系在各个运算中相应的推理运算方法。对线型物 体主方向模型中的凸关系进行了详细分析，给出了线型物体主方向关系中 凸关系的判定方法，并且结合凸关系网络定理和路径一致性算法，提出了 主方向关系网络一致性检验的方法和具体算法，给出了算法的正确性证明 和主方向关系网络一致性检验的具体示例。 关键词主方向关系；线型物体；最小边界矩形；方向关系运算；方向关系 推理；致性检验 燕山人学j ：学硕士学位论文 a b s t r a c t 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 sa na b s o l u t e l yn e c e s s a r yp a r to ft h es t u d y a b o u tt h ea p p l i c a t i o no fs p a t i a ld a t a b a s ea n dg e o g r a p h yi n f o r m a t i o ns y s t e m ， a n dt h ed i r e c t i o nr e l a t i o ns t u d yo fq u a l i t a t i v es p a t i a lr e a s o n i n gi 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 sa ni m p o r t a n tp a r ti nt h e r e s e a r c h i n g a r e ao fq u a l i t a t i v e s p a t i a lr e a s o n i n g ，t h ed i r e c t i o n r e l a t i o n r e a s o n i n go fl i n e t y p eo b j e c t sh a sah o p e f u la n de x t e n s i v ef u t u r eo fa p p l i c a t i o n ， s ot h i sp a p e rc a r r i e so ns t u d i e sa n de x p l o r e si nt h ea s p e c to fd i r e c t i o nr e l a t i o n r e a s o n i n gb a s e do nl i n e t y p eo b j e c t s m o d e l so fs p a t i a ld i r e c t i o nr e l a t i o n sa r es u m m a r i z e di nt h i sp a p e r b a s e do n t h em i n i m u mb o t m d a r yr e c t a n g l em o d e lo fs p a t i a la r e ao b j e c t s ，t h ec a r d i n a l d i r e c t i o nr e l a t i o n sm o d e lo fl i n e t y p eo b j e c t si sp u tf o r w a r d c a r d i n a ld i r e c t i o n r e l a t i o n so fl i n e t y p eo b j e c t sa r es t u d i e df a r t h e ra n dt h es t u d yi sb a s e do nt h e e s t a b l i s h e dc a r d i n a ld i r e c t i o nm o d e lo fl i n e t y p eo b j e c t s am e t h o di sp u t f 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 la l g e b r aa n dr e c t a n g l ea l g e b r at o e 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 so fl i n e t y p eo b j e c t s ，u s i n gt h er e c t a n g l e a 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 ft h eo p e r a t i o no 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 gf o rl i n e t y p eo b j e c t s ，a n do f t h er e a l i z a t i o n o ft h en e t w o r k c o n s i s t e n c yc h e c k i n ga sw e l l i n v e r s i o no p e r a t i o n ，i n t e r s e c t i o no p e r a t i o na n dc o m p o s i t i o no p e r a t i o nw i t h c a r d i n a ld i r e c t i o nr e l a t i o n so fl i n e t y p eo b j e c t sa r es t u d i e df a r t h e ri n t h i sp a p e r c o r r e s p o n d i n gd e f i n i t i o n sa n dt h e o r e m so ft h e ma r ep u tf o r w a r d ，a n dt h e r e a s o n i n go p e r a t i o nm e t h o d so fp r o j e c t i o ns e c t i o n sr e l a t i o n sa p p l i e dt o p r o j e c t i v ei n t e r v a lr e l a t i o n s ，c a r d i n a ld i r e c t i o nr e l a t i o n sa n dm u l t i - c a r d i n a l d i r e c t i o nr e l a t i o n si n e v e r yf o r e n a m e do p e r a t i o na r ea n a l y z e dc o n c r e t e l y c o n v e xr e l a t i o n si nt h ec a r d i n a ld i r e c t i o nr e l a t i o n sm o d e lo fl i n e t y p eo b j e c t s a r ea n a l y z e di nd e t a i l t h ej u d g i n gm e t h o do fc o n v e xr e l a t i o n si nc a r d i n a l a b s t r a c t d i r e c t i o nr e l a t i o n so fl i n e t y p eo b j e c t si sp r o v i d e d t h i sm e t h o da n da l g o r i t h m o fc o n s i s t e n c yc h e c k i n gf b rc a r d i n a ld i r e c t i o nr e l a t i o nn e t w o r k sa r ep r o p o s e d b yc o m b i n i n gt h ec o n v e xr e l a t i o nn e t w o r kt h e o r e ma n dp a t hc o n s i s t e n c y c h e c k i n ga l g o r i t h m ，a sw e l la st h ec o r r e s p o n d i n gc o r r e c t n e s sp r o o fa n dt h e a l g o r i t h m i ca n a l y s i sa r eg i v e ni nt h ee n d k e y w o r d sc a r d i n a ld i r e c t i o nr e l a t i o n s ；l i n e t y p eo b j e c t ；m i n i m u mb o u n d a r y r e c t a n g l e ；o p e r a t i o no fd i r e c t i o nr e l a t i o n s ；r e a s o n i n go f 、d i r e c t i o n r e l a t i o n s ；c o n s i s t e n c yc h e c k i n g i l l 第1 章绪论 1 1 课题研究背景 第1 章绪论 人类在2 1 世纪将全面进入信息时代，有关地球科学问题的研究需要以 信息科学为基础并以现代化信息技术为手段。地理信息系统( g i s ) 是与人类 生存、发展、进步密切相关的一门信息科学与技术，是地球空间信息科学 的重要组成部分，它被广泛应用于国民经济的很多部门，如城市规划与设 计、资源环境管理、生态环境监测与保护、地质勘探测量、城市管网配电 网、灾害监测防治等多个领域，越来越受到人们的重视【l 】。 但是，随着地理信息系统应用深入，不仅要求g i s 具有一般管理和分 析功能，还需要有进一步空间预测和推理能力，而现有g i s 空间数据表达 不直接支持空间推理运算，因此能够支持空问推理运算的空间推理研究成 为g i s 进一步发展的当务之急【2 】。 空间推理( s p a t i a lr e a s o n i n g ，s r ) 是指利用空间理论和人工智能 ( a r t i f i c i a li n t e l l i g e n c e ，a d 技术对空间对象进行建模、描述和表示，并据此 对空间对象间的空间关系进行定性或定量分析和处理的过程。目前，空间 推理被广泛应用于地理信息系统、机器人导航、高级视觉、自然语言理解、 工程设计和物理位置的常识推理等方面，并且正在不断向其他领域渗透， 其内涵非常广泛。 由于空间知识多数是粗粒度、主观的、不确定的，而且在描述一个空 间配置或对这样的空间配置进行推理的时候，要获得精确、定量的数据通 常是不可能或不必要的，因此，空阅关系的描述和推理酱遍采用定性方法 以符合人们的空间认知行为。 定性空间推理( 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 ) 主要研究空间信息 的定性表示和推理，是表示和处理空间知识的一种有效方法。o s r 一般采 用代数或逻辑方法对拓扑、距离、方向等空间关系以及形状、尺寸等空间 燕山大学工学硕士学位论文 特征进行描述，并对复合推理、约束满足问题、定性模拟等推理问题进行 研究。q s r 是空间推理和地理信息系统应用研究的重要部分，其研究不仅 具有重要的理论意义，同时在g i s 、机器人导航等领域都具有广泛的应用 前景【4 】。 空间方向关系与空间距离、空间拓扑关系一样，是s r 和g i s 中的重要 理论问题，在空间数据建模、空间查询、空间分析、空间推理、制图综合、 地图解译等过程中起着重要的作用。在距离、拓扑和方向等空间数据约束 条件中，距离的约束最强，方向次之，拓扑最弱蟑j 。作为定性空间推理中 非常重要的一部分，定性的方向推理用来处理关于物体之间的方向关系查 询、从已知的方向关系中推导出物体之间的未知的方向关系，以及检验空 间方向关系网络一致性等各种空间推理问题，一直是定性空间推理研究领 域的热点。 目前，国内外学者在定性空间方向推理方面的研究主要集中在基于点 和区域的主方向关系模型的建立、主方向关系的推理及查询等方面，而且 已经有许多方向关系模型和方向关系推理方法被提出f 6 j 。但是，这些已有 的方向关系模型在针对线型物体主方向关系研究的时候，都存在很多缺陷 和不足。比如，基于锥形的方向关系模型通常将空间目标的表示限制为一 个点，对于区域目标和线目标使用目标的几何中心来代替，忽略了目标的 大小和形状对方向关系的影响；而最小边界矩形( m i n i m u mb o u n d a r y r e c t a n g l e ，m b r ) 方向关系模型由于使用目标的m b r 代表目标本身，因而 对目标之间方向关系的描述欠准确，也容易产生错误的方向关系推理结果。 另外，由于不同比例尺空间对目标描述的细致程度要求不一样，因此， 在小比例尺空间可以采用抽象点表示一个空间目标来建立点目标问的方向 关系模型，但是在太比例尺空间应该充分考虑目标的大小和形状对方向关 系描述的影响，应该建立更细致、准确描述方向关系的模型。 对于线型物体，由于考虑到物体的具体形状，因此既不能简单抽象为 点，也不能用其m b r 简单替代。因此，考虑到以上关于线型物体空间关系 推理中存在的一些问题，有必要建立一种新的方向关系模型，既能细致准 确地表示线型物体主方向关系，又能满足对线型物体主方向关系进行各种 苎! 垩堑笙 推理运算的需要。这对进一步完善空间方向关系推理和地理信息系统的应 用研究均有理论意义和应用价值。 1 2 国内外研究现状 随着地理信息系统的发展及空间数据库技术的应用，空间方向关系的 推理研究正在迅速发展，许多世界著名大学教育机构都在进行空间方向关 系推理的研究【7 l 。近年来，在国外成立了许多专门从事空问推理方面研究 的协会和联盟。如欧洲定性空间推理网s p a c e n e t 以及匹兹堡大学的空间 信息研究组和慕尼黑大学空间推理研究组等等：在国内外的一些大学里， 不仅有越来越多的研究人员从事空间推理方面的研究工作，还在大学生和 研究生中开设了空间推理方面的课程。 对于空间方向推理首先是a l l e n 在文献 8 】中提出了区间代数理论，给出 了1 3 种区间关系以及这1 3 种关系的基本运算法则，为时态关系推理提供了 基础。但是，a l l e n 提出的区间代数理论只能用来推理一维区间之间的方向 关系，对于二维空间区域物体的方向关系推理不适合。b a l b i a n i l 9 发展了 a l l e n 理论，将a l l e n 的区间代数理论扩展n - - - - 维空间。提出了两个矩形之间 的1 6 9 种方向关系以及凸关系的定义，从而形成了矩形代数理论。应用该理 论可以将一维的时态关系推理算法扩展到为二维空间领域，方便地进行区 域关系的推理。但是b a l b i a n i 的矩形代数理论没有将方向关系推理整合到其 理论中。 方向关系模型的研究是空间方向关系推理研究中是至关重要重要的。 在空间方向关系研究的过程中，已有多种主方向关系模型被提出f 6 】。文献 【l o 将空间对象抽象为点，并建立了基于点物体的方向模型，利用有向图 和代数方法提出方向关系的推理规则，但是该方法对于线型物体和区域物 体并不适用。t h e o d o r i d s 在文献【1 1 】中利用m b r 建立了主方向关系模型，给 出了一系列主方向关系的定义，并且利用彤附进行基于m b r 主方向关系的 索引，加速了基于m b r 主方向关系的查询速度；但是，m b r 是空间对象的 几何近似值，这种粗糙的近似值会导致空间推理结果的矛盾和曲解。在文 燕山大学工学硕士学位论文 献【1 2 中提出的用方向关系矩阵表示主方向关系的模型，在基于授影的参 考框架上把参考对象四周的空间进行划分，记录目标对象落入的方向区域； 但是该模型的提出主要是针对区域物体的，并没考虑研究点物体和线型物 体空间方向关系的情况。g o y a t 在文献 1 3 l 中提出用深度方向关系矩阵表示 主方向关系的方法，不仅可以表示3 3 空间方向关系，而且可以进一步表 示相应的方向边界关系；但是该方法在进行空间方向关系表示和推理的过 程中，由于需要表示的空间信息比较多，因此相应的空问开销也比较大。 2 0 0 4 年，c h r i s t o p h e 和m a r i u s 在文献【1 4 】中提出了基于模糊语义的空间方向 关系推理模型，利用模糊理论进行空间方向关系的相似性研究。 s p i r o s 和m a n o l i s 在文献 1 5 】中进一步的研究了主方向关系合成问题， 从结果的存在性和一致性方面对主方向关系合成进行了深入的分析；又在 文献 1 6 仲提出了基于方向关系谓词的方向关系合成及主方向关系约束集 一致性检验研究的问题，但是该理论不能直观地表示空间线型物体和区域 物体之间的方向关系。i s l i i ”提出把基于投影的主方向关系算法和相对方向 关系算法结合在一起，以此解决单独使用其中一种算法均不能解决的方向 关系不一致的情况；但是该方法对于线型物体主方向关系推理并不适用。 m o r a t z i l 8 】讨论了具有方向关系的线型物体推理和演算方法，但是该研究采 用的是物体内部参考框架，并没有涉及针对线型物体外部参考框架韵主方 向关系研究。 综上所述，目前已有的各种方向关系模型和空间推理方法在针对线型 物体主方向关系研究的时候都存在缺陷和不足。因此，很有必要采用一种 新的方向关系模型和方法，既能细致准确地表示线型物体主方向关系，又 能满足对线型物体主方向关系进行推理运算的需要。迄今为止，还没有针 对线型物体主方向关系推理和一致性检验方面的专门研究。 因此，本文在前人研究的空闯方向关系推理的理论基础上，提出并采 用了线型物体主方向模型，因为相对于其他的主方向关系模型来说，该模 型能够更好地表示线型物体的空间方向关系，有利于线型物体主方向关系 的推理研究和一致性检验的实现。在此基础上，深入研究了线型物体的方 向关系推理及其一致性检验问题，结合凸关系网络定理和路径一致性算法， 4 第1 章绪论 提出了线型物体主方向关系网络一致性检验的方法和具体算法，给出了该 算法的j e 确性证明和主方向关系网络一致性检验的具体示例。这对进步 完善空间方向关系推理和地理信息系统的应用研究均有理论意义和应用价 值。 1 3 课题研究意义 空间方向关系的研究，特别是空间方向关系推理的研究，在空间推理 和地理信息系统领域有着深远的影响和巨大的作用。下面从三个方面简要 阐述这一课题的研究意义。 首先，空间关系理论完整性的需要。空间方向关系理论是空间关系整 体理论不可或缺的重要组成部分，缺少了空间方向关系，空间关系理论就 不能或不能很好的对空间信息进行分析、加工和优化。只有空间关系的各 个组成部分协同工作，才能达到对空间信息最佳的处理效果。因此，对于 空问方向关系的研究十分重要。而且，空间方向关系不仅可以作为空间分 析中的一个参数，丰富空间分析的方法，它的合理定义、描述和计算还能 够在地理空间的研究中，使g i s 从空间关系全局的高度把握模型的建立和 应用。所以，空间方向关系的研究，特别是空间方向关系推理的研究，对 于空间方向关系理论的完善具有重要意义。 其次，空间推理的需要。由于空间方向关系具有自反性和传递性，因 此，空间方向关系具备用于空间推理的条件，能够进行相应的运算和推理。 当描述一个空间关系或对这样的空间关系进行推理的时候，要获得精确、 定量的数据通常是不可能的或不必要的，在这种情况下就可能要用到关于 空间关系的定性推理【1 9 】。定性空间表示包括拓扑、形状、距离、方向等许 多不同的方面，我们不仅要判定什么样的空间实体是我们可以接受的。同 时还要考虑描述这些空间实体之间关系的不同方法；空间方向关系作为对 空间实体之间关系进行定性表示和描述的重要方法，其推理研究是空间推 理研究不可或缺的重要组成部分【7 】。 最后，地理信息系统的需要。地理信息系统技术被广泛用予科学调查、 5 燕山大学工学硕士学位论文 军事、资源管理和发展规划等领域。例如，当发生自然灾害时，应急规划 者可以利用地理信息系统容易地计算出响应时间，也可以利用地理信息系 统来查找受到波及的区域。然而，在地理信息系统中往往需要利用空间推 理理论，空间推理研究已经成为地理信息系统不可或缺的重要部分。这主 要有以下两个方面的原因：一方面，地理信息系统常常需要处理许多空间 方位、距离等信息，尤其是空间方向关系，它在地理信息系统中经常用作 空间查询的选择条件；另一方面，空间推理的研究大大促进了空间地理信 怠系统的发展，因为绝大多数的空间推理研究都涉及到地理信息系统，而 且在空间推理方面的文献中有关地理信息系统的研究最多。在地理信息系 统的实际应用中，人们不能满足只对空间信息进行存储和简单的位置描述， 需要对已有的地理信息进行分析和处理，而空间方向推理研究正好在一定 程度和范围内满足这分析处理空间信息的需要，能够很好的支持对未知空 间信息的推导和对已有信息正确性的检验，方便空间查询和剪枝t “。所以， 空间推理的研究，尤其是空间方向关系的推理研究，对于地理信息系统的 研究和发展是至芙重要的。 从上述三个方面的介绍可以看出，空间方向关系的研究，特别是空间 方向关系推理的研究，在空间推理和地理信息系统领域有着重要意义。而 本课题基于线型物体方向关系推理的研究正是空闯方向关系推理研究的一 个重要部分，对空间数据库、地理信息系统、人工智能、人工推理等领域 空间线型物体的方向关系推理和一致性检测有着重要的研究意义【2 0 】。 1 4 本文主要研究内容 本文主要研究基于线型物体方向关系的推理和主方向关系网络的一致 性检验，包括以下两个方面：一方面是建立基于线型物体的主方向模型， 并在此基础上给出线型物体主方向关系的表示和运算方法；另一方面是应 用线型物体主方向模型和主方向关系的表示和运算方法，对线型物体主方 向关系进行推理运算，并提出对线型物体主方向关系网络进行一致性检验 的方法和具体算法，以实现对线型物体主方向关系网络的一致性检验。 6 第1 革绪论 根据以上两方面的肉容，本文的主要研究工作有： 第一，提出线型物体主方向模型。相对于其他的主方向关系模型来蜕， 该模型能够更好地表示线型物体的空问方向关系，有利于线型物体主方向 关系的推理研究和一致性检验的实现。 第二，利用区间代数和矩形代数理沦，结合线型物体主方向模型，提 出了线型物体主方向关系的投影区涮矩形代数表示方法。 第三，将提出的主方向关系投影区间矩形代数表示方法应用于线型物 体主方向关系的表示和运算，给出了线型物体主方向关系运算的定义、方 法和定理，为线型物体主方向关系的推理研究奠定了基础。 最后，基于上述研究成果，提出了线型物体主方向关系网络的一致性 检验方法和具体算法，并且给出了算法的j f 确性证明和主方向关系网络的 致性检验示例。 1 5 本文组织结构 本文总体上分为五章，具体的布局和结构安排如下。 第1 章是绪论。本章介绍了本课题的研究背景、研究现状以及研究意义。 重点介绍了空间推理和空间方向关系的研究与发展，最后概述了本文的主 要研究内容及组织结构。 第2 章是空间方向关系概述及模型。本章首先介绍了与本课题研究相关 的空间方向基本知识和参考框架，然后讨论分析了常用的定量方向模型和 定性空间方向模型及其优缺点，最后是提出并建立线型物体主方向模型， 以便于进行下一步的线型物体主方向关系的研究。 第3 章是线型物体主方向关系。本章在线型物体主方向模型的基础上， 首先对课题研究涉及到的基本定义和基本理论进行了简要的介绍，然后将 区间代数和矩形代数理论与线型物体主方向关系相结合，提出了线型物体 主方向关系的投影区间矩形代数表示方法。 。第4 章是线型物体的主方向关系运算。本章对线型物体主方向关系的取 反运算、求交运算和合成运算进行了深入研究，给出了相应的定义和定理， 燕山人学一学硕十学位论文 弹细分析了在进行取反、求交和合成时，投影区问关系、基本主方向关系 和多基本j = 方向关系的推理运算方法。这些运算构成了线型物体主方向关 系推理以及网络一一致性检验的运算基础。 第5 章是主方向灭系推理及一致性检验。本章首先，简要介绍了主方向 关系网络和主方向关系网络的一致性检验：然后，对线型物体主方向模型 中的凸关系进行了洋细分析，给出了线型物体主方向关系中的凸关系判定 方法，并且介绍了重要的凸关系网络定义和定理：最后，结合凸关系网络 定理和路径一致性算法，提出了线型物体主方向关系网络一致性检验的方 法和具体算法，并给出了算法的f 确性和线型物体主方向关系网络一致性 检验的具体示例。 最后是本文的结论，总结了课题的主要研究成果和下一步研究工作的 主要方向。 8 第2 章空间方向概述及模型 2 1 引言 第2 章空间方向概述及模型 上一章主要阐述了本课题的研究背景、研究现状和研究意义。在本章 中，将详细介绍与本课题研究相关的空间方向基本知识，以及进行空间方 向关系研究的基本模型。 2 2 空间方向概述 人们研究二维空间中的定性空间推理的时候，经常使用的方向关系主 要是9 个主方向关系：本身，北，东北，东，东南，南，西南，西，和西北 【2 ”。例如，北京在天津的“北”方。在这个关系中天津是参考物体，北京 是目标物体，“北”是这两个有序物体间的主方向。 方向推理允许从已知的方向来推导未知的方向。在数据库中，这种推 理非常有用，可以用最小的计算来提供一致性计算。方向结合距离可以用 来推理位置t 2 2 1 。方向结合拓扑可以推理空间物体的位置布局【2 3 1 。 虽然现在人们通常使用主方向作为参考和交流，但是作为g i s 中的一 贯的应用来说，这种概念还是非常的模糊的。这里有在g i s 中的正式的主 方向的一些定义，例如查询语言，查询处理器，和空间推理的智能接口引 擎。空间方向关系的研究就是为了找到一种在g i s 中可以广泛应用的正式 的方向关系模型。 2 2 1 空间方向的性质和特点 空间方向具有5 个基本性质，可以概括如下1 2 4 1 。 ( 1 ) 传递性在所使用的参考框架f 中假设其主方向的集合为 d = d i ，d 2 ，d n ，n _ 2 ，砭1 ) ，目标为o i ，空间方向计算函数为c 若对空间 9 燕山大学工学硕士学位论文 方向三元组有f ( o l ，0 2 ，f ) = d ，f ( 0 2 ，0 3 ，f ) = d i ，则必有f ( o l ，0 3 ，f ) = d i 成立，此 为空间方向的传递性。 ( 2 ) 反射性若对空问方向三元组有f ( a ，b ，f ) = d i ，则必有f f b ，a ，f ) = d + 1 成立，此为空间方向的反射性。 ( 3 ) 完整性空问方向是全圆方向的覆盖，此为空间方向的完整性。 ( 4 ) 平等性空浏方向没有大小的区分，是一种平等关系，此为空间方 向的平等性。 ( 5 ) 相对性这包括两层意思：一是空间方向是相对于参考框架的，参 考框架变化，它也发生变化；二是空间方向是相对于目标指向的，指向关 系改变，空间方向也会发生变化。 空间方向还具有两个特点，简述如下。 ( 1 ) 多样性 由参考物体到目标物体的空间方向往往不能用一个角度 值或一句简单的方向描述性语言，如东、南、西、北等来表达。如我国内 蒙古和东北三省用传统的4 、8 、1 6 或3 2 方向定义的基本方向术语都无法完 备地描述二者的方向关系，需要寻求新的表达手段对空间方向多侧面进行 描述。 ( 2 ) 复杂性空间方向的判断求解并不像看上去那么简单，而是一个复 杂的空间思维和运算过程，与目标的位置、形状、大小、距离、拓扑等有 关。人们对空间方向的判断是多因素“合力”作用的结果。 2 2 2空间数据库中的方向查询 空间数据包括点、线、面等几何类型的对象。空间对象在空间上覆盖 了一定的区域，它具有一定的空间位置和边界范围特钲。通常在空间对象 上所作的方向查询是找出满足一定空间特征的所有对象，这类查询可称之 为空间查询，它经常出现在地理信息系统里面。 比如找出天安门广场北方内的宾馆。在没有任何空间索引的支持下， 查找过程需要扫描所有的天安门广场北方的范围，所以从直观上可以看蹬 这样做了很多不必要的判断。因此，如何从大量的空间对象中快速提取满 足一定空间特征的对象就成了研究的重点。 1 0 第2 章空间方向概述及模型 在空间数据库中的空间方向查询方面，g u t i n g 在文献【2 5 】中提出了在数 据模型、查询语言、空间数据类型以及空间索引领域的调查研究。搜索引 擎q - t r e e 26 1 、r t r e e 2 7 l 是在空间数据库中的数据模型中应用最为广泛的模 型。为了检索给定方向上的数据，p a p a d i a s f 2 8 】使用r t r e e 来定义一个基于参 考物体的搜索范围，返回与查询区域相交的物体。这种理论包括了基于几 何物体的无遗漏的搜寻。正式的方向模型允许方向关系可以被清楚的存储 在数据库中，以方便使用方向来作为查询条件。 f r a n k l i n 2 9 1 最近的研究表明，如果人们把他们的周围的平面空间分成 相交的前，后，左，右四个方向区域，那么就会存在如前和右这样的两个 方向交界的部分。 同样，主方向在人们的思想中也存在交界的部分，例如北和东，不同 的人会有不同的认识。例如，一些人可能会认为北是一个物体前方的直角 行区域，另一些人会认为是通过物体中心点的一条线，而另外些人会认 为是一个参考物体北方的矩形区域。不同的人在讨论方向关系的时候会有 不同的表示，但是在g i s 查询中需要正式的方向定义，因此方向模型必须 是正规的。 2 2 3 空间方向的参考框架 空间方向的参考框架就是在研究空间方向关系时所使用的参照系统。 空间方向的描述是基于一定的空间方向参考框架的。方向是在空间方向参 考框架的基础上，用来记录一个有序的物体对a 和b 之间的一种二元关系， 其中a 是目标物体，b 是参考物体。参考框架使用方向符号来划分空间。如 果参考框架改变了，方向也就相应的发生改变。 空间方向参考框架主要有内部参考框架、直接参考框架和外部参考框 架三类，下面分别进行简要介绍瞰l 。 ( 1 ) 内部参考框架该框架是指一个目标在自身内部建立的方向参照 系统，多用前、后、左、右等术语描述，如图2 1 ( a ) 所示。例如，一个居民 住宅，正门入口为前，阳台为后，卧室为左，其他房间物品的空间方向可 依此确定。 燕山大学工学硕士学位论文 ( 2 1 直接参考框架该框架基于观察者的观点，以自己的前、后、左、 右等对空间进行划分，建立空间方向判断的参照系统。直接参考框架如图 2 1 ( b 、所示。 ( 3 ) 外部参考框架该框架是根据地球表面选择的北方向( 磁北、真北、 坐标北等) 建立的参考框架，如图2 1 ( c ) 所示。 ( a ) 内部参考框架 ( a ) i n t r i n s i cr e f e r e n c ef r a m e 左 右西 后南 ( b ) 直接参考框架 ( b ) d i r e c tr e f e r e n c ef r a m e 东 ( c ) 外部参考框架 ( c ) e x t r i n s i cr e f e r e n c ef r a m e 图2 1空间方向的3 种参考框架 f i g u r e2 - 1t h r e er e f e r e n c ef r a m e so f s p a t i a ld i r e c t i o n s 内部参考框架用于小尺度的地理空间，直接参考框架用于人们的日常 方向判断描述。在g i s 中，地理空间目标的空间方向参考框架是典型的外 部参考框架。 在地理信息系统里面有关几何物体之间的方向研究主要使用主方向来 进行描述，所以在本文的讨论中物体之间的方向关系是基于外部参考框架 的主方向模型。 2 3 空间方向模型 方向关系模型的表示能力在研究地理信息系统里面是至关重要的【3 0 】。 在将来地理信息系统将会提供多种用户界面应用模型，提供语音查询等多 种功能1 3 ”。例如用户可以使用自然语言询问，“查找中国长江以北的所有 的河流”，地理信息系统将会具有提供这个查询结果的功能。 这种空间推力任务对人类的智能来说是非常容易的，但是为了使用计 算机的帮助来完成这些任务，则需要正式的空间方向模型。下面首先介绍 第2 章空间方向概述及模型 空间方向模型的必备属性，然后再按照空间方向模型的不同类型分别进行 简要的介绍。 2 3 1方向模型的必备属性 为了满足空间方向关系推理的需要，空问方向关系模型必须具备一定 的属性。下面对空洲方向关系模型的些必备属性进行简要的介绍怛。 ( 1 ) 正式性模型必须是唯一j 下式的，以满足对方向信息进行处理的一 致性需要。 在地理信息系统中，经常用到方向作为条件的空间查询，例如“搜索 黄河以北的所有城市”。但是，在涉及空间方向信息时，如果不同的人所使 用的方向模型不是唯一正式的模型，那么就会有不同的表示和不同的认识， 就会出现描述和理解上的差异【2 9 】。因此，在空间方向信息处理和g i s 查询 中，需要正式唯一的方向定义和方向模型。 ( 2 ) 可推理性模型必须是可以推理的，即可以从已知的关系中推理得 到未知关系。 使用自然语言描述物体的位置经常和已知物体进行关联。位置和海拔 使用地理信息语言来描述空间关系【3 2 】。为了执行关于空间物体位置的空间 推理，把枯燥的语言转为测量坐标，例如自然语言“沿着长江北方1 l o o 米 的地方”，可以使用己知位置的地理坐标转换为所描述的相关的横坐标和纵 坐标的位置关系。主方向关系的模型必须支持从已知的方向推导出未知的 方向关系，就是说必须具有可推理性。 ( 3 ) 形状敏感性模型必须能够表示出不规则物体的真实形状，而不是 近似的形状表示，即模型必须是形状敏感的。 几何物体的形状会影响他们之间的方向关系 3 3 , 3 4 。几何物体可能有多 种形状并会在多种角度进行旋转。例如，物体可能有大的凸起，物体会包 围另一个物体，物体之间相互交叉等。在特定的位置上的物体的形状的一 些改变，甚至会影响一个物体与另一个物体之间的方向关系。因此，几何 物体的方向模型必须能够表示出物体形状的变化所带来的方向关系的变 化，称之为方向关系模型的形状敏感属性。 燕山大学工学硕士学位论文 为了记录几何物体的形状带来的变化，方向模型不能对几何物体进行 近似处理，只能使用几何物体的真实形状。现存的模型都是对几何物体进 行矩形近似或者是点近似，所以他们忽略了物体形状的变化对物体间的方 向关系所带来的影响，进而产生错误的结论。所以，方向模型必须能够表 示所有的物体的真实形状和方向，即必须是形状敏感的。 ( 4 ) 可运算性模型必须能够支持方向关系的运算，即模型必须具有可 运算性。 在地理信息系统中，存储着物体的几何属性和视觉属性，从而决定了 该物体的所在和与其他物体的相互关系1 3 5 】。而方向关系就是几何属性中的 一种。当用户从已知的物体方向关系推导其他可能的方向关系时，就是进 行方向关系的运算，这是空间方向关系推理的基础。所以，空间方向模型 必须支持方向关系的运算，即方向模型必须具有可运算性。 2 3 2 定量的方向模型 在用方位角表示空问方向的定量方向模型中，目标点的方向主要使用 的是相对于一个参考点的方位角来定义的。方位角是一个通过参考点的子 午线和参考点到目标点的连线之间的角度，如图2 2 所示，其中a 为参考点， q 目标点，a 为b 相对于a 的方位角。 n o r t h x b ，y b ) 图2 2 方位角定义 f i g u r e2 - 2t h ed e f i n i t i o no f a z i m u t ha n g l e 子午线上所有的点相对于参考点来说在正北方向，也就是方位角为0 0 。 对所有的其他点的方位角，是将子午线位置的直线以参考点为中心顺时针 方向旋转到测量线位置时转过的角度。方位角“可用公式( 2 1 ) 来计算，取 1 4 第2 章空间方向概述及模型 值范围为f o o ，3 6 0 0 ) 。 厂、 a ：t a n “| 盟i( 2 1 1 y h y 。) 对于那些大于或等于3 6 0 0 的角则循环映射到这个区间。例如1 3 6 0 0 映射 为0 0 ，4 5 0 0 映射为9 0 。 两个点之间的定量的方向关系使用方位角的角度来测量。它们的值可 以近似的用在如陆地测量或者是机器设计等领域中。但是，空间数据库中 的查询语言使用的是定性的方向而不是定量的方向。因此本文重点介绍的 是定性的方向模型和定性的方向关系。 2 3 3定性的方向模型 定性的方向关系相对于定量的方向关系来说是对方向关系的一种更为 粗糙的近似，并且使用更少的符号集来记录方向关系的信息。例如，整个 方向区间 o o , 3 6 0 0 ) 会被划分为四个或者是八个方向区域，每一个区域表示 一种方向关系。四个区域的方向系统使用的首要方向是东、南、西和北。 八个区域的方向系统使用的首要方向是北、东北、东、东南、南、西南、 西和西北。 人们经常使用定性的空间推理而不是定量的空间推理，这主要是因为 定性的空间信息已经能够满足人们信息交流的需要，而定量的信息反而不 容易理解，在人们的头脑中不能很快得到结果。因此，人们使用地理信息 系统的时候很少使用像“查找与北京方位角为4 3 0 3 4 的所有的湖泊”这样 的查询，而是经常使用类似“查找所有位于北京西北方向的湖泊”这样的 查询。 定性的空间推理是采用的是定性的方向模裂。下面就定性的方向模型 进行分类讨论。 ( 1 ) 基于锥形的点物体方向模型基于锥形的系统把参考点周围的空 间划分为互不相交的分别间隔为9 0 0 或者4 5 0 的四个部分或l 个部分3 6 1 ，如 图2 3 所示。其中四方向系统使用定性的方向北、东、西和南，而八方向系 统还要使用额外的东北、东南、西北和西南四个方向。 燕山大学工学硕士学位论文 如果目标物体与参考物体重叠，则称之为与自身相同。包括与自身相 同方向关系在内，四方向系统区分了5 种方向关系，八方向系统区分了9 种 方向关系。目标物体相对于参考物体的方向关系由目标物体占据根据参考 点划分的方向区域决定。例如，在圈2 3 ( a ) 所示的四方向系统中，目标物体 6 相对于参考物体口的方向关系为北( a d ，而图2 3 ( b ) 所示的八方向系统中目 标物体b 相对于参考物体口的方向关系为东北( 幻。 、弩 n wa e ，s 、 ( a ) 四方向系统 ( a ) f o u r - d i r e c t i o ns y s t e m ( b ) 八方向系统 ( b ) e i g h t - d i r e c t i o ns y s t e m 图2 3 锥形法模型 f i g u r e2 - 3t h ec o n e b a s e dm o d e l ( 2 ) 基于投影的点物体方向模型基于投影的点物体方向模型使用通 过参考物体的垂直线和水平线来划分空间，如图2 4 所示。一条水平线把空 间划分为北( 的与南两部分，而一条竖直线把空间划分为东( 毋与西( 聊 两部分，同时使用水平线与竖直线则把空间划分为东n ( s 互9 、东北( 腮) 、 西南 叻、西北( 聊四个部分。 图2 4 基于投影的点物体方向模型 f i g u r e2 - 4t h ep r o j e e 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 基于投影的点物体方向模型中包括表示四种方向的四个区间以及四条 线和一个点。四个区间表示东南、东北、西南、西北四个方向，四条线代 表东、南、西、北，而中心点则表示与本身相同方向关系。 棠一 一一一 0 引 一 墨州 一 第2 章空间方向概述及模型 基于投影的模型相对于锥形表示模型的优势有：基于投影的模型类似 于地图中的经度纬度刚；与基于锥形的模型相比，该模型有大量精确的合 成推论；与基于锥形模型划分空间的角度问题相比，基于投影的模型相对 来说更容易在数据库中实现。 基于锥形的模型更容易被扩展，用来支持更多的方向划分，例如划分 为1 6 或者3 2 个方向区间。但是人们日常使用的表示方向关系的方向划分很 少会多于9 种，所以本文所使用的方向模型主要是基于投影的。 ( 3 ) 点物体与线型物体之间的方向模型f r e k s a ； l l z i m m e r m a n n 提出了 如图2 5 所示的一个方向关系参考框架，用来表示点