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

Direction Region Query Method Based on Voronoi Diagram

针对空间中方向区域查询效率不高的问题,通过引入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.