Python - рассчитать минимальное евклидово расстояние двух списков точек (координат) - PullRequest
Новая
       10

Python - рассчитать минимальное евклидово расстояние двух списков точек (координат)

0 голосов
/ 27 февраля 2020

У меня есть два списка формы n, и каждая точка будет сравниваться (евклидово расстояние) с каждой точкой второго списка, а затем будет выбрано минимальное расстояние, например:

A: [(1, 1), (2,1), (3,1)]

B: [(2,2), (3,3)]

На выходе будет 3 расстояния:

мин ((1,1) -> (2,2), (1,1) -> (3,3)),

мин ((2,1) -> ( 2,2), (2,1) -> (3,3)),

мин ((3,1) -> (2,2), (3,1) -> (3, 3))

-> евклидово расстояние

Сложно сделать эффективный код.

Ответы [ 3 ]

1 голос
/ 27 февраля 2020

Вот пример кода, который может помочь: 

from scipy.spatial import distance

A = [(1,1),(2,1),(3,1)]
B = [(2,2),(3,3)]

min_dist = []
for a in A:
    dist = []
    for b in B:
        dist.append(distance.euclidean(a,b))
    min_dist.append(min(dist))

>> min_dist
>> [1.4142135623730951, 1.0, 1.4142135623730951]

Я использую библиотеку scipy для этого. Также возможно использование numpy.linalg.norm. Этот подход работает для вас?

HTH.

0 голосов
/ 27 февраля 2020

Зависит от того, что вы подразумеваете под «эффективным». Если у вас есть большие списки, и вы собираетесь проводить много сравнений, вам нужно просто найти минимальное квадратное расстояние, которое гораздо быстрее вычислить, потому что вы избегаете квадратной операции root. Это стандартный хак при работе с евклидовыми расстояниями.

Если в итоге вам нужно фактическое евклидово расстояние, , то возьмите квадрат root.

Рассмотрим : 

import numpy as np

A = [(1, 1), (2, 1), (3, 1)]
B = [(2, 2), (3, 3)]

# compare each point in A to all points in B, return the shortest distance

for pt in A:
    min_sq_dist = min( (pt[0] - t[0])**2 + (pt[1] - t[1])**2 for t in B )
    print(np.sqrt(min_sq_dist))

Вывод: 

1.4142135623730951
1.0
1.4142135623730951

В чем большая разница? Код выше вычисляет 3 квадратных корня. Наивный подход вычисляет 6 (| {B} | раз больше)

0 голосов
/ 27 февраля 2020

Я нашел способ, я не знаю, может ли кто-то сделать его более эффективно, 

import numpy as np
from scipy.spatial import distance

s1 = np.array([(0,0), (0,1), (1,0), (1,1)])
s2 = np.array([(3,2), (1,9)])
print(distance.cdist(s1,s2).min(axis=1))
# array([3.60555128, 3.16227766, 2.82842712, 2.23606798])
...