一种Voronoi Diagram与虚拟网格结合的高效空间最近邻查询方法

摘要

本发明公开了一种VoronoiDiagram与虚拟网格结合的高效空间最近邻查询方法，包括以下步骤：（1）使用VoronoiDiagram划分二维空间中的数据点，形成N个VoronoiCell；（2）使用虚拟网格将二维空间划分为若干个网格单元，确定网格单元的边长并进行编号；（3）设计计算虚拟网格单元和VoronoiCell之间的对应关系的方法，并存储在一个哈希表中；（4）计算查询点位置所在的网格单元，并确定对应的网格单元的编号；（5）在哈希表中查找查询点位置所在的网格单元所对应的VoronoiCell，并从中计算选择距离查询点位置最近的数据点返回给用户。本发明适用于大规模均匀分布的二维数据集，能够将空间最近邻查询的时间复杂度从O(logN)降低到O(1),极大地提高了空间最近邻查询的效率。

主权项

一种Voronoi Diagram与虚拟网格结合的高效空间最近邻查询方法，其特征在于，包括以下步骤：A:使用Voronoi Diagram划分二维空间中的数据点，形成N个Voronoi Cell，N为数据点个数，每个Voronoi Cell为一个凸多边形且仅包含1个数据点；B:使用虚拟网格将二维空间划分为若干个等大的正方形网格单元，确定网格单元的边长，并对虚拟网格进行编号；C:设计计算虚拟网格单元和Voronoi Cell之间的对应关系的方法，并将该对应关系存储在一个哈希表中；D:计算查询点位置所在的网格单元，并确定查询点位置所对应的网格单元的编号；E:根据步骤D中计算出的网格单元编号，在步骤C中所建立的存储网格单元与Voronoi Cell对应关系的哈希表中，查找查询点位置所在的网格单元所对应的Voronoi Cell，并从中计算选择距离查询点位置最近的数据点返回给用户。