Сначала создайте набор всех «атомарных» прямоугольников в композиции, то есть областей, образованных пересечениями прямоугольников и не подразделяющихся между собой. Каждый фактический прямоугольник охватывает 1 или более атомных прямоугольников. Затем запустите комбинаторный алгоритм оптимизации, например, SETCOVER, чтобы рассчитать минимальное количество прямоугольников, необходимое для их покрытия.
Вот иллюстрация подхода. У вас есть три прямоугольника (A, B, C). Они создают 5 атомных областей (1-5):
+---------+A
| 1 |
| +----+-----+B
| | 2 | 3 |
| | +-+---+C|
| | |4| | |
+----+--+-+ 5 | |
| +-----+ |
+--+-------+
Прямоугольники охватывают атомные области в соответствии с этой таблицей:
A {1,2,4}
B {2,3,4,5}
C {4,5}
Задача SETCOVER теперь состоит в том, чтобы выбрать минимальное подмножество прямоугольников {A, B, C} так, чтобы все атомные области были покрыты, когда вы соединяете атомные области, покрытые прямоугольниками. Минимальное решение (очевидно)
A {1,2,4} + B {2,3,4,5} = {1,2,3,4,5}
Обратите внимание, что здесь области не прямоугольные, например, участок 3 имеет сложную форму. Вы можете избавиться от этой проблемы следующим способом: возьмите все различные X-координаты угловых точек исходных прямоугольников и рассмотрите их как X-координаты сетки и сделайте то же самое для Y-координат; тогда каждый прямоугольник покрывает набор квадратов сетки, которые никогда не подразделяются, т. е .:
+---------+A -
| 1 |
| +----+-----+B -
| | 2 | 3 |
| | +-+---+C| -
| | |4| | |
+----+--+-+ 5 | | -
| +-----+ | -
+--+-------+ -
| | | | | |
Что дает следующую сетку 5x5:
AAA A = rectangle A only
A**BB B = rectangle B only
A*#CB * = A and B
BCCB C = rectangles C and B
BBBB # = All
Из этого вы можете легко извлечь 5 регионов; на самом деле они уже отмечены :) (A, B, C, *, #)