python - 查找距离网格位置最近的 n 个数据点

Question

我正在解决一个问题，其中有大量(> 400 万)数据点位于三维空间中，每个数据点都有一个标量函数值。这由四个数组表示:XD、YD、ZD 和 FD。元组(XD[i], YD[i], ZD[i])指的是数据点i的位置，其值为FD[i]。

我想在与我的数据相同的空间中叠加一个由 100x100x100 点组成的直线网格。该网格的设置如下。

[XGrid, YGrid, ZGrid] = np.mgrid[Xmin:Xmax:Xstep, Ymin:Ymax:Ystep, Zmin:Zmax:Zstep]
XG = XGrid[:,0,0]
YG = YGrid[0,:,0]
ZG = ZGrid[0,0,:]

XGrid 是网格中每个点的 x 值的 3D 数组。 XG 是从 Xmin 到 Xmax 的 x 值的一维数组，间隔距离为 XStep。

我想使用插值算法，我必须根据每个网格点周围的数据找到该函数的值。在此算法中，我需要 20 个最接近(或至少接近)我感兴趣的网格点的数据点。也就是说，对于网格点(XG[i]，YG[j]，ZG[k])我想找到20个最接近的数据点。

我能想到的唯一方法是使用一个 for 循环遍历每个数据点，然后使用一个嵌入的 for 循环遍历所有(这么多!)数据点，计算欧几里德距离，并选出 20 个最接近的的。

for i in range(0,XG.shape):
  for j in range(0,YG.shape):
    for k in range(0,ZG.shape):

      Distance = np.zeros([XD.shape])

      for a in range(0,XD.shape):
        Distance[a] = (XD[a] - XG[i])**2 + (YD[a] - YG[j])**2 + (ZD[a] - ZG[k])**2

      B = np.zeros([20], int)
      for a in range(0,20):
        indx = np.argmin(Distance)
        B[a] = indx
        Distance[indx] = float(inf)

这将为我提供一个数组 B，其中包含最接近网格点的数据点的索引。我觉得这会花费太长时间来遍历每个网格点的每个数据点。

我正在寻找任何建议，例如如何在计算距离之前组织数据点，这可以减少计算时间。

Answer 1

看看看似相似但二维的 problem看看你是否无法利用那里的想法进行改进。

从我的头脑中，我认为您可以根据坐标(三个单独的数组)对点进行排序。当您需要距离[X, Y, Z]网格点最近的点时，您将快速找到这三个数组中的点并从那里开始。