Блог

У меня есть маршруты, которые представлены в виде координат с широтой / длиной. В зависимости от протяженности маршрута он может иметь 100 или даже 800 координат. Затем у меня снова есть конкретная координата с широтой / длиной, которая представляет мое местоположение. То, что я пытаюсь сделать, это найти ближайшую точку (координату) на маршруте к моему местоположению. Я могу сделать это с помощью формулы haversine, вычисляющей расстояние от каждой точки маршрута до моего местоположения, и взять минимальное, но это может занять слишком много времени, потому что некоторые маршруты действительно длинные и есть много точек для сравнения. Существует ли алгоритм поиска, который может помочь решить эту проблему? Я провел исследование по поиску золотого сечения, но не мог быть уверен, что это то, что я искал.

Я могу придумать два способа, которыми вы могли бы решить эту проблему. Одним из них было бы создание K-D дерева для каждого из маршрутов и запрос вашей новой координатной точки в каждом дереве для поиска ближайшей точки. Проверьте sci-kit 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