1

我正在解决一个问题,我有大量(> 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,最接近网格点的数据点的索引。我觉得这需要很长时间才能遍历每个网格点的每个数据点。

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

4

3 回答 3

1

看看一个看似相似但 2D 的问题,看看你是否不能用那里的想法来改进。

从我的脑海中,我在想你可以根据它们的坐标(三个独立的数组)对点进行排序。当您需要最接近[X, Y, Z]网格点的点时,您将快速定位这三个数组中的点并从那里开始。

于 2012-07-10T10:46:59.000 回答
1

此外,您实际上并不需要欧几里得距离,因为您只对相对距离感兴趣,这也可以描述为:

abs(deltaX) + abs(deltaY) + abs(deltaZ)

并节省昂贵的功率和平方根...

于 2012-07-10T10:51:40.357 回答
0

无需为每个网格位置迭代您的数据点:您的网格位置本质上是有序的,因此只需迭代一次数据点,并将每个数据点分配给围绕它的八个网格位置。完成后,某些网格位置的数据点可能太少。检查相邻网格位置的数据点。如果您有大量数据点要处理(这取决于您的数据分布方式),您已经可以在初始通道中选择 20 个最近的邻居。

附录:您可能还想重新考虑算法的其他部分。您的算法是一种分段线性插值,并且有很多相对简单的改进。与其将空间划分为均匀分布的立方体,不如考虑分配多个中心点并动态重新定位它们,直到数据点与最近中心点的平均距离最小化,如下所示:

  1. 将每个数据点分配到其最近的中心点。
  2. 将每个中心点重新定位到可以最小化从“其”点(到数据子集的“质心”)的平均距离的坐标。
  3. 一些数据点现在具有不同的最近中心点。重复步骤 1. 和 2. 直到收敛(或足够接近)。
于 2012-07-10T13:57:44.380 回答