Покрытие прямоугольников

Question

У меня есть N прямоугольников со сторонами, параллельными осям X и Y.Есть еще один прямоугольник, модель .Мне нужно создать алгоритм, который бы мог определить, полностью ли модель покрыта N прямоугольниками.Я думаю, что сначала мне нужно отсортировать прямоугольники по их левой стороне (это можно сделать за O (n log n) время), а затем использовать вертикальную прямую линию.

Синий прямоугольник - это модель .

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

Это одна из задач по подготовке к тесту.Я знаю, что лучший алгоритм может сделать это за O (n log n) времени.

Answer 1

ОК, я задал достаточно вопросов, вот что-то из ответа ...

Если данные представлены в виде растра, алгоритм тривиален:

1. Создать логический массив, представляющий прямоугольник модели (т.е. синий). Установите для всех элементов значение FALSE (представляющее «не покрыто»)
2. Для каждого красного прямоугольника (игнорируйте те, которые не могут перекрывать синий), установите все элементы массива на ИСТИНА, если они находятся внутри красного прямоугольника.
3. Наконец, проверьте, установлен ли каждый элемент массива в значение ИСТИНА.

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

1. Создайте переменную с именем UnCoveredRectangle, которая инициализируется так же, как синий прямоугольник.

2. Опять же, беспокойтесь только о красных прямоугольниках, которые пересекают синий. Для каждого красного прямоугольника вычислите пересечение прямоугольника с UnCoveredRectangle. Пересечение приведет к одной из следующих ситуаций:

   2.1 Пересечение равно UnCoveredRectangle. Работа завершена.

   2.2 Пересечение «кусает» прямоугольный кусок из CoveredRectangle. Оставшийся UnCoveredRectangle будет либо прямоугольником, либо L-образным, либо U-образным. Если это сам прямоугольник, установите UnCoveredRectangle в качестве оставшегося прямоугольника и перейдите к шагу 2. Если UnCoveredRectangle имеет L- или U-образную форму, разделите его на 2 или 3 прямоугольника и выполните возврат из шага 2 ..

3. Если у вас закончились красные прямоугольники до того, как область (часть) UnCoveredRectangle будет отправлена ​​в 0, вы закончили.

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

Answer 2

Трудно понять, что вы ищете, но мне кажется, что R-дерево может сработать?