Что-нибудь лучше, чем ограничительные рамки?
У меня есть сценарий, где у меня есть x миллионов точек широты долготы.
Когда добавляется новая точка long/lat, я хочу эффективно знать, какие другие точки находятся в параметре расстояния, настроенного пользователем, чтобы я мог добавить их в список.
есть что-нибудь лучше, чем ограничительные рамки?
Я хотел бы видеть алгоритмы, ссылки и несколько реализаций;) спасибо, любезно!
3 ответа
Есть несколько вариантов, которые лучше, в основном, основаны на разделении пространства.
Распространенным и часто очень хорошим вариантом (который не слишком сложен для реализации) является использование KD-Tree. Quadtree проще в реализации, но медленнее для поиска. В зависимости от распределения ваших данных и ваших требований другие алгоритмы разделения пространства могут работать лучше, иметь меньшие требования к памяти или другие связанные с этим проблемы.
Этот быстрый и грязный подход может избавить вас от некоторого горя: разделите поверхность земли на блоки по 1 градусу. После этого у вас будет массив элементов размером 180x360, и вам нужно будет выполнить поиск только в небольшом количестве ящиков, включая поле, содержащее новую точку, и все ячейки, расположенные непосредственно вокруг нее, для которых один из углов находится в пределах указанного пользователем расстояния. Вы обнаружите, что есть некоторые приемы, которые вы можете использовать, чтобы быстро выяснить, какие коробки использовать, не рассматривая их все. Только не забывайте широту и долготу.
Если у вашего "только" есть миллионы точек, и они не объединены в горячие точки, это может помочь вам.
Теоретически превосходный способ: вы можете отобразить каждую точку в трехмерном пространстве, а затем сохранить их в октодереве, что позволит вам быстро найти близлежащие точки с произвольным расстоянием. Конечно, расстояние в трехмерном пространстве будет немного отличаться от расстояния по большому кругу на глобусе, поэтому вам придется рассчитать коэффициент пересчета. Это должно быть просто, хотя. Вы не упоминаете язык реализации, но почти наверняка будет хорошо проверенная реализация octree для любого языка, на котором вы работаете. Если вы не против вставить сторонний код, это решение является способом идти.
Коллега сказал мне, что у него был хороший опыт использования Morton-Code в качестве пространственного индекса данных ГИС, возможно, это стоит изучить.