计算机应用 ›› 2015, Vol. 35 ›› Issue (2): 452-455.DOI: 10.11772/j.issn.1001-9081.2015.02.0452

• 人工智能 • 上一篇    下一篇

连续多方向区域查询的空间向量模型算法

刘润涛, 赵振国, 田广悦   

  1. 哈尔滨理工大学 应用科学学院, 哈尔滨 150080
  • 收稿日期:2014-08-29 修回日期:2014-11-20 出版日期:2015-02-10 发布日期:2015-02-12
  • 通讯作者: 刘润涛
  • 作者简介:刘润涛(1961-),男,黑龙江东宁人,研究员,博士,主要研究方向:空间数据库技术、计算几何; 赵振国(1990-),男,黑龙江桦南人,硕士研究生,主要研究方向:空间数据库技术、计算几何; 田广悦(1960-),男,黑龙江哈尔滨人,副教授,主要研究方向:计算几何。
  • 基金资助:

    黑龙江省教育厅2011年科学技术研究项目(12511103)。

Space vector model algorithm for query of continuous and multidirectional regions

LIU Runtao, ZHAO Zhenguo, TIAN Guangyue   

  1. College of Applied Sciences, Harbin University of Science and Technology, Harbin Heilongjiang 150080, China
  • Received:2014-08-29 Revised:2014-11-20 Online:2015-02-10 Published:2015-02-12

摘要:

针对判定空间对象间方向关系模型不能给出带有方向特征的定量分析,导致查询区域只是单方向开放区域的问题,结合向量运算和MB树,提出了一种能够解决连续开放区域的方向关系查询空间向量模型算法。该算法主要包括对查询目标进行过滤和提纯两个步骤。在过滤过程中,分析了查询区域与包含空间目标的最小边界矩形(MBR)顶点之间的位置关系,给出了相应的判断方法,利用MB树中MBR的有序性对被查询节点的MBR给出了有效的剪枝规则,从而使查询时能有效减少系统I/O;在提纯过程中,处理过滤步骤中筛选出来的与查询区域有交的MBR,从中找到位于查询区域中的目标点。实验结果表明,空间向量模型算法不仅可以解决单方向开放区域问题,而且能够有效地解决连续多方向区域查询问题,它在二维和三维空间都具有适用性。

关键词: 方向查询, 连续区域, 多方向区域, 开放区域

Abstract:

The directional relations between spatial objects cannot be quantitatively analyzed with directional feature in existing models, which caused regional query to be involved in only single-direction open region. To resolve this problem, a space vector model algorithm combined with vector operation and MB-tree was proposed to deal with directional relation query in continuous and open regions. The proposed algorithm mainly included two steps. One was filtration, and the other was purification. In the process of filtration, the relations between query region and the vertexes of space object's Minimum Bounding Rectangles (MBRs) were analyzed quantitatively and the corresponding judging method was given. Effective pruning rule for nodes of MB-tree was given to reduce I/O cost when directional query was executed by the order of MB-tree. In the process of purification, in order to find actual target objects, MBRs which were saved in the filtration step were traversed. The experiments show that the proposed algorithm can not only solve the query of single open region, but also solve the query of continuous and multidirectional region. In addition, the algorithm can be used in two- and three-dimensional spaces.

Key words: directional query, continuous region, multidirectional region, open region

中图分类号: