KDTree для долготы/широты

Двоичное дерево поиска не может справиться с зацикливанием полярного представления по своей конструкции. Возможно, вам потребуется преобразовать координаты в трехмерное декартово пространство, а затем применить ваш любимый алгоритм поиска, например, kD-Tree, Octree и т. д.

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

Я считаю, что BallTree от scikit-learn с метрикой Haversine должен помочь вам.

В качестве примера:

from sklearn.neighbors import BallTree
import numpy as np
import pandas as pd

cities = pd.DataFrame(data={
    'name': [...],
    'lat': [...],
    'lon': [...]
})

query_lats = [...]
query_lons = [...]

bt = BallTree(np.deg2rad(cities[['lat', 'lon']].values), metric='haversine')
distances, indices = bt.query(np.deg2rad(np.c_[query_lats, query_lons]))

nearest_cities = cities['name'].iloc[indices]

Обратите внимание, что это возвращает расстояния, предполагающие сферу радиусом 1, чтобы получить расстояния на Земле, умноженные на радиус = 6371 км.

видеть:

• https://jakevdp.github.io/blog/2013/04/29/benchmarking-nearest-neighbor-searches-in-python/
• https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html
• https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.haversine_distances.html#sklearn.metrics.pairwise.haversine_distances