Поиск ближайших точек на карте

Question

[Prescott]

Всем привет.

Есть большая база людей, двигающихся по карте, у каждого записана широта и долгота. Задача: быстро получить ближайших к заданной точке людей с сортировкой по расстоянию. Решение в лоб — брать ограниченный по координатам прямоугольник и обсчитывать расстояние до каждого человека в нем, но оно слишком уж в лоб.

Подскажите алгоритмы / инструменты / материалы на почитать.

Answer 1

[Prescott]

Пользователь Azy дал ссылку на исчерпывающий ответ: www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

Спасибо!

Answer 2

[Александр Коротков]

Советую также посмотреть поиск ближайших соседей в GiST индексах PostgreSQL начиная с версии 9.1. Там всё сделано куда более естественно с точки зрения пользователя.
А вообще если точки очень часто перемещаются по карте, то я бы посоветовал не пользоваться функциями СУБД, а просто построить какой-нибудь Quad-tree в памяти и искать по нему.