есть что-нибудь лучше ограничивающих рамок?

Question

У меня есть сценарий, в котором у меня есть x миллионов точек широты долготы.

Когда будет добавлена новая точка длины / широты, я хочу знать эффективно какие еще точки находятся в пределах настроенного пользователем параметра расстояния, чтобы я мог добавить их в список.

есть что-нибудь получше ограничивающих рамок?

Я бы с удовольствием посмотрел алгоритмы, ссылки и несколько реализаций ;) большое вам спасибо!

Answer 1

Есть довольно много вариантов, которые лучше, в основном основанных на разделение пространства.

Распространенным и часто очень хорошим вариантом (который не слишком сложен в реализации) является использование KD-Дерево. Квадродеревья проще в реализации, но медленнее в поиске.В зависимости от распределения ваших данных и ваших требований другие алгоритмы разделения пространства могут работать лучше, иметь меньшие требования к памяти или другие связанные с этим проблемы.

Answer 2

Коллега сказал мне, что у него был хороший опыт использования Мортон-Код как пространственный индекс данных ГИС, возможно, это то, что стоит исследовать.

Answer 3

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

Если у вашего "единственного" есть миллионы точек, и они не сгруппированы в горячие точки, это может помочь вам пройти.

Теоретически более эффективный способ:Вы могли бы отобразить каждую точку в трехмерном пространстве, а затем сохранить их в восьмиугольник, что позволило бы вам быстро находить близлежащие точки с точностью до произвольного расстояния.Конечно, расстояние в трехмерном пространстве будет немного отличаться от расстояния по большому кругу на земном шаре, поэтому вам придется рассчитать коэффициент пересчета.Однако это должно быть просто.Вы не упоминаете язык реализации, но почти наверняка будет хорошо протестированная реализация octree для любого языка, на котором вы работаете.Если вы не возражаете против вставки стороннего кода, это решение - правильный путь.