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

摘要

针对空间中方向区域查询效率不高的问题,通过引入Voronoi图,利用其特性对数据空间进行划分,提出了基于Voronoi图的方向区域查询方法。该方法在基于Delaunay三角网生成的Voronoi图索引结构基础上,将首结点与查询对象连线形成有向线段,利用Voronoi图可以通过邻接生成点延展的特点确定查询对象的位置,通过判断空间对象与查询区域的位置关系,将相应关联数据点加入候选集,并判定该数据点是否为正确结果,从而得到查询结果集。理论研究和实验结果表明,该方法在确定查询点位置的过程中有效减少了非必要数据的访问,在过滤阶段大大减少了候选集中点的数量,从而提高了空间数据的方向区域查询效率。