Эффективное упорядочение местоположений по их географическому расстоянию от точки запроса

Question

Я пытаюсь найти метод, который эффективно, возможно O (log (n)), находит заданное количество ближайших местоположений к местоположению запроса, учитывая их географические координаты (широта, долгота).

Точка запроса заранее неизвестна, но я могу заранее организовать другие местоположения для оптимизации запроса.

Есть ли такой метод или мне нужно заказать и обрезать список всех пиров?

Answer 1

Если ваша поверхность удовлетворяет неравенству треугольника, т.е. является евклидовым пространством, лучший алгоритм для переупорядочения пространственного индекса - это кривая заполнения пространства или кривая монстра.Он сводит 2-мерную задачу к 1-мерной и дискретизирует и решает проблему адресации пространства.Поиск похожих мест похож на O (log (n)).Вы можете найти хорошую статью в блоге quadtree.Предлагаю посмотреть на n-арные монотонные серые коды тоже.Я написал себе реализацию php, включающую кривую Гильберта в 4 направлениях и кривую Мура.