Определить, в каких полигонах точка

Question

У меня огромные потоки точечных данных (в 2D) (тысячи в секунду). На этой карте у меня есть несколько фиксированных полигонов (от десятков до нескольких сотен из них).

Я хотел бы определить в режиме реального времени (порядка нескольких миллисекунд на довольно мощном ноутбуке) для каждой точки, в которой лежат многоугольники (многоугольники могут пересекаться). Я думал, что буду использовать алгоритм наведения лучей.

Тем не менее, мне нужен способ предварительной обработки данных, чтобы избежать сканирования каждого полигона. Поэтому я рассматриваю использование подходов дерева (PM quadtree или Rtree?). Есть ли другой соответствующий метод? Есть ли хорошая реализация PM Quadtree, которую вы бы порекомендовали (на любом языке, предпочтительно C(++), Java или Python)?

Answer 1

Я разработал библиотеку нескольких многомерных индексов на Java, ее можно найти здесь. Он содержит R*Tree, STR-Tree, 4 дерева квадрантов (2 для точек, 2 для прямоугольников) и дерево критических битов (может использоваться для пространственных данных путем чередования координат). Я также разработал PH-Tree.

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

Я обычно нахожу PH-дерево наиболее эффективным деревом, оно имеет быстрое время построения и очень быстрое время запроса, если точка пересекается с 100 прямоугольниками или менее (даже лучше с 10 или менее). STR/R*-деревья лучше с большими размерами перекрытия (1000+). Квадроды немного ненадежны, у них есть проблемы с числовой точностью при вставке миллионов элементов.

Предполагая, что трехмерное дерево с 1 миллионом прямоугольников и в среднем одним результатом на запрос, PH-Tree требует около 3 микросекунд на запрос на моем рабочем столе (i7 4xxx), то есть 300 запросов в миллисекунду.