Оптимальное отрицательное пространство между алгоритмами прямоугольников?

Учитывая прямоугольники r [] внутри большего прямоугольника R, существует оптимальный быстрый алгоритм для определения минимального числа прямоугольников, которые заполняют отрицательное пространство "" между r []?

Например, учитывая эти три синих прямоугольника внутри фиолетового прямоугольника:

three blue rectangles inside of a purple rectangle

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

green rectangles in between the blue rectangles

Ответы

Ответ 1

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

Когда прямоугольники находятся в общем положении, он вернет "прямоугольную форму" С# зелеными прямоугольниками = 3 * # синие прямоугольники + 1, и это оптимально. L-образная окрестность каждого синего угла должна быть разрезана в одном или другом направлении зеленым сегментом (общее положение: мы не можем использовать один и тот же сегмент для двух синих прямоугольников), поэтому для каждого синий прямоугольник, добавим 4 зеленых края 8 зеленых краев и 4 вершины (4 новых ребра плюс 4 разделенных), уменьшив количество подключенных компонентов на 1 в процессе. Результатом многогранной формулы является еще 3 грани (прямоугольники):

V - E + F = 1 + # связанных компонентов.


Пример:

 0123456789abc
0+-----------+
1|           |
2|  +--+     |
3|  |R | +-+ |
4|  +--+ |S| |
5|       | | |
6| +--+  | | |
7| |T |  +-+ |
8| +--+      |
9+-----------+

Мы запускаем линию развертки сверху вниз. События

# (y, whichside, xmin, xmax)
(2, top, 3, 6)  # R
(3, top, 8, a)  # S
(4, bot, 3, 6)  # R
(6, top, 2, 5)  # T
(7, bot, 8, a)  # S
(8, bot, 2, 5)  # T

Мы создали двоичное дерево поиска, упорядоченное по x, которое содержит частично построенные зеленые прямоугольники. Я напишу его как список.

# (xmin, xmax, ymin)
(0, c, 0)

Теперь мы начинаем обработку событий. Сначала это (2, вверху, 3, 6). Мы обнаруживаем, что он вложен в единственный зеленый прямоугольник до сих пор (xmin = 0, xmax = c, ymin = 0, ymax = 2). (Синий интервал всегда гнездится до тех пор, пока синие прямоугольники не пересекаются.) Мы начинаем два новых зеленых прямоугольника, по одному с каждой стороны синего прямоугольника, а дерево поиска содержит

(0, 3, 2) (6, c, 2)

Теперь мы обрабатываем (3, top, 8, a). Интервал (8, a) лежит внутри (6, c), поэтому мы заканчиваем еще один прямоугольник (xmin = 6, xmax = c, ymin = 2, ymax = 3) и начинаем еще два:

(0, 3, 2) (6, 8, 3) (a, c, 3)

Теперь мы обрабатываем (4, бот, 3, 6). Это заканчивает зеленые прямоугольники слева и справа, (xmin = 0, xmax = 3, ymin = 2, ymax = 4) и (xmin = 6, xmax = 8, ymin = 3, ymax = 4). Дерево поиска

(0, 8, 4) (a, c, 3)

Я думаю, что к этому моменту все должно быть ясно. Вот законченная прямоугольность:

 0123456789abc
0+-----------+
1|           |
2+--+--+-----|
3|  |R |-+-+-|
4+--+--+-|S| |
5|       | | |
6+-+--+--+ | |
7| |T +--+-+-+
8+-+--+------+
9+-----------+

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