python - 大量的 x,y 坐标。在彼此一定距离内找到任何东西的有效方法？

Question

我在 pandas 数据框中有大量数据点，列中包含这些点的 x/y 坐标。我想识别数据框中任何其他点的一定距离“d”内的所有点。

我首先尝试使用“for”循环来做到这一点，检查第一个点与所有其他点之间的距离，然后是第二个点与所有其他点之间的距离，等等。显然，这对于大数据来说效率不高放。

最近在线搜索表明最好的方法可能是使用 scipy.spatial.ckdtree，但我不知道如何实现它。我看到的大多数示例都针对单个 x/y 位置进行检查，而我想检查所有与所有。是否有人能够提供建议或示例，从我的数据框中获取的 x/y 坐标数组开始，如下所示:

points = df_sub.loc[:,['FRONT_X','FRONT_Y']].values  

看起来像这样:

[[19091199.587  -544406.722]
 [19091161.475  -544452.426]
 [19091163.893  -544464.899]
 ...
 [19089150.04   -544747.196]
 [19089774.213  -544729.005]
 [19089690.516  -545165.489]]

理想的输出将是彼此之间的截止距离“d”内的所有点对的 ID。

Answer 1

scipy.spatial有许多处理距离计算的好函数。

让我们创建一个包含 1000 (x, y) 个点的数组 pos，类似于您在数据框中的内容。

import numpy as np
from scipy.spatial import distance_matrix

num = 1000
pos = np.random.uniform(size=(num, 2))

# Distance threshold
d = 0.25

从这里我们将使用 distance_matrix计算成对距离的函数。然后我们使用 np.argwhere 找到所有小于某个阈值 d 的成对距离的索引。

pair_dist = distance_matrix(pos, pos)

ids = np.argwhere(pair_dist < d)

ids 现在包含“在彼此截止距离“d”内的所有点对的 ID”，如您所愿。

缺点

当然，这种方法有一个缺点，就是我们总是计算每个点和它自己的距离(返回0的距离)，它总是小于我们的阈值d。但是，我们可以使用以下代码从我们的 ids 中排除 self 比较:

pair_dist[np.r_[:num], np.r_[:num]] = np.inf
ids = np.argwhere(pair_dist < d)

另一个缺点是，当我们只真正需要上三角或下三角成对距离矩阵时，我们会计算完全对称的成对距离矩阵。但是，除非这种计算确实是您代码中的瓶颈，否则我不会为此担心太多。