Выяснить, скрыт ли прямоугольник прямоугольниками над ним?

Question

У меня есть коллекция прямоугольников и ссылочный прямоугольник. Я хочу выяснить, полностью ли скрыт эталонный прямоугольник прямоугольниками над ним (все они в коллекции). Например:

http://i54.tinypic.com/246w57l.png

Очевидное решение состоит в том, чтобы создать матрицу bools или растровое изображение и просто скопировать все прямоугольники и проверить, есть ли что-то, что не покрыто, но это не вариант. Это должно быть сделано много раз в секунду.

Я придумал эту идею: для каждого прямоугольника пересекайте его с любым другим прямоугольником (и ограничивайте их ссылочным прямоугольником), в результате чего получается коллекция меньших прямоугольников, которые не пересекаются, например: http://i54.tinypic.com/s1j30h.png

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

Спасибо.

Answer 1

Пусть n будет числом покрывающих прямоугольников.Эту проблему можно решить за время O (n log n), используя плоскую развертку (http://en.wikipedia.org/wiki/Sweep_line_algorithm) и расширенное восходящее дерево отображения (http://en.wikipedia.org/wiki/Splay_tree).

1. Обрезать все покрывающие прямоугольники до ссылки.

2. Сортировкой уменьшите задачу до единицы, где все x-координаты покрывающих прямоугольников являются целыми числами в [0, 2n).Преобразуйте y-координаты аналогичным образом.

3. Создайте 2n-узел Splay Tree.Значение узла j - это количество прямоугольников, пересекающих линию развертки в открытом интервале (j, j + 1).Для O (log n) -временных обновлений не храните значение j в j, а скорее разницу между значением j и значением родительского j (корень хранит его истинное значение).Вращения немного сложнее: вращение

       y          x
      / \        / \
     x   c  ->  a   y
    / \            / \
   a   b          b   c
   

   включает обновление

   b.diff += x.diff;  // if b exists
   x.diff += y.diff;
   y.diff -= x.diff;
   

   Каждый узел также отслеживает минимум своего поддерева.Для совместимости с представлением значения, описанным ранее, узел j хранит разницу минимума своего поддерева и его значения.Во время ротации:

   y.diffmin = min(0, b.diffmin + b.diff, c.diffmin + c.diff);
   

   В конце операции объединения обновите корень таким же образом.Пропустите b или c, если они не существуют.

4. Прокрутить линию.Для x в [0, 2n) найдите все прямоугольники, левая часть которых находится в точке x, и обновите дерево следующим образом.Для прямоугольника от y0 до y1 отобразите y1 и увеличьте diff его левого дочернего элемента (и заново вычислите diffmin), затем добавьте y0 и уменьшите diff его левого дочернего элемента.

   После того, как все левые части былиобработано, проверьте дерево мин.Если он равен нулю, то ссылка на него не распространяется.

   Обрабатывать правые части практически одинаково (приращение и уменьшение в описании).