Алгоритм «исцеления» нескольких прямоугольников в меньшее количество прямоугольников?

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

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

Далее мы можем найти связанные области одного цвета, используя алгоритмы глубинного поиска или заливки. Мы можем рассматривать каждую связанную область (a polyomino ) в изоляции - ничего, что мы делаем в другом регионе должен влиять на это.

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

Одним простым способом является объединение горизонтальных прогонов соседних квадратов в длинные тощие прямоугольники. Затем мы можем сравнить с приведенной выше строкой и объединить, если наш запуск начнется & заканчивается совпадением - либо по завершении каждого пробега /строки, либо по мере того, как мы рассматриваем каждую ячейку для добавления к текущему прогону.

Пока еще не знаю, насколько близок этот метод к оптимальному. Кажется, он может столкнуться с небольшими проблемами, когда ряд, который он еще не рассмотрел, предлагает другой раскол, чем строки, которые он видел до сих пор:

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

Я также рассмотрел методы, по которым мы проходим по периметру полиомино, и пересекаем их в любое время, когда мы сталкиваемся с вогнутым углом, но этот подход выглядит более подверженным ошибкам. Получение оптимальных результатов, по-видимому, требует приоритизации разрезов, которые соединяются с двумя вогнутыми углами, а формы, содержащие углубления, требуют специальной обработки, поэтому метод сканирования строк имеет преимущество простоты.

Еще один метод, который я ищу, - это сделать первый запуск, найденный в верхней строке & продлите его, насколько сможете. Затем сделайте первый прогон в верхнем ряду того, что осталось ... Это получается на инвертированных T-образцах, поэтому оно также не оптимально.

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