我问了一个关于VP Trees and Nearest Neighbors 的堆栈溢出性能问题的问题，我对答案不满意，所以我想我会为这个网站改写我的问题并将这个问题作为计算科学问题发布。

我正在使用VPTree来存储我的稀疏数组的坐标，因为数据位于球体/椭圆体上，并且我想使用大圆距离或测地线来进行最近邻搜索，如相关问题中所问 -具有纬度和的快速最近邻搜索经度。VPTree 的创建本身不是问题，因为它发生得非常快（我大约有 7000 分）。我通过以下方式创建了一个规则网格，并且 minLat、maxLat、minLon、maxLon 是从包含稀疏观察矩阵的粗略数据网格中获得的。

latGrid = np.arange(minLat,maxLat,0.05)
lonGrid = np.arange(minLo,maxLo,0.05)

所以 latGrid 中的总点数是 1800，而 lonGrid 中的总点数是 7200。所以网格点的总数是 1800 * 7200 = 12960000

我正在尝试进行固定半径最近邻搜索，这就是我目前遇到的问题 -

for grid_point in (grid_points):
    indices = tree.get_all_in_range(grid_point,r=4)
    args.append(indices)

当我对 12960000 个网格点运行此查询时，需要 12 分钟，我必须运行 175 次。

我使用粗网格的 7000 个点构建 VPTree，并使用常规网格的 12960000 个点对其进行查询。

我相信发送到查询的网格点数

get_all_in_range 

可以大大减少，因为许多网格点不在稀疏矩阵坐标的范围内。问题是如何使用数学方法对网格点和粗略矩阵坐标进行“交叉”？我已经看到了这个问题的答案 - Using Morton keys or Geohashes但我不确定这是否适用于我的问题。至少我不明白如何将它应用于我的问题。同样可以使用测地线凸包来确定交点吗？