Структура данных для определения пересечения прямоугольника с большим набором прямоугольников

Question

Мой набор данных выполнен из множества прямоугольников, которые лежат на плоскости x, y (представлены набором четырех точек). 99,9% времени эти прямоугольники не будут перекрываться, но очень редко они будут. Я пытаюсь найти оптимальную структуру данных для хранения прямоугольников, чтобы найти экземпляры пересечения.

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

Например: Предположим, что я ищу текст «123». Есть два прямоугольника. Первый прямоугольник содержит «TEST 123», а второй содержит «123». Если «123» перекрывается с «123» в первом прямоугольнике (в пределах заданного порога), тогда мой результат поиска должен возвращать только одно вхождение текста «123».

До сих пор я кратко рассмотрел квадранты, r-деревья, деревья k-d и деревья диапазона. Я мало знаю об этих деревьях, и не знаю, будет ли кто-нибудь работать над этой проблемой. Я чувствую, что r-tree не будет оптимальным в этом случае, потому что вероятность перекрытия очень мала.

Answer 1

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

Насколько мне известно, очень мало выделенных алгоритмов, кроме, может быть, TOUCH algorithm (оптимизированное R-дерево, я думаю). Поэтому я бы использовал подход грубой силы, выполнив для каждого прямоугольника один запрос окна в вашем наборе данных.

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

1. Менее 100 прямоугольников или около того? Тогда любой индекс должен быть точным.
2. Вам нужно обновить набор данных в какой-то момент? Или все в порядке, чтобы загрузить все один раз, а затем выполнить поиск?
3. Вы хотите сохранить индекс на диске или он будет в памяти?

Для дисков на диске обычно рекомендуются варианты R-Tree, такие как дерево R * или X-дерево. Однако R-деревья, как правило, менее эффективны с обновлениями, но обычно используются с начальной массовой загрузкой. Запросы Windows в R-Tree имеют тенденцию работать лучше с большими наборами результатов, но это может зависеть от фактического набора данных.

Quadtrees должно быть в порядке для вашего «редкого» набора данных, они также просты в реализации, но требуют большой памяти и не идеальны для использования на диске.

Если вы используете Java, посмотрите на мой PH-Tree, он немного похож на квадрант, но обладает гораздо большим пространством и отлично работает с большими наборами данных, поддерживает обновления и имеет очень быстрые запросы к окну, особенно если результирующие множества малы (0 или 1 результат). Это может быть именно то, что вам нужно, за исключением того, что оно несколько сложно реализовать (моя версия - Java и Apache v2 лицензирована), и в настоящее время нет эффективного способа сохранить его на диске.