Как найти ближайщую точку из списка географических координат?

Question

[Dato38it]

Есть список географических координат в файле и одна отдельная координата, которой нету в списке. Как выбрать из списка координат ближайшую координату? Есть какой-то алгоритм?

Comments

[pfg21]

если в файле нет индекса, то перебор всех точек, нахождение расстояния от "отдельной координаты" и поиск наименьшей длины.

[Alexandroppolus]

единственная оптимизация, которая здесь доступна - сравнивать не расстояния, а квадраты расстояний

[Viktor T2]

Можно Shapely - библиотеку потыкать
https://stackoverflow.com/questions/78305001/using...

Answer 1

[Wataru]

Если у вас задача найти ближайшую к одной один раз, то весь "алгоритм" - цикл for.
Перебираете все точки из файла, считаете расстояние по формуле.

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

Если же вам надо много раз для многих точек находить ближайшую из заданных, то имеет смысл построить какой-то индекс по опорным точкам. Какое-нибудь R-tree или квадро-дерево.

Answer 2

[Steel_Balls]

Перебором считать расстояние до каждой точки и выбрать среди них минимальное