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

摘要

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

主权项

一种Voronoi Diagram与虚拟网格结合的高效空间最近邻查询方法，其特征在于，包括以下步骤：A:使用Voronoi Diagram划分二维空间中的数据点，形成N个Voronoi Cell，N为数据点个数，每个Voronoi Cell为一个凸多边形且仅包含1个数据点；B:使用虚拟网格将二维空间划分为若干个等大的正方形虚拟网格单元，确定虚拟网格单元的边长，并对虚拟网格进行编号；其中，步骤B包括以下具体步骤：B1:使用虚拟网格将二维空间划分为若干个等大的正方形虚拟网格单元，通过公式确定虚拟网格单元的边长，其中，l为虚拟网格单元边长，d为空间中所有两个数据点之间距离的最小值，ξ＝10^‑9；B2:令R为数据集中的所有数据点所构成的最小边界矩形，以R的左下角的顶点(x₀,y₀)为出发点，建立虚拟网格，并从坐标(x₀,y₀)所在的虚拟网格单元开始，从左到右、自下而上递增地对虚拟网格单元进行编号；计算坐标点(x,y)所在的虚拟网格单元编号的公式为：$id=m*\left(ceil\right(\frac{y-y_0}{l})-1)+ceil\left(\frac{x-x_0}{l}\right)-1;---\left(2\right)$其中，id为坐标点(x,y)所在的虚拟网格单元编号，m为网格的每一行所包含的虚拟网格单元的数量，ceil为上取整函数；C:设计计算虚拟网格单元和Voronoi Cell之间的对应关系的方法，并将该对应关系存储在一个哈希表中；其中，步骤C包括以下步骤：C1:计算与每个Voronoi Cell的各边相交的虚拟网格单元：对于每一个Voronoi Cell的任意一条边的两个端点e₀和e₁，计算边e₀→e₁与纵向网格线和横向网格线的交点；按照e₀到e₁方向，按照横坐标值的大小关系有序排列上述交点及e₀和e₁两个顶点所组成的点的集合；对排序之后的集合中的所有点依次计算集合中所有相邻两点的中点，对每个中点使用步骤B2中的公式(2)计算该中点所在的虚拟网格单元的编号，中点所在的虚拟网格单元所组成的集合即为与边e₀→e₁相交的虚拟网格单元；C2:计算Voronoi Cell包含的虚拟网格单元：与任意一个Voronoi Cell的各边所相交的虚拟网格单元围成的区域所包含的所有虚拟网格单元，即为Voronoi Cell包含的虚拟网格单元；C3:将与Voronoi Cell相交的虚拟网格单元、Voroni Cell包含的虚拟网格单元两者的并集组成的虚拟网格单元和该Voronoi Cell的对应关系存储在一个哈希表中，哈希表的键key即为虚拟网格单元编号，哈希表的值value即为该虚拟网格单元对应的Voronoi Cell的编号；D:计算查询点位置所在的虚拟网格单元，并确定查询点位置所对应的虚拟网格单元的编号；E:根据步骤D中计算出的虚拟网格单元编号，在步骤C中所建立的存储虚拟网格单元与Voronoi Cell对应关系的哈希表中，查找查询点位置所在的虚拟网格单元所对应的Voronoi Cell，并从中计算选择距离查询点位置最近的数据点返回给用户。