У меня есть сценарий, где у меня есть х миллионов долготы.ничего лучше ограничивающих прямоугольников?
Если добавлена новая длинная/точка lat, я хочу знать эффективно, что другие точки находятся в пределах заданного пользователем параметра расстояния, поэтому я могу добавить их в список.
получил что-то лучшее, чем ограничивающие коробки?
Мне бы хотелось увидеть алгоритмы, ссылки и несколько реализаций;) Благодарим вас!
Существует несколько вариантов, которые лучше, в основном основаны на space partitioning.
Обычный и часто очень хороший вариант (который не слишком сложный для реализации) заключается в использовании KD-Tree. Quadtrees проще реализовать, но медленнее для поиска. В зависимости от распределения ваших данных и ваших требований другие алгоритмы разделения пространства могут работать лучше, иметь более низкие требования к памяти или другие связанные с этим проблемы.
Я определенно согласен, что он хочет сделать некоторое разбиение пространства. Ему придется изменить концепцию квадранта, чтобы заставить ее работать, поскольку она предназначена для двумерного пространства, в котором области прямоугольны. Ему также нужно будет беспокоиться об обертывании, как справедливо указывает Носдрена. – PeterAllenWebb
Да, но квадранты и деревья kd можно использовать в этих ситуациях. Quadtrees проще, поскольку в этом случае обработка упаковки становится намного проще.Однако, как правило, вы не имеете дело с глобальным случаем, в таких ситуациях, но в меньшем регионе, и в этом случае большинство из этих проблем менее проблематичны. –
Коллега сказал мне, что у него был хороший опыт использования Morton-Code в качестве пространственного индекса по данным ГИС, возможно, это то, что стоит исследовать.
Я использовал коды Мортона в базе данных с десятками миллионов записей - они работают хорошо. –
Этот быстрый и грязный подход может сэкономить вам некоторое горе: разделите поверхность земли на 1 градус коробки. Затем у вас будет массив элементов размером 180x360, и вам нужно будет только найти небольшое количество ящиков, включая коробку, содержащую новую точку, и все ящики, расположенные непосредственно вокруг нее, для которых один из углов находится на заданном пользователем расстоянии. Вы обнаружите, что есть некоторые трюки, которые вы можете использовать, чтобы быстро определить, какие ящики использовать, не учитывая их всех. Просто не забывайте о широте и долготе.
Если ваши «единственные» имеют миллионы очков, и они не группируются в горячие точки, это может вас охватить.
Теоретически превосходный способ: вы можете сопоставить каждую точку в трехмерном пространстве, а затем сохранить их в octree, что позволит вам быстро найти близлежащие точки на произвольном расстоянии. Конечно, расстояние в трехмерном пространстве будет немного отличаться от расстояния большого круга на земном шаре, поэтому вам придется вычислить коэффициент преобразования. Это должно быть просто. Вы не упомянули язык реализации, но почти наверняка будет хорошо протестированная реализация octree для любого языка, на котором вы работаете. Если вы не возражаете, вставляя сторонний код, это решение является способом идти.
Это как раз был дан ответ несколько минут назад здесь: http://stackoverflow.com/questions/1847310/count-number-of-points-inside-a-circle-fast – hirschhornsalz
Помните, что long/lat странно, потому что расстояния изменение на основе широты. Если все данные находятся в пределах страны, это не имеет большого значения. Но я видел, как люди забывают об этом на глобальных наборах данных. – Nosredna
О, и не забывайте, что долгота обертывается, конечно. :-) – Nosredna