Нахождение ближайшей точки к набору точек (в лат / лонг)
Мне дан случайный набор точек (не сказано, сколько) с широтой и долготой, и мне нужно их отсортировать.
Затем мне дадут другую случайную точку (широта / долгота), и мне нужно будет найти точку, ближайшую к ней (из набора выше).
Когда я реализую линейный поиск (поместите набор в список, а затем рассчитайте все расстояния), это займет примерно в 7 раз больше времени, чем разрешено.
Итак, мне нужен гораздо более эффективный алгоритм сортировки, но я не уверен, как я мог бы это сделать, тем более что мне дают точки, которые не существуют на плоской плоскости.
1 ответ
Если ваши точки распределены умеренно хорошо, то геометрическое хеширование - это простой метод для ускорения поиска ближайших соседей на практике. Идея состоит в том, чтобы просто зарегистрировать ваши объекты в ячейках сетки и выполнить поиск по ячейкам, чтобы вы могли ограничить свой поиск локальным соседством.
Эта небольшая демонстрация Python применила эту идею к кругу на плоскости:
Так что в вашем случае вы можете выбрать несколько фиксированных N и разбить координаты долготы в [0, 2pi] на N равных частей, а координаты широты в [0, pi] на N частей. Это дает вам N^2 клеток на сфере. Вы регистрируете все свои начальные точки в этих ячейках.
Когда вам задают точку запроса p, вы начинаете поиск в ячейке, в которую попадает p, и в достаточно большом районе, так что вы не можете пропустить ближайшую точку.
Если вы изначально зарегистрировали n точек, вы можете выбрать N для чего-то вроде sqrt(n)/4 или около того.