Блог

У меня есть два набора из n точек, как массивы Numpy, в случайном порядке. Я должен связать точки между двумя списками на основе расстояния (L2), чтобы каждая точка в list1 получала одну и только соответствующую точку, ближайшую к list2.

Мой вопрос: каков самый быстрый способ сделать это с точки зрения времени вычислений?

На данный момент я вычисляю симметричную матрицу кросс-норм (с помощью scipy.spatial.distance_matrix) и сортирую точки оттуда, выполняя цикл для нахождения наименьшей нормы во всей матрице. Затем удалите соответствующие строки и столбцы и выполняйте итерацию до тех пор, пока матрица не станет пустой. Интересно, есть ли известный более быстрый способ сделать это?

[РЕДАКТИРОВАТЬ]: Вот код и пример, который я получаю

 import numpy as np
import numpy.ma as ma
import matplotlib.pyplot as plt
from scipy.spatial import distance_matrix

rng = np.random.default_rng()
lst1 = rng.random((10, 2))
lst2 = lst1   0.1 * rng.standard_normal(lst1.shape)  # rng.random((10, 2))

mask = np.zeros((len(lst1), len(lst2)), dtype=bool)
dst = ma.array(distance_matrix(lst1, lst2), mask=mask)

ord_lst1 = []
ord_lst2 = []
for i in range(min(len(lst1), len(lst2))):
    index = np.unravel_index(np.argmin(dst), shape=dst.shape)
    ord_lst1.append(lst1[index[0], :])
    ord_lst2.append(lst2[index[1], :])

    dst[index[0], :] = ma.masked
    dst[:, index[1]] = ma.masked

fig = plt.figure()
plt.grid(True)
plt.scatter(x=lst1[:, 0], y=lst1[:, 1], label="list1")
plt.scatter(x=lst2[:, 0], y=lst2[:, 1], label="list2")
for p1, p2 in zip(ord_lst1, ord_lst2):
    plt.plot((p1[0], p2[0]), (p1[1], p2[1]), "--", color="black")
plt.legend()
 

Результат следующий:

Как вы можете видеть, огромная связь посередине между двумя очень удаленными точками может вызывать беспокойство. Однако точка списка 1 в (0.4, 0.6) имеет наиболее близкое совпадение с верхним правым списком 2, поэтому создается ассоциация и исключаются эти две точки из дальнейшего объединения.

Спасибо 🙂

Загляните в scipy.spatial.KDTree https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial .KDTree.html

Создайте KDTree из списка 2 и запрашивайте его в каждой точке списка 1

Следующий фрагмент не тестировался, поэтому может потребоваться отладка. Это должно стать началом вашего собственного дизайна

 #L1 is numpy array with shape (N,2)
#L2 is numpy array with shape (N,2)
import scipy.spatial
tree=scipy.spatial.KDTree(L2)
assoc=[]
for I1,point in enumerate(L1):
    _,I2 = tree.query(point,k=1)
    assoc.append((I1,I2))
 

assoc Переменная содержит конечные ассоциации в виде списка кортежей индексов

РЕДАКТИРОВАТЬ: чтобы помочь с проблемой неуникальных ассоциаций, одним из первых шагов может быть запуск алгоритма KDTree дважды, один раз с «основным списком» L1 и один раз с «основным списком» L2, затем сохранить только общие ассоциации между ними. затем вы можете обрабатывать оставшиеся точки как специальныйслучай.