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