Quad-Trees, вероятно, будут работать хуже, чем растеризация — по сути, они представляют собой повторную растеризацию в изображения 2x2... Но определенно используют растеризацию для всех простых случаев, потому что тестирование растра должно быть настолько быстрым, насколько это возможно. . И если вы можете легко решить 90% своих задач, у вас будет больше времени для остальных.

Также не забудьте сначала удалить дубликаты. Индексы часто дублируются, и они явно избыточны для тестирования.

R*-деревья, вероятно, стоит попробовать, но вам нужно очень тщательно их реализовывать.

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

Основная идея объединения состоит в том, чтобы построить два дерева — одно для точек, другое для полигонов. Затем вы начинаете с корневых узлов каждого дерева и рекурсивно повторяете следующее до конечного уровня:

• If one is a non-directory node:
  • If the two nodes do not overlap: return
  • Решите с помощью эвристики (вам нужно будет выяснить эту часть, для начала может подойти «большее расширение»), какой узел каталога расширять.
  • Рекурсивно переходите к каждому новому узлу, а также к другому неоткрытому узлу как к новой паре.
• Leaf nodes:
  • fast test point vs. bounding box of polygon
  • медленная тестовая точка в полигоне

Вы можете еще больше ускорить это, если у вас есть быстрый внутренний тест для многоугольника, в частности, для прямоугольника в многоугольнике. Это может быть достаточно хорошо, если оно приближенное, если оно быстрое.

Для получения более подробной информации выполните поиск по запросу пространственное объединение r-tree.

Попробуйте использовать четырехъядерные деревья.

По сути, вы можете рекурсивно разделить пространство на 4 части, а затем для каждой части вы должны знать: а) многоугольники, которые являются надмножеством данной части, б) многоугольники, которые пересекают данную часть.

Это дает некоторый коэффициент накладных расходов O(log n), который может вас не устроить.

Другой вариант — просто разделить пространство с помощью сетки. Вы должны сохранить ту же информацию или каждую часть сетки, что и в случае выше. Это имеет только некоторые постоянные накладные расходы.

Оба этих варианта предполагают, что распределение полигонов как-то однородно.

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