Как рассчитать расстояние между n координатами в python

Question

Я работаю над проектом python, где из функции я получаю значения координат x, y в dict, как показано ниже:

centroid_dict = {0: (333, 125), 1: (288, 52), 2: (351, 41)}

, где 0, 1, 2 являются objectId и (333, 125), (288, 52), (351, 41) их значениями (x, y) соответственно. Мне нужно вычислить расстояние между каждой координатой, что означает:

0 - 1 -> ((333, 125) - (288, 52))

0 - 2 -> ((333, 125) - (351, 41))

1 - 0 -> ((288, 52) - (333, 125))

1 - 2 -> ((288, 52) - (351, 41))

2 - 0 -> ((351, 41) - (333, 125))

2 - 1 -> ((351, 41) - (288, 52))

Чтобы вычислить расстояние, я могу использовать:

def calculateDistance(x1, y1, x2, y2):
    dist = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return dist

, но я не могу думать ни о каких логах c, который может рассчитать расстояние между каждой точкой, поскольку длина dict может увеличиться в будущем. На данный момент это 3, но это может быть 10. Может кто-нибудь, пожалуйста, помогите мне дать некоторые идеи по этому поводу. Спасибо

Answer 1

Вы можете использовать комбинации из itertools для формирования нового словаря с каждой парой объектов в качестве ключа:

from itertools import combinations:
distances = dict()
for (id1,p1),(id2,p2) in combinations(centroid_dict.items(),2):
    dx,dy = p1[0]-p2[0], p1[1]-p2[1]
    distances[id1,id2] = distances[id2,id1] = math.sqrt(dx*dx+dy*dy)

Недостаток этого подхода заключается в том, что он будет систематически вычислять все расстояния, и вашей программе может не понадобиться чтобы получить доступ ко всем этим ценностям. Более эффективным подходом может быть использование словаря в качестве кэша расстояния и получение их «по требованию» с помощью функции:

distanceCache = dict()
def getDist(id1,id2):
    if id1 > id2: return getDist(id2,id1) # only store each pair once
    if (id1,id1) in distanceCache: return distanceCache[id1,id2]
    x1,y1 = centroid_dict[id1]
    x2,y2 = centroid_dict[id2]
    dx,dy = x1-x2,y1-y2 
    return distanceCache.setDefault((id1,id2),math.sqrt(dx*dx+dy*dy))

Это позволит вам просто очистить кэш при расположении объектов изменяются без немедленной задержки O (n ^ 2) времени

Обратите внимание, что вы также можете использовать сами точки (позиции) в качестве ключа к кешу, а также использовать кеш LRU (из functools)

from functools import lru_cache
import math

@lru_cache(1024)
def getDist(p1,p2):
    dx,dy = p1[0]-p2[0],p1[1]-p2[1]
    return math.sqrt(dx*dx+dy*dy)

def getObjectDist(id1,id2):
    return getDist(centroid_dict[id1],centroid_dict[id2])

Answer 2

Вы можете сделать что-то вроде этого. Импорт не требуется.

def dist(key1,key2):
    return calculateDistance(*centroid_dict[key1],*centroid_dict[key2])

all_dist = []
for key1 in centroid_dict:
    all_dist.extend([dist(key1,key2) for key2 in centroid_dict if not key1==key2])

Answer 3

с использованием решения из здесь , это проблема с графом дерева kd

Найти евклидовы расстояния между четырьмя двумерными координатами:

from scipy.spatial import distance
coords = [(35.0456, -85.2672),
          (35.1174, -89.9711),
          (35.9728, -83.9422),
          (36.1667, -86.7833)]
distance.cdist(coords, coords, 'euclidean')

array([[ 0.    ,  4.7044,  1.6172,  1.8856],
   [ 4.7044,  0.    ,  6.0893,  3.3561],
   [ 1.6172,  6.0893,  0.    ,  2.8477],
   [ 1.8856,  3.3561,  2.8477,  0.    ]])