（计算机应用技术专业论文）基于开放区域的方向关系查询技术研究.pdf

摘要 摘要 空间数据库中的方向关系在地理信息系统和图像数据库等领域都有着 重要应用 它经常作为空间查询中的选择条件 而方向关系查询的效率也 成为近年来学术界普遍关心的问题 本文研究了绝对参考框架下的方向关系查询处理方法 基于现有的方 向关系模型 本文引入了一种新的开放区域模型并对其进行扩展 定义了 开放区域上相关的一些拓扑运算 把实际方向区域转化为开放区域 把对 象间方向关系的计算转化为开放区域和封闭区域之间的拓扑关系运算 传统静态方向关系查询是用范围查询技术解决的 本文使用开放区域 模型处理静态查询中的定性和定量方向关系查询 本文详细介绍了利用开 放区域对定量方向关系查询进行建模和处理的具体方法 并扩展定量查询 技术提出了不同参考框架下方向关系查询的通用算法 然后用实验证明了 开放区域查询方法与传统范围查询方法相比 在系统的c p u 花费和i 0 花 费方面的优势 本文直接针对移动对象的动态属性对方向关系查询进行处理 提出基 于开放区域模型的时间参数化方向关系查询技术 该技术摒弃了传统的利 用有限次静态方向关系查询来进行间接处理的方法 通过空间对象与查询 窗口的相交时域的计算 实现了对查询结果的实时更新 最后用实验对传 统相交时域算法与开放区域模型下相交时域算法的相对性能做了比较 并 证明了开放区域方法在性能上的优势 关键词开放区域 方向关系查询 定性查询 定量查询 时间参数化查 询 燕山大学工学硕士学位论文 a b s t r a c t b e i n gc r i t i c a li ng e o g r a p h i ci n f o r m a t i o ns y s t e m s i m a g ei n t e r p r e t a t i o n e t c d i r e c t i o nr e l a t i o n s h i p si ns p a t i a ld a t a b a s ea r eu s e da ss e l e c t i o nc o n d i t i o n s t h e e f f i c i e n c yo f t h eq u e r ya l s oa t t r a c t sm o r ec o n c e mo f a c a d e m i ai nr e c e n ty e a r s a p r o c e s s i n gm e t h o db a s e do na b s o l u t er e f e r e n c ef r a m ew a se x p l o r e di n t h i sp a p e r b a s e do nc u r r e n td i r e c t i o n a lr e l a t i o n s h i pm o d e l w ee x t e n d e da n o p e ns h a p em o d e la n dd e f i n e dt h et o p o l o g i c a lo p e r a t i o n so ni t w h i c hc o n v e y s t h ed i r e c t i o n a lr e l a t i o n s h i pq u e r yt o t o p o l o g i c a lo p e r a t i o n s b e t w e e no p e n s h a p e sa n dc l o s e dg e o m e t r yo b j e c t s r a n g eq u e ys t r a t e g yw a su s e dt oi m p l e m e n ts t a t i cd i r e c t i o n a lq u e r i e s w h i l ew eu s e do p e ns h a p et op r o c e s st h eq u a l i t a t i v ea n dq u a n t i t a t i v eq u e r i e s t h i s p a p e ri n t r o d u c e d t h e s p e c i f i cm o d e l i n ga n dp r o c e s s i n g m e t h o do f q u a n t i t a t i v eq u e r i e sb a s e do no p e ns h a p e a n dp r o p o s e dau n i v e r s a la r i t h m e t i c i nd i f f e r e n tr e f f e r e n c ef r a m ew i mq u a n t i t a t i v eq u e r yt e c h n o l o g y a n dt h e n p r o v e dt h ea d v a n t a g eo fo p e ns h a p es t r a t e g y i nc p uc o s ta n di 0c o s t c o m p a r e d w i t ht r a d i t i o n a lr a n g eq u e r ys t r a t e g yb ye x p e r i m e n t t h et i m e p a r a m e t e r i z e dd i r e c t i o n a lr e l a t i o n s h i p q u e r yt e c h n o l o g yw a s p r o p o s e di n t h i s p a p e r w h i c hc o n t r a p o s e dt h em o v i n go b j e c t s d y n a m i c a t t r i b u t i o nd i r e c t l y i ns t e a do ff i n i t e l ys t m i cd i r e c t i o n a lr e l a t i o n s h i pq u e r i e s i t c a l c u l a t e dt h eo b j e c ta n dt h eq u e r yw i n d o w si n t e r s e c t i o np e r i o da n du s e di tt o r e n e wt h er e s u l t s f i n a l l y w ec o m p a r e dt h ei n t e r s e c t i o np e r i o da r i t h m e t i c s r e l a t i v e p e r f o r m a n c eo ft r a d i t i o n a ls t r a t e g y a n do p e n s h a p es t r a t e g yw i t h e x p e r i m e n t a n dp r o v e d t h eo p e ns h a p es t r a t e g y sa d v a n t a g ei np e r f o r m a n c e k e y w o r d so p e n s h a p e d i r e c t i o n a lr e l a t i o n s h i pq u e r y q u a l i t a t i v eq u e r y q u a n t i t a t i v eq u e r y t i m e p a r a m e t e r i z e dq u e r y i i 燕山大学硕士学位论文原创性声明 本人郑重声明 此处所提交的硕士学位论文 基于开放区域的方向关 系查询技术研究 是本人在导师指导下 在燕山大学攻读硕士学位期间独 立进行研究工作所取得的成果 据本人所知 论文中除已注明部分外不包 含他人已发表或撰写过的研究成果 对本文的研究工作做出重要贡献的个 人和集体 均已在文中以明确方式注明 本声明的法律结果将完全由本人 承担 作者签字日期 5 年i 月p 日 燕山大学硕士学位论文使用授权书 基于开放区域的方向关系查询技术研究 系本人在燕山大学攻读硕 士学位期间在导师指导下完成的硕士学位论文 本论文的研究成果归燕山 大学所有 本人如需发表将署名燕山大学为第一完成单位及相关人员 本 人完全了解燕山大学关于保存 使用学位论文的规定 同意学校保留并向 有关部门送交论文的复印件和电子版本 允许论文被查阅和借阅 本人授 权燕山大学 可以采用影印 缩印或其他复制手段保存论文 可以公布论 文的全部或部分内容 保密口 在年解密后适用本授权书 本学位论文属于 不保密囱 请在以上相应方框内打 4 作者签名 形衙日期 孔形年1 1 月j 日 导师签名 歹铷 茹 日期 2 n 6 年 月 日 第1 章绪论 1 1 研究背景 第1 章绪论 在空间数据库中 方向是一个常见的概念 它常作为空间查询的选取 条件 lj 和影像相似性评估的标准 2 1 人们通常将方向作为目标对象之间的 空间关系来建立方向关系的描述模型 对方向关系的查询涉及到拓扑学和几何学的问题 是空间查询中的重 要操作 例如在可视化的战场中 3 中有如下三类方向关系查询 列出建筑 物a 南方的敌方目标 列出建筑物b 左边的所有坦克 和 列出山脊上 的所有对象 上述查询都有各自的参考框架 第一个例子是基于a 的绝 对方向的查询 第二个例子是基于对象b 本身方位的查询 第三个例子是 基于观察者方位的查询 随着空间查询处理技术日益受到关注 并广泛应用于地理信息系统 4 1 计算机辅助设计 多媒体系统 导航系统 医学和卫星图象数据库 6 1 等 领域 学术界对方向关系查询技术的研究也逐渐兴起 但由于空间数据库 中的数据量庞大 数据结构复杂 操作代价昂贵 空间查询的优化势必成 为空间应用的难点和突破点 因此优化查询也成为空间查询研究中的难点 和热点 要解决方向关系查询问题 就要在空间数据库中找出满足给定方向关 系条件的空间对象 这样 最直接的方法就是计算实际方向区域的最小边 界矩形 m b rm i n i m u mb o u n d i n gr e c t a n g l e 7 1 在r 树嗍中 无论叶子节 点还是中间节点只要它的m b r 和方向区域的m b r 相交 这些节点就被访 问 这种方法的搜索时间随着数据点数目的增加呈线性增长 由于空间数 据库中数据点的数目巨大 采用这种方法处理方向查询的效率非常低 因 此 就涉及到方向关系查询处理中的建模问题 如何建立起更合理的方向 关系模型以便在效率上改进现有方法就具备一定的研究价值了 燕山大学工学硕士学位论文 在过去的几年里 人们对方向关系查询技术的研究主要针对静态对象 而且鉴于人们日常习惯 多使用定性的查询方法 对于定量查询 由于相 应的处理比较复杂 在计算方面的开销相对较大 所以相关的研究还比较 少 这样 对于一些需要进行定量查询处理的领域 对其查询效率的改进 也就成为学术研究的一块空白 近年来 随着无线通讯和全球定位系统的迅速发展 针对移动对象的 方向关系研究和应用也成为新的研究热点 它在地理信息系统 移动计算 图像处理等方面有着重要的应用 例如 向行进的部队实时提供其某个方 向上的其他连队 为司机用户提供基于位置的服务和导航等f 9 l 由于查询 点的位置是不断变化的 为了得到最新 最准确的结果 只有随着查询点 的移动不断地更新查询结果 但这种想法是根本不现实的 目前 这种方 向关系查询的处理基本上使用的是有限次的静态方向关系查询 进行移动 轨迹上不同位置的方向关系查询得到结果 但其效率在数量巨大的空间数 据库中还不是十分有效 因此 针对移动对象方向关系查询的优化还有待 进一步的研究 提高方向关系查询算法的效率在理论方面有着重要的研究 价值 同时可以广泛地应用到相关的各个领域 1 2 国内外研究现状 在方向关系查询的过程中 不可避免地会涉及到方向关系模型的使用 目前 国内外对于方向关系模型的研究已经有很多相对成熟的理论 一般 认为 在二维空间有两种主要的方向关系模型 基于锥形的模型 1 0 和基于 投影的模型 1 1 a f r a n k 1 2 曾对这两种模型进行过比较 并发现基于投影 的模型在各方面都优于基于锥形的模型 但他将空间目标的表示限制为一 个点 对于区域目标和线目标使用目标的几何中心表示目标 忽略了目标 的大小和形状对方向关系描述的影响 对于区域对象间的方向关系则需要 根据它们的m b r 的关系表示 这种方法由d p a p a d i a s 等人 7 j 提出 但m b r 只是空间对象的几何近似 依赖于特殊的外形 有时空间对象间的方向关 系和相应m b r 间的方向关系存在不一致性 因此这种粗糙的近似值会导 2 第1 章绪论 致结果的矛盾和曲解 c f r e k s a 1 曾提出过一种可替代的方法 一维半间 隔时空关系 r o o y a l 等人 1 4 也提出了用方向关系矩阵表示主方向关系的 方法 这种方法在基于投影的参考框架上 把参考对象四周的空间进行划 分 并记录下目标对象落入的方向区域 它确保了查询过程中的方向关系 与对象的几何数据结构相互独立 但是这种方法并不适用于线对象 而且 它只限于二维空间 在文献 1 5 中对方向关系矩阵进行了扩展 它更详细 地对空间方向关系进行了描述 文献 1 6 中指出 在三维空间中 对方向 关系模型的研究目前还比较少 对于静态方向关系查询的索引 目前常见的有基于二叉树的空间索引 结构 基于b 树的空间索引结构 基于动态哈希的格网法以及基于空间目 标排序的索引方法 1 9 8 1 年 j t r o b i n s o n 提出了k d b 树的概念1 1 7 它是 基于二叉树的索引结构 由区域页和点页所构成 但它只针对多属性的数 据和多维空间点进行处理 对于其它形体的空间目标 查询比较差 1 9 8 4 年 a g u t t m a n 1 s 最早提出一种r 树索引结构 这种索引结构是b 树在多 维空间的扩展 它在叶子节点存储实际对象的m b r 在中间节点存储包括 其所有子节点m b r 的矩形 但它允许节点间重叠 这将导致在检索时的 错误命中 为了解决这一问题 1 9 8 7 年 t s e l l i s 等人1 1 9 l 提出一种r 树索 引结构 它通过对矩形的分割实现了中间节点之间的零重叠 但它占据了 较多的存储空间 对于多维空间及大型的空间数据库系统而言 r 树的索 引效率仍然很差 所以在1 9 9 0 年 n b e c k m a n n 等人 卅又提出一种r 树索 引结构 这种索引结构允许重叠 但它通过比传统r 树更复杂的算法来最 小化节点重叠的范围 实验表明 r 树的检索性能和空间利用率都得到了 较大的提高 也就是说 r 树以增加少量的构造时间开销换取了更高的查 询性能 r 树 r 树和站树都是基于b 树的索引结构 j n i e v e r g e r 等人曾 针对点目标的索引提出了网格文件的概斜2 0 1 它属于基于动态哈希的格网 法 如果用这种方法索引复杂空间目标 其空间利用率和查询效率都会很 低 典型的基于空间目标排序的索引方法有z 排序 h i l b e r t 曲线等 它们 将多维的空间目标映射成一维的目标 并在些基础上 利用现有数据库管 理系统中比较成熟的一维索引技术 来提供对一维空间数据的快速存取和 燕山大学工学硕士学位论文 检索 这种方法虽然比较简单 但经过映射后 空间目标之间的空间关系 往往会丢弃 从而影响空间查询的效率和准确性 y t h e o d o r i d i s 等人曾在 文献 2 1 对不同索引结构上绝对方向关系查询的性能做出比较 近年来 人们对静态方向关系查询技术的研究主要集中在定性处理技 术上 对于需要根据精确值处理的定量查询领域 相关研究还比较少 1 9 9 5 年 y t h e o d o r i d i s 等人 2 l 首先提出了二维空间中方向关系的范围查询方法 这种方法成为我们进行方向关系查询处理的基础技术 随后 y t h e o d o r i d i s 等人 又在1 9 9 8 年定义了空间对象问定性的方向关系 y l i u 等人矧曾给 出一种基于m b r 的主方向关系与矩形代数关系相结合的方向关系定性推 理方法 这种定性推理技术可以间接应用于方向关系定性查询之中 文献 2 4 给出了基于r 树索引结构的空间方向关系查询的一般方法 并提出利 用传统的过滤和提纯技术对查询进行处理 但文中讨论的是基于投影的方 向关系模型 对于定量查询所需的区域对象间基于锥形的模型 由于其方 位角的计算相对复杂 所以文中并没有给出具体的处理方法 闰浩文等人 曾用方向组给出一种方向关系的定量描述模型 2 5 1 s s k i a d o p o u l o s 等人 2 6 1 又针对主方向关系计算的性能问题从定性和定量两个方面提出了改进算 法 但文中所提的定量算法是基于定量拓扑关系的定量推理技术 它用于 计算空间对象间精确位置关系的量值 郭庆胜等人 2 7 1 对这种定量描述的拓 扑关系做出了分析 但它并不是本文要讨论的定量查询技术 目前常见的静态方向关系查询的处理方法大致可分为三类 第一类是 过滤和提纯技术刚 其中 过滤步骤是基于对象的m b r 快速地找出符合 查询条件的候选集合 提纯步骤 是对由过滤步骤得到的候选集合 确切 地检查该集合中的数据是否符合查询条件 第二类是范围查询技术 2 l l 范 围查询方法就是把实际的方向区域或者方向区域的m b r 看作为空间范围 进行查询 这种处理方法非常实用 第三类是方向关系矩阵i 通过记录 目标物体的真实区域落在参考物体的哪一个区域来描述方向 随着移动索引的提出 针对移动对象的空间查询技术正逐渐兴起 由 于此时空间对象的形状 位置等信息要随着时间发生变化 所以在存储时 还需要在空1 日j 数据库中增加一个时间维 形成时空数据库 4 第1 章绪论 总体来说 时空数据库的索引结构分为基于离散数据表示的和基于连 续数据表示的两类 1 9 9 8 年 m n a s c i m e m o 等人所提出的h r 树 2 8 就是一 种基于离散数据表示的索引结构 它将时间维独立出来 并保存每一时间 戳的空间数据 使用h r 树进行时间片查询 其查询性能比较好 但它对 时间段查询的效率却比较低 数据冗余较多 空间开销大 此后 s s a l t e n i s 等人1 2 叫在2 0 0 0 年提出了一种t p r 树 t p r t i m e p a r a m e t e f i z e dr t r e e 它 是典型的基于连续数据表示的索引结构 它能够存储对象的当前位置和速 度 方向等信息 支持移动对象在当前和将来的位置的有效查询 只是在 更新或查询期间 为了避免由于边界矩形 b rb o u n d i n gr e c t a n g l e 变得非 常大而导致严重的重叠 必须要考虑将边界矩形进行紧缩 2 0 0 3 年 y t a o 等人 3 0 l 针对移动对象的特定属性 利用一种新的算法对t p r 树在性能上进 行了改进 提出了t p r 树索引结构 实验证明 与t p r 树相比 t p r 树 索引结构可以有效地降低空间查询过程中磁盘的i o 花费 由于移动对象的空间查询技术还处于研究初期 所以目前没有比较系 统的理论体系 下面介绍一下比较常见的一些技术 窗口查询 w q w i n d o w q u e r y 技术 3 用于找到所有在指定时间间隔之内与所查询的区域相交的 对象 k 邻近 k n n k n e a r e s tn e i g h b o r 查询 3 2 找出在指定期间内离查询 点最近的k 个对象 对k 邻近问题的研究也是当前学术界的热点问题 距 离内连接 3 3 查询则返回在指定期间内两个数据集的笛卡尔积中的距离短 于一定极限数值的所有对象对 针对移动对象的动态属性 还有一些新的 查询方法 导航窗口查询 3 4 指定了两个查询区域和两个时间戳 检索在每 个时间戳内都与相应查询区域相交的对象 文献 3 5 提出了移动对象的时 间参数化 t p t i m e p a r a m e t e r i z e d 查询算法 它可以应用于任何传统查询 除了结果集还返回它的有效时间以及其后结果的变化 另外 文献 3 6 还 把时间参数化的概念扩展为连续查询 它也是可应用于传统查询的一个通 用概念 目的在于连续地跟踪结果的变化直到满足某一条件 时间参数化 查询和连续查询要求对象的移动方向被明确地指出 在一些不能明确指定 对象移动方向的情况下 就要用到基于位置 l b l o c a t i o n b a s e d 的查询鲫 它应用于窗口查询和k 邻近查询 并且找出查询结果和它的合法区域 使 燕山大学工学硕士学位论文 得在这一区域范围内时 查询结果保持不变 以上研究主要集中在点查询 范围查询 最邻近查询和拓扑查询等传统的空间查询 对方向关系查询的 动态扩展却很少 文献 3 8 1 只提出了移动对象方向关系查询的概念 却 没有提出具体的处理方法 1 3 本文研究的内容 目前学术界对方向关系查询技术的研究 虽然在理论方面已经取得了 不小的成绩 但对于庞大的空间数据库来说 如何提高查询效率仍是人们 所关注的问题 本文的研究主要有两个目标 一是弥补学术界在方向关系 查询技术研究过程中所忽略的方面 提出静态方向关系查询的通用算法以 及直接针对移动对象动态属性的方向关系查询处理技术 二是利用开放区 域模型在i 0 花费和c p u 花费方面改善方向关系查询技术的性能 以提高 查询效率 本文的研究内容主要包括以下三个方面 首先 在现有的空间方向关系模型的基础上 本文将应用一种更为高 效的方向关系模型 开放区域模型1 3 纠 并根据本课题的需要对这种模型 在概念上进行扩展 而且将对该模型上的拓扑运算作出定义 这样把方向 关系查询处理转化为相应的拓扑运算处理 以期改善算法性能 提高查询 效率 本文还将用实验对基于开放区域建模方式的方向关系查询技术与传 统的范围查询技术在性能方面做出比较 第二 本文将利用所扩展的开放区域模型在性能方面的优势 扩展传 统方向关系定性查询技术 提出利用开放区域模型对方向关系定量查询进 行建模的具体方法以及相应的定量查询的具体技术 并针对不同参考框架 下需要采用不同方向关系查询技术的问题 扩展绝对参考框架下的定量查 询技术 提出不同参考框架下静态方向关系查询的一种通用算法 用于改 善相关处理技术的冗杂现状 最后 本文将直接针对移动对象的动态属性提出一种基于开放区域的 时间参数化方向关系查询技术 用于改善传统的通过有限次静态方向关系 6 第1 章绪论 查询对移动对象进行间接处理的方法 在处理中 本文将利用前面所提到 的开放区域的建模方式对时间参数化查询技术中的关键算法 也就是相交 时域算法做出改进 并将以实验在性能方面对开放区域改进的算法与传统 的算法做出比较 处理方便起见 本文后面的数据对象将用绝对参考框架下的m b r 近 似表示 为了实现更有效的检索 本文的静态对象将使用r 树组织和索引 动态对象使用t p r 树组织和索引 1 4 本文的组织结构 本文后面的结构安排如下 第2 章是方向关系查询处理 本章将介绍空间方向关系查询过程中需 要用到的一些基本技术 并分析选择它们的理由 还将给出基本方向模型 的实现方法 并总结方向关系查询的一般步骤 第3 章是开放区域模型的设计 本章将介绍基本的开放区域概念 并 对它们进行扩展 本章还将介绍不同参考框架下 基于开放区域的方向关 系模型的构建方法 特别对课题实验中需要用到的开放区域的拓扑运算操 作给出定义 第4 章是静态方向关系查询技术 本章将会对开放区域模型下的静态 方向关系查询技术进行研究 分别介绍定性查询和定量查询两种技术 并 总结不同参考框架下的方向关系查询转换到绝对参考框架下的通用算法 在性能方面 本章将把上述技术与传统范围查询技术进行比较 第5 章是时间参数化方向关系查询技术 本章将针对移动对象动态属 性提出时间参数化方向关系查询技术 并利用开放区域理论对该技术的关 键算法作出改进 最后 在结论中对所研究的课题进行了总结 分析了课题的研究意义 以及应用前景 并指出了本课题今后的研究方向 燕山大学工学硕士学位论文 第2 章方向关系查询处理 2 1 空间数据结构 本节从区域对象的表示和索引结构两方面对空间数据结构进行介绍 2 1 1区域对象的表示 二维空间中 简单对象包括点 线和多边形 由于多边形的复杂程度 最高 因此本文主要讨论这种方向关系 鉴于多边形的不规则性 在空间 处理中人们都想用更少的数据对实际对象的空间信息进行几何近似 这样 既能节省存储空间 又能提高查询效率 目前最常用的是最小边界矩形 m b r 方法 刀 一个对象的m b r 定义为完全包含该对象的矩形 m b r 方法用 两个点来表示多边形对象 如图2 1 每个对象q 都可用有序对 q q 表示 其q a q f 和q s 分别记录q 的最小边界矩形q 的左下角和右上角的坐标 图2 r 1 对象q 的最小边界矩形 f i g 2 1t h em i n i m u mb o u n d i n gr e c t a n g l eo f o b j e c tq 很多空间数据结构和索引技术都是基于m b r 开发的 例如将对象的 m b r 关系作为过滤器来判断对象是否可能满足一个给定的关系 4 0 这种 方向关系是按照b a l i a n 的二维区间关系描述的 该模型可以区分1 6 9 种两 个m r b 间所有可能的方向关系 g o y a l 曾给出所有可能的组合l l 2 1 2 索引结构的选取 存储器分为内存和外存两种 访问这两种存储器一次所花费的时间一 般相差十万倍以上 尽管现在有 内存数据库 的说法 但绝大多数数据 8 第2 苹方向关系查询处理 是存储在外存磁盘上的 如果对磁盘上数据的位置不加以记录和组织 每 查询一个数据项就要扫描整个数据文件 这种访问磁盘的代价就会严重影 响系统的效率 空间索引是对存储在介质上的数据位置信息的描述 用来 提高系统对数据获取的效率 2 1 2 1 r 树索引结构对于静态查询 由于基于二叉树的索引和基于动 态哈希的格网法不适用于二维空间中的区域对象 而基于空间目标排序的 索引在技术上并不成熟 所以本文选择基于b 树的索引结构中性能相对较 高的r 树索引结构i s l r 树延续了传统的r 树结构 由中间节点和叶子节点组成 在叶子节 点存储实际对象的m b r 和索引对象的惟一标识符 在中间节点存储包括其 所有子节点m b r 的最小边界矩形和指向下一层子节点的指针 与传统r 树 不同的是 r 树通过修改插入 分裂算法 并通过引入强制重插机制对r 树的性能进行改进 r 树的算法更复杂 但在实际的检索过程中 它能够 更有效地降低错误命中 提高查询的效率 如图2 2 所示 图2 2 a 是一幅 地图 图2 2 b 是它所对应的r 树 地图中用m b r 表示区域对象 a 一幅地图 a a m a p 孽珥望 点点伽 b 对应的r 树 b t h er t r e ea c c o r d i n g l y 图2 2r 树 f i g 2 2r t r e e 2 1 2 2t p r 树索引结构对于移动对象的空间查询 无论是查询窗口还 是空间对象的移动都需要对当前对象的位置信息进行实时更新 如果采用 静态r 树进行索引 将会造成庞大的系统开销 所以需要引入动态索引结 构 但基于离散数据表示的动态索引结构并不支持对将来位置的查询 所 以本文的时间参数化查询部分将采用基于连续数据表示的索引结构 由于 t p r 树 3 0 l 在性能方面对t p r 树 2 9 1 进行了改进 所以本文采用t p r 树 9 燕山大学工学硕士学位论文 t p r 树与t p r 树一样 引入了速度边界矩形 v b v e l o c i t yb o u n d i n g r e c t a n g l e 用速度矢量将索引结构参数化 移动节点 的v b r 用o h o 表示o 在第f 维 1 0 c 2 0s t d c l d l c 2 d 2 a m o n g di sa m o n gd l d 2a n dd 3i f 3 cx o c z o c 3 0s td c l d t c 2 d 2 c 3 d 3 r o 骶 州1 c s 警o s 0 c 薯s i n 0 习 曲建前选一f i g h t 翼p f r o n t a 平移 b 旋转 a t r a n s l a t e b r o t a t e 图2 6 方位上的运算 f i g 2 6o p e r a t i o n so l lo r i e n t a t i o n s 1 3 燕山大学工学硕士学位论文 这里根据上面的讨论给出向量 方向和方位的类 在表2 3 中描述了 向量 方向和方位对象的抽象数据类型 a d t 表中属性栏表示每个类的 成员变量 在函数栏声明了各个运算的函数 表2 3 方向和方位的抽象类 t a b l e2 3a b s t r a c td a t at y p e sf o rd i r e c t i o n sa n do r i e n t a t i o n s a d t 属性类的构造函数和成员函数 v e c t o r f l o a t f l o a t f l o a tm a g n i t u d e f l o a t xv e c t o ro p e r a t o r v e c t o r v e c t o r f l o a t vv e c t o ro p e r a t o r v e c t o r 向量的类 f j o a t 2 v e c t o ro p c f a t o rx n k c 0 r v e c t o ro p e r a t o rs c a l e v e c t o r f l o a to p e r a t o rd o to r o d u c t0 v c c t o o d i r e c t i o n f l o a t f l o a t d i r e c t i o n v c c t o r d i r e c t i o nf i o 砒xd i r e c t i o no p e r a t o rc o m p o s e d i r e c t i o n 方向的类 f l o a t y d i r e c t i o no p e r a t o rr e v e r s c 向量的子类 f i n a tzf l o a to p e r a t o rd e v i a t i n n d i r e c t i o n b o o l e a nb e t w e e n d i r e c t i o n d i r e c t i o n b o o l e a na m o n g d i r e c t i o n d i r e c t i o n d i r e c t i o n p o i n t 0 p o r i e n t a t i o n f l o a t d r i e c t i o n d i r e c t i o n o r i e n t a t i o nd i r e c t i o nf r o n t o r i e n t a t i o no p e r a t o r t r a n s l a t e v e c t o r 方位的类 d i r e c t i o nr i g h t o r i e n t a t i o no p e r a t o rr o t a t e r o t a t e m a t r i x d i r e c t i o n 曲o v e 表2 3 中向量类有三个实数成员变量 表示坐标系统基本向量线性组 合的系数 给定三个实数 构造函数创建一个向量对象 向量的五个运算 被声明为成员函数 方向定义为向量类的子类 它除了继承向量的函数外 还有自己的成员函数b e t w e e n 和a m o n g 方位类有四个成员变量 t r a n s l a t e 1 4 第2 章方向关系查询处理 和r o t a t e 两个成员函数 本文将用到方向和方位对象的属性和运算 2 3 方向关系查询的步骤 方向关系查询是指从空间数据库中查找出满足某一方向关系的空间 目标的过程 比如 查找位于对象q 东南方的所有对象 在方向关系查询过程中 首先需要明确所讨论的空间对象的表示形式 以及在查询中要使用的空间索引结构 这是方向关系查询过程中最基本的 然后就可以对方向关系进行建模了 方向关系模型的合理与否直接影响着 方向关系查询的效率 所以这部分的处理需要慎重分析 最后需要根据参 考对象以及查询的条件在索引结构中检索出所需的结果对象 并添加到结 果集中 如果说前两个步骤是对方向关系查询做出必要的准备 最后一个 步骤也就是方向关系查询的最终实现 目前进行方向关系查询的一般方法通常是综合传统的范围查询方法 和过滤与提纯技术 先确定出所查询的方向区域 再从索引树的根节点开 始 逐层进行过滤 排除与方向区域不相交的中间节点 并在剩余的节点 中按索引树的层次递归地进行过滤 直至叶子节点 最后根据对象的实际 几何形状对选择出的叶子节点做出进一步提纯 得到结果集 2 4 本章小结 本章介绍了后面方向关系查询过程中需要用到的数据结构 包括区域 对象的表示方法以及空间数据的索引结构 并对选择它们的理由做出了分 析 本章还给出了方向的概念 并在此基础上介绍了基本方向模型的构造 方法 为后面的开放区域建模方式做出了必要准备 另外 本章还指出了 实现空间方向关系查询的一般步骤 燕山大学工学硕士学位论文 第3 章开放区域模型的设计 3 1 开放区域的概念 本节将引入一种新的方向关系模型 开放区域 并介绍它的概念 3 1 1基本概念 开放区域是只有部分边界被定义或者其边界超出数据空间范围的几何 区域 4 2 1 开放区域一股针对几何图形的边界不重要或者是无限的情况 例 如 开放的直线 开放的平面和开放的空间 把这些开放形状描述为抽象 的类 就可以方便地描述几何空间 下面定义基类o p e n s h a p e 来表示一个开放的几何图形 它的边界并不 是闭合的 在表3 1 中描述了基类o p e m h a p e 在开放形状上的几何和拓扑 操作 表3 1 开放区域的基类 t a b l e3 1t h eb a s i cc l a s so f o p e n s h a p e 开放区域的边界是由一组线段或者开放线段组成 它是一组更低维的 几何图形 在本文中 我们将主要讨论的是二维空间中的方向关系 其中 单边开放线段的边界包含一个端点 两边开放线段的边界是空集 开放区 域的内部是指当开放区域的边界被删除后开放形状中剩余的部分 例如单 边开放线段的内部是指除了端点之外直线上的点集 两边开放的矩形的内 部是指一个矩形区域 这个区域的边界被删除并可以向两个方向无限扩展 1 6 第3 章开放区域模型的设计 图3 1 中是二维空间中常见的几种开放区域 图3 l a 和图3 1 b 分别表示 单边开放线段和两边开放线段 图3 1 0 图3 1 d 和图3 1 e 表示开放矩 形 a 单边开放线段 a o n e e n do p e nl i n e b 两边开放线段 b t w o e n do p e nl i n e 皇 早 瞪 c 单边开放矩形 d 两边开放矩形 e 三边开放矩形 c o n e s i d eo p e nr e c t a n g l e d t w o s i d eo p e nr e c t a n g l e e t h r e e s i d eo p e nr e c t a n g l e 图3 1基本开放区域的例子 f i g 3 1e x a m p l e so f b a s i co p e ns h a p e s 表3 2 给出了图3 1 中各类型开放区域的属性和构造函数 表3 2 开放线段和开放矩形的抽象类 t a b l e3 2a b s t r a c td a t at y p ef o ro p e nl i n e sa n do p e nr e c t a n g l e s 类型 a d t 属性构造函数举例 p o i n ta m p o i n t o p e n o p e n l i n e l o p e n l i n e l p o i n t d i r e c t i o n 图3 l a d i r e c t i e nd i r l i n e p o i n ti n t e r p o i n t o p e n l i n e 2o p e n l i n e 2 p o i n t d i r e c t i o n 图3 l b d i r e c t i o nd i r p o i n tw 玎t e x l o p e n r e c t l p o i n tv e r t e x 2 o p c n r c c t i p o i n t p o i n t d i r e c t i o n 图3 l c d i r e c d o nd i r o p e n o p e n l i n e l l i n e lo p e n r e c t 2 o p e n l i n e i o p e n l i n e l r e c t a n g l e o p e n a 2图3 l d o p e n l i n e l l i n e 2o p c n r e c t 2 p o i n kd i r e c t i o n d i r e c t i o n o p e n l i n e 2l i n e o p e n r e c t 3o p e n r e c t 3 o p e n l i n e 2 d i r e c t i o n 图3 l c d i r e e t i o nd i r 通过构造函数可以构建每个类 通过端点和方向就可以定义 o p e n l i n e l 因为o p e n l i n e 2 延伸了两个端点 所以需要内部端点和一个方 向来定义 类o p e r l l i n e l 和类o p e n l i n e 2 的属性是相同的 它们之间不同 的地方是各种操作的定义 类o p e n r e c t l 是由两个矩形的端点和一个代表 1 7 燕山大学工学硕士学位论文 开放方向的方向定义 类o p e n r e c t 2 是一个两边开放的矩形 需要一个矩 形的端点和一对有序的方向定义 类o p e n r e c t 3 是半个平面或三边开放的 矩形 需要o p e n l i n e 2 和一个方向定义 它们都是开放区域的子类 3 1 2 扩展概念 由于在定量的方向关系查询中还需要在数据空间中进行任意角度的 查询 上述开放区域的基本抽象类远远不能满足需要 所以这里对它们进 行扩展 如图3 2 所示 扩展后的开放区域包括图3 2 a 所示的开放梯形 和图3 2 b 所示的开放扇形两类 p w k a 开放梯形 a o p e nt r a p e z o i d b 开放扇形 b o p e ns e c t o r 图3 2 扩展开放区域的例子 f i g 3 2e x a m p l e so f e x t e n d e do p e ns h a p e s 表3 3 给出了扩展的开放区域的属性和构造函数 表3 3 开放梯形和开放扇形的抽象类 t a b l e3 3a b s t r a c td a t at y p ef o ro p e nt r a p e z o i d sa n do p e ns e c t o r s a d t 属性构造函数举例 p o i t a tv e r t e x l p o i n tv 眦c 2 o p e n t r 印 o p e n t r a p p o i n t d i r e c t i o n p o i n t d i r e c t i o n 图3 2 a d i r e c t i o nd i r l d i r e c t i o nd i t 2 o p e n l i n e l l i n e lo p e n s e c t o p e n l i n e l o p e n l i n e l o p e n s e c t图3 2 b 1 o p e n l i n e l l i n e 2o p e n s e c t p o i n t d i r e c t i o n d i r e c t i o n 3 2 用开放区域建立方向关系模型 本节将分别在三种基本的参考框架下 介绍用开放区域对方向关系进 第3 章开放区域模型的设计 行建模的方法 3 2 1绝对参考框架下的方向关系模型 我们以绝对参考框架为例 介绍如何利用开放区域建立方向关系模型 给定两个区域对象t o 和r o 确定目标对象t o 关于参考对象r o 的方向 根据文献 4 3 1 q h 的方法 首先求出参考对象r o 的m b r 根据求得的m b r 把r o 的四周划分为九个方向区域 如图3 3 所示 m b r 是矩形a b c d 图3 3 对象t o 和r o f i g 3 3o b j e c t st oa n dr o 把九个方向区域分别表示成空间对象 如表3 4 所示 表3 4 绝对方向区域 t a b l e3 4a b s o l u t ed i r e c t i o nr e g i o n s 方向区域 图3 3 中方向区域的空间对象的描述 n w o p e n r e c t 2 o p e n l i n e 2 a u o p e n l i n e 2 a v n o p e n r e e t l b u n e o p e n r e c