Найти ближайшую точку в системе координат?

Question

[elailasou]

Есть таблица в БД с координатами в формате 55.888755,37.430337 и сами заданные координаты в таком же формате. Как найти ближайшие координаты к заданным координатам? Интересен сам алгоритм, а не код конечно=)

Comments

[Владимир Мартьянов]

Трактовать координаты как координаты на декартовой плоскости и искать расстояние между двумя точками?

[elailasou]

vilgeforce: я хз что такое декартовая плоскость, просто нужно найти ближайшую точку

[Владимир Мартьянов]

junk1114: А что такое гугл вы не ХЗ?

[elailasou]

vilgeforce: можно подсказать просто?

Answer 1

[D']

1) Берем массив с точками
2) Берем заданную точку
3) Находим расстояние между точками
4) ???
5) Profit!!1

PS
По ссылке формула для координат на плоскости. Если нужно с учетом искривления земли -> гугл.

Answer 2

[TomasHuk]

Напишу алгоритм "в лоб".
Пройтись по каждой точке в БД - найти расстояние между двумя точками (между заданной точкой и точкой в базе);
Среди этих значений найти минимальное.

Comments

[Виталий]

Этот вариант не подходит из-за того что придется выполнять полный перебор таблицы, а недостатки полного перебора все знают

[TomasHuk]

Думаю, все зависит от количества точек в базе. Если их ну очень много, то поиск будет долгим, согласен. А если их мало, то зачем усложнять?
Если точек много, то тут уже лучше разбить на несколько баз данных. Чем больше точек всего, тем больше дробление БД.
Допустим есть прямоугольная карта - 100 км на 500 км. Делим на квадраты - 10х10 км. Создаем 500 БД. Определяем в каком квадрате находится заданная точка. Проходим по точкам в БД этого квадрата и соседних (точка может быть на стыке квадратов). Ищем минимальное расстояние.
Но повторюсь, всё зависит от ситуации. Нужно пробовать, проводить эксперименты, это лучший вариант.

Answer 3

[Сергей]

Если точек много (очень много), то поиск можно сузить применяя сравнение по hashcode.

Comments

[elailasou]

Каким образом это может помочь?

[Сергей]

Для каждой точки находим hashcode -- бинарное отображение координаты. Индексируем побайтно такой хешкод. Для искомой точки также строим hashcode.
В первом приближенини, чем ближе точки друг к другу тем более похожа у них левая часть хешкода. Т.о. вам нужно найти точки с минимальным отличием хемкода от заданного. По индексу это сделать проще (сложность O(log n)), чем перебором всех точек (сложность O(n)).