基于Voronoi图的方向区域查询方法  

Direction Region Query Method Based on Voronoi Diagram

作　　者：刘润涛[1,2] 董庆宇 吴昊天 LIU Runtao;DONG Qingyu;WU Haotian(Institute of Information and Scientific Computing Technology,Harbin University of Science and Technology,Harbin 150080,China;Department of Mathematics,College of Science,Harbin University of Science and Technology,Harbin 150080,China)

机构地区：[1]哈尔滨理工大学信息与科学计算技术研究所,哈尔滨150080 [2]哈尔滨理工大学理学院数学系,哈尔滨150080

出　　处：《计算机工程与应用》2022年第8期83-89,共7页Computer Engineering and Applications

基　　金：国家自然科学基金(11871181)。

摘　　要：针对空间中方向区域查询效率不高的问题,通过引入Voronoi图,利用其特性对数据空间进行划分,提出了基于Voronoi图的方向区域查询方法。该方法在基于Delaunay三角网生成的Voronoi图索引结构基础上,将首结点与查询对象连线形成有向线段,利用Voronoi图可以通过邻接生成点延展的特点确定查询对象的位置,通过判断空间对象与查询区域的位置关系,将相应关联数据点加入候选集,并判定该数据点是否为正确结果,从而得到查询结果集。理论研究和实验结果表明,该方法在确定查询点位置的过程中有效减少了非必要数据的访问,在过滤阶段大大减少了候选集中点的数量,从而提高了空间数据的方向区域查询效率。In order to solve the problem of low efficiency of direction region query in space, Voronoi diagram in computational geometry is introduced to divide the data space, and a direction region query method based on Voronoi diagram is proposed. This method is based on the index structure of Voronoi diagram generated by Delaunay triangulation. Firstly,the first node is connected with the query object to form a directed line segment, by using Voronoi diagram, the location of query object can be determined by the feature of point extension generated by adjacency. Then, by judging the location relationship between the spatial object and the query region, adding the corresponding related data points to the candidate set, and determining whether the data point is the correct result, it gets the query result set. The theoretical research and experimental results show that this method can effectively reduce the access of unnecessary data in the process of determining the location of query points. In the filtering stage, the number of candidate points is greatly reduced, thus the efficiency of direction region query of spatial data is improved.

关 键 词：方向区域查询 VORONOI图 DELAUNAY三角网 索引结构 开放区域 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]