То, что описывает 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-координате сразу).