0

目标

我有一个 3D 空间中大约 500K 点的列表。我想找到具有最大第一最近邻距离的两个坐标。

方法

我正在使用 scipy 计算稀疏距离矩阵：

from scipy.spatial import cKDTree

tree = cKDTree(points, 40)
spd = tree.sparse_distance_matrix(tree, 0.01)
spo = spd.tocsr()
spo.eliminate_zeros()

我消除了显式零以解释计算每个点与其自身之间距离的对角线元素。

我现在想找到每行/列中最小距离的坐标，它应该对应于每个点的第一个最近邻居，例如：

spo.argmin(axis=0)

通过找到该数组中元素的最大距离，我应该能够找到具有最大第一最近邻距离的两个元素。

问题

问题是min和的argmin函数scipy.sparse.csr_matrix也考虑了隐式零，这对于这个应用程序我不想要。我该如何解决这个问题？有了这个庞大的矩阵，性能和内存都是问题。或者对我想做的事情有完全不同的方法吗？

4

1 回答 1

0

我没有找到距离矩阵的解决方案，但似乎我忽略了使用query树方法的最明显的解决方案。

因此，为了找到我所做的第一个最近邻居之间的最大距离（使用向量一个形状为 (N, 3) 的 numpy 数组）：

tree = cKDTree(vectors, leaf_size)
# get the indexes of the first nearest neighbor of each vertex
# we use k=2 because k=1 are the points themselves with distance 0
nn1 = tree.query(vectors, k=2)[1][:,1]
# get the vectors corresponding to those indexes. Basically this is "vectors" sorted by
# first nearest neighbor of each point in "vectors".
nn1_vec = vectors[nn1]
# the distance between each point and its first nearest neighbor
nn_dist = np.sqrt(np.sum((vectors - nn1_vec)**2, axis=1))
# maximum distance
return np.max(nn_dist)
于 2020-10-05T08:45:51.780 回答