Скажем, у меня есть сетка прямоугольников разных форм и цветов, и я хочу уменьшить (достаточно близко к оптимальному, хорошо, оптимально не нужно) количество прямоугольников, чтобы представить одну и ту же схему цветов.
Изображение выше - очень упрощенный случай, и пробелы между прямоугольниками предназначены только для визуализации - они на самом деле будут плотно упакованы.
Что такое подход или название алгоритма (рад Google), который может помочь мне сделать это?
Ответы:
Во-первых, мы можем преобразовать исходные прямоугольники в ячейки вашей базовой сетки, чтобы сделать ввод более равномерным. (Эффективно растеризация проблемы)
Это позволит нам найти оптимизации, которые могут быть неочевидны при работе непосредственно с исходными прямоугольниками, особенно когда это требует разделения нескольких исходных прямоугольников для их рекомбинации по-разному.
Затем мы можем найти связанные области одного цвета, используя алгоритмы поиска в глубину или заливки. Мы можем рассматривать каждый связанный регион ( полиомино ) изолированно - ничто из того, что мы делаем с другим регионом, не должно влиять на этот регион.
По сути, мы хотим найти способ разбить это полиомино на прямоугольники (к сожалению, большая часть литературы, которую я могу найти, посвящена противоположной проблеме: разбиение прямоугольников на полиомино! Это затрудняет поиск потенциальных клиентов ...)
Одним простым методом является объединение горизонтальных участков соседних квадратов в длинные тощие прямоугольники. Затем мы можем сравнить с приведенной выше строкой и объединить, совпадают ли совпадения начала и конца цикла - либо по окончании каждого цикла / строки, либо с учетом того, что каждая ячейка добавляется к текущему циклу.
Я пока не знаю, насколько близок этот метод к оптимальному. Кажется, может возникнуть небольшая проблема, когда строка, которую он еще не рассматривал, предлагает другое разделение, чем строки, которые он видел до сих пор:
Обнаружение, когда трасса / прямоугольник точно покрывается трассами выше и ниже, затем разделение и объединение их решит этот конкретный случай, но я не исследовал, насколько общая проблема.
Я также посмотрел на методы, где мы проходим по периметру polyomino и прорезаем каждый раз, когда сталкиваемся с вогнутым углом, но этот подход кажется мне более подверженным ошибкам. По-видимому, для получения оптимальных результатов требуется расставить приоритеты надрезов, которые соединяют два вогнутых угла, а формы, содержащие пустоты, требуют особой обработки, поэтому метод сканирования строк, по-видимому, имеет преимущество в простоте.
Еще один метод, который я рассматриваю, заключается в том, чтобы взять первый прогон, найденный в верхнем ряду, и расширить его как можно дальше. Затем сделайте первый прогон в верхнем ряду того, что осталось ... Это срабатывает на перевернутых Т-формах, так что это тоже не оптимально.
Я чувствую, что, возможно, есть способ использовать динамическое программирование для нахождения оптимального разделения, но я еще не нашел его.
источник