Ближайшая координата маршрута к заданной точке с использованием алгоритма поиска (python)
У меня есть маршруты, которые представлены в виде координат с широтой/долготой. В зависимости от длины маршрута он может иметь 100 или даже 800 координат. Затем у меня снова есть конкретная координата с широтой/долготой, которая представляет мое местоположение. Я пытаюсь найти ближайшую точку (координату) на пути к моему местоположению. Я могу сделать это с помощью формулы гаверсинуса, вычисляющей расстояние от каждой точки маршрута до моего местоположения, и взять минимум, но это может занять слишком много времени, потому что некоторые маршруты очень длинные и есть много точек для сравнения. Есть ли алгоритм поиска, который может помочь решить эту проблему? Я провел исследование поиска по золотому сечению, но не был уверен, что это то, что я искал.
Ответы 1
Я могу придумать два способа решить эту проблему. Можно было бы создать дерево K-D для каждого из маршрутов и запросить новую точку координат в каждом дереве для поиска ближайшей точки. Проверьте научный набор KDTree
Другая более простая возможность заключается в том, что вы создаете каждый маршрут в виде массива, используете некоторую метрику между вашей точкой и каждым массивом и находите тот, где метрика минимальна, например. используя Евклидово расстояние
import numpy as np
from sklearn.metrics import euclidean_distances
x = np.array([[0.1, 0.5]])
route = np.random.rand((10,2))
array([[0.78275588, 0.92844543],
[0.30066744, 0.21161873],
[0.95533462, 0.11647814],
[0.37786273, 0.58306683],
[0.86670199, 0.90861542],
[0.68658895, 0.60087646],
[0.19966574, 0.57160265],
[0.34182302, 0.02809684],
[0.08862117, 0.89459785],
[0.18083728, 0.39331416]])
dist = euclidean_distances(x,route)
array([[0.80605278, 0.35132774, 0.9373827 , 0.29001344, 0.8687914 ,
0.59519968, 0.12272001, 0.53025557, 0.39476188, 0.13385266]])
Затем, если мы получим argmin, как вы можете видеть, ближайшая точка — это 6-й элемент
np.argmin(euclidean_distances(x,route))
6