如何高效地找到两个非常大的三维坐标数组中点之间的最小距离值？

Question

假设我们有两个三维坐标点的数组。

A = (1000000, 3) 类型为浮点数， B = (100000, 3) 类型为浮点数

对于A中的每个坐标，我想找到与B中任意坐标的最小欧几里得距离。这意味着它应该计算A[0]与B中所有坐标之间的欧几里得距离，然后取最小值。

我编写了使用循环来实现此功能的代码。它可以工作，但由于我的数组大小，需要超过一个小时才能完成。伪代码大致如下：

minDistances = np.zeros(A.shape)
for i in range(len(A)):
  queriedPoint = A[i]
  distances = B - queriedPoint
  euclideanDistances = np.linalg.norm(distances, axis=1)
  minDistance = np.min(euclideanDistances)
  minDistances[i] = minDistance

理想情况下，我希望能将其向量化，但这样做似乎会因为内存使用而导致程序崩溃。有没有什么更高效的方法或技巧可以解决这个问题？我在想是否可以将问题简化为更容易处理的形式，或者重新思考如何解决它。谢谢！

- C West

---

这个回答解决了你的问题吗？在Python中找到两个列表中点之间的最小距离 - Woodford

这个回答解决了你的问题吗？在Python中找到两个列表中点之间的最小距离 - Woodford

关键是，_取最小值_。那个问题的大部分答案中的方法都是蛮力法（尽管提到了KD树）。 - Reinderien

从关键的角度来看，选择最小值。那个问题的答案中大多数方法都是蛮力法（尽管提到了KD树）。 - Reinderien

@Reinderien 你很难证明哪种方法是“最高效”的。无论如何，这两个帖子都在问同一个问题，而且两个问题中的示例代码产生了相同的结果。这个问题是重复的。 - Woodford

Answer 1

最快的方法可能是使用scipy.spatial.KDTree。建议的重复推荐使用scipy.spatial.distance.cdist，但是你的数组太大了，会消耗太多内存。

import numpy as np
from scipy.spatial import KDTree

rng = np.random.default_rng(42)
A = rng.uniform(low=-100, high=100, size=(1_000_000, 3))
B = rng.uniform(low=-100, high=100, size=(100_000, 3))

tree = KDTree(B)
distances = tree.query(A)[0]

我不知道变量A和B的实际值范围，所以我只使用了“（-100，100）”。这段代码需要运行约2.2秒。

- jared

Answer 2

暴力方法需要进行NxN次距离计算。

一个更简单的方法是使用“桶排序”，即使用一些特殊的盒子。

构建盒子大约需要4N次计算。例如，首先确定每个数组的最大和最小X、Y、Z坐标。然后将“空间”分割成64个盒子用于array_1，另外64个盒子用于array_2。

通过简单的顶点比较，您可以得到两个盒子（每个数组一个）之间更近的盒子。是的，这是一种暴力方法，但对于小数据量来说还是可以接受的。 注意：如果盒子相交或存在多个近似对，则需要一个候选列表，更多的盒子，但仍然不是初始的大数据量。

然后在数组上运行新的遍历。只获取那些位于盒子列表中的点。

最后，您可以对选择的点运行暴力方法。

对于最坏情况，即array_1的大多数盒子与array_2的某些盒子相交（或距离相同），然后将每个盒子再分成八个较小的盒子并重新检查。最坏情况可能比使用数组的暴力方法还要糟糕，但这种情况很少见。

- Ripi2

Answer 3

如果这两个数组被完全随机的数字填充，那么也许没有什么可以做的。如果每个数组对应于例如一个车辆轨迹，那么你应该考虑一下豪斯多夫距离和弗雷歇度量。

- J_H

Answer 4

是的，所以最好的方法是将问题分解为子问题，采用分而治之的算法；因此，根据上面的伪代码，我们可以尝试使用字典和列表推导来解决它。

import numpy as np
A = np.random.rand(1000000,3)
B = np.random.rand(1000000,3)

minDistance = {i: np.linalg.norm(B-A[i],axis=1).min() for i in range(len(A))}
minDistance = [minDistance[i] for i in range(len(A))]

print(minDistance)

通过使用字典和列表推导，它们有助于优化时间和复杂度。希望这能帮到你。

或者，你可以尝试基于循环的方法。

import numpy as np
from scipy.spatial.distance import cdist

A = np.random.rand(1000000,3)
B = np.random.rand(1000000,3)

minDist = np.zeros(len(A))

for i, coord in enumerate(A):
    distances = cdist(np.expand_dims(coord,axis=0),B)
    minDist[i] = np.min(distances)
print(minDist)

- mfundo_debug

---

虽然它们可能会产生正确的结果，但这两种解决方案都非常不优化，并且不适合这个应用程序。它们每个运行需要数十分钟。 - jared

虽然它们可能会产生正确的结果，但这两种解决方案都非常不优化，并且不适合这个应用。它们每个运行需要数十分钟。 - jared

虽然它们可能会产生正确的结果，但这两种解决方案都非常不优化，不适合这个应用。它们每个运行需要数十分钟。 - undefined