Получить ближайшую координату в 2D массиве

Question

coordinates = [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]

xy = (-222.4, -204.5)

Каков наилучший способ сравнения заданного значения xy с двухмерным списком координат и возврата номера индекса ближайшей координаты?

В этом примере xy будет сравниваться со списком координат и, таким образом, будет возвращать ближайшую координату (-225,0, -299,5) или, в идеале, номер индекса 0.

Я пытался найти метод с помощью itertools или numpy, но, похоже, не мог понять, как получить желаемый результат в моем примере.

Answer 1

Использование scipy.spatial.KDTree:

from scipy import spatial
import numpy as np
coordinates = [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]
x = [(-222.4, -204.5)]
distance,index = spatial.KDTree(coordinates).query(x)
print(distance)
print(index)

Метод дерева kd - это O (N * log (N)) и он намного быстрее, чем метод грубой силы, который требует O (N ** 2) времени для достаточно большого N.

Answer 2

Вы можете использовать min с соответствующей key функцией. Sth вдоль следующих строк, например:

coordinates = [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]
xy = (-222.4, -204.5)

dist = lambda x, y: (x[0]-y[0])**2 + (x[1]-y[1])**2
min(coordinates, key=lambda co: dist(co, xy))
# (-225.0, -299.5)

Answer 3

Ваш вопрос эквивалентен: Как отсортировать список Python, используя пользовательский метод для определения ключа сортировки. Это можно сделать в сыром python без использования внешних библиотек.

При использовании функции Python sorted() вы можете передать лямбду аргументу key, чтобы выполнить сортировку по определенному ключу.

Оттуда вам просто нужно определить ключ как ваш собственный метод расчета расстояния (здесь, используя расстояния между точками):

from math import *
coordinates = [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]
xy = (-222.4, -204.5)
results = sorted(coordinates, key= lambda v: sqrt(pow((v[0] - xy[0]), 2) + pow((v[1] - xy[1]), 2)))
# Output : [(-225.0, -299.5), (-150.0, 75.5), (0.0, 0.0), (225.0, 300.5)]

Оттуда вы можете просто взять первый элемент списка, если вы хотите приблизить точку и т. Д. Если вы все еще хотите использовать внешний модуль, я думаю, что вы можете использовать некоторые сторонние функции, такие как from scipy.spatial import distance, в качестве ключевого параметра сортировка.

Answer 4

Вы можете просто создать функцию, которая выполняет итерацию по списку координат и сохранить индекс той, в которой расстояние между двумя точками является наименьшим (используя теорему Пифагора).

Однако, если выМне нужно что-то быстрое, что было дано внешним модулем, а не написано вашим собственным, я не знаю, какие библиотеки я уже использовал, у которых уже есть эта функция, поэтому я здесь не помог.