Алгоритмическое решение для поиска ближайшего города на основе широты / долготы
Обратите внимание, есть и другие подобные вопросы, но 1) Я не задаю' не хочу полагаться на онлайн-сервис, 2) Я ищу чистое алгоритмическое решение.
У меня есть база данных городов и их широт / долгот. Я ищу способ, который, учитывая произвольные широты и долготы, находит ближайший город.
Решения, которые я могу придумать до сих пор:
Очевидное решение методом грубой силы - это, конечно, вычислить все возможные расстояния по формуле большого круга . Это также занимает много времени и составляет O (n).
Модификация алгоритма KD-Tree может работать, но я не понимаю, как изменить этот алгоритм, чтобы он работал в не декартовы координаты, как в случае широты и долготы. Мы можем предположить проекцию Меркатора , если это поможет.
Используйте базу геоданных, такую как PostgreSQL. У меня это не работает, точка.
Есть какие-нибудь идеи?