Мой набор данных состоит из множества прямоугольников, лежащих в плоскости x, y (представленной набором четырех точек). В 99,9% случаев эти прямоугольники не перекрываются, но очень редко. Я пытаюсь найти оптимальную структуру данных для хранения прямоугольников, чтобы я мог найти случаи пересечения.
Кстати, прямоугольники содержат текст, поэтому я делаю это для того, чтобы найти совпадения одного и того же текста. Это потому, что такие вхождения следует рассматривать как один прямоугольник текста вместо двух.
Например: допустим, я ищу текст «123». Есть два прямоугольника. Первый прямоугольник содержит «ТЕСТ 123», а второй - «123». Если «123» перекрывается с «123» в первом прямоугольнике (в пределах заданного порогового значения), тогда мой результат поиска должен возвращать только одно вхождение текста «123».
До сих пор я вкратце рассмотрел квадродеревья, r-деревья, k-d деревья и деревья диапазонов. Я мало знаю об этих деревьях, и я не знаю, подойдет ли какое-либо из них для решения этой проблемы. Я чувствую, что r-дерево не было бы оптимальным в этом случае, потому что вероятность перекрытия очень мала.
