Как найти все расстояния между точками в матрице без дубликатов?

Question

У меня есть матрица Nx3, которая содержит координаты x, y, z N точек в трехмерном пространстве. Я хотел бы найти абсолютные расстояния между всеми точками без дубликатов.

Я пытался использовать scipy.spatial.distance.cdist () [см. документацию здесь: https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html]. Однако выходная матрица содержит дубликаты расстояний. Например, расстояние между точками P1 и P2 рассчитывается вдвое как расстояние от P1 до P2 и снова как расстояние от P2 до P1. Смотрите вывод кода:

>>> from scipy.spatial import distance
>>> points = [[1, 2, 3],
...           [4, 5, 6],
...           [7, 8, 9]]
>>> distances = distance.cdist(points, points, 'euclidean')
>>> print(distances)
[[ 0.          5.19615242 10.39230485]
 [ 5.19615242  0.          5.19615242]
 [10.39230485  5.19615242  0.        ]]

Я бы хотел, чтобы вывод был без дубликатов. Например, найдите расстояние между первой точкой и всеми остальными точками, затем второй точкой и оставшимися точками (исключая первую точку) и т. Д. В идеале, эффективным и масштабируемым образом, который сохраняет порядок точек. То есть, как только я найду расстояния, я бы хотел их запросить; например находить расстояния в пределах определенного диапазона и иметь возможность выводить точки, соответствующие этим расстояниям.

Answer 1

Похоже, что в общем случае вам нужна реализация KDTree с query_pairs.

from scipy.spatial import KDTree
points_tree = KDTree(points)
points_in_radius = points_tree.query_pairs(radius)

Это будет намного быстрее, чем на самом деле вычисление всех экземпляров и применениедопуск.