Есть таблица в БД с координатами в формате 55.888755,37.430337 и сами заданные координаты в таком же формате. Как найти ближайшие координаты к заданным координатам? Интересен сам алгоритм, а не код конечно=)
Напишу алгоритм "в лоб".
Пройтись по каждой точке в БД - найти расстояние между двумя точками (между заданной точкой и точкой в базе);
Среди этих значений найти минимальное.
Думаю, все зависит от количества точек в базе. Если их ну очень много, то поиск будет долгим, согласен. А если их мало, то зачем усложнять?
Если точек много, то тут уже лучше разбить на несколько баз данных. Чем больше точек всего, тем больше дробление БД.
Допустим есть прямоугольная карта - 100 км на 500 км. Делим на квадраты - 10х10 км. Создаем 500 БД. Определяем в каком квадрате находится заданная точка. Проходим по точкам в БД этого квадрата и соседних (точка может быть на стыке квадратов). Ищем минимальное расстояние.
Но повторюсь, всё зависит от ситуации. Нужно пробовать, проводить эксперименты, это лучший вариант.
Для каждой точки находим hashcode -- бинарное отображение координаты. Индексируем побайтно такой хешкод. Для искомой точки также строим hashcode.
В первом приближенини, чем ближе точки друг к другу тем более похожа у них левая часть хешкода. Т.о. вам нужно найти точки с минимальным отличием хемкода от заданного. По индексу это сделать проще (сложность O(log n)), чем перебором всех точек (сложность O(n)).
Простой
Простой
