Алгоритм поиска оптимального способа покрытия плоскости цветными прямоугольниками

Question

Предположим, что я открываю MS Paint, рисую кучу сплошных прямоугольников, сохраняю ее в виде png и даю вам:

Теперь вы должны выяснить, как я нарисовал эти прямоугольники. Для этого изображения ваш алгоритм будет генерировать такие инструкции, как

1. Нарисуйте зеленый прямоугольник (заполняя все пространство)
2. Нарисуйте розовый прямоугольник
3. Нарисуйте желтый прямоугольник
4. Нарисуйте синий прямоугольник

Или, другими словами, учитывая изображение, я хочу сгенерировать его, используя наименьшее количество прямоугольных команд , насколько это возможно. Команда rectangle рисует сплошной прямоугольник с учетом его положения, длины, ширины и цвета. Как я могу подойти к этой проблеме?

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

Answer 1

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

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

Answer 2

Это многошаговый процесс.

Начните с этих списков: R и S. R - прямоугольники (рисует прямоугольник, который он использует для построения окончательного изображения по порядку). S - сечение (каждая область пикселей одинакового цвета).

1) Обнаружение любых «совершенных» фигур; любой прямоугольник, цвет которого найден НЕТ ГДЕ, КРОМЕ этого прямоугольника. Должно быть не менее 1, поскольку последний прямоугольник не мог быть перекрыт. Добавьте его в КОНЕЦ Р.

2) Продолжайте (1), пока не останется идеальных фигур.

3) Следующая часть хитрая. Для каждого раздела: если этот раздел плюс некоторая совокупная часть всех прямоугольников в R образует идеальный прямоугольник, вставьте этот прямоугольник в начало списка перед всеми другими существующими прямоугольниками в R.

4) Повторяйте (3), пока их больше не будет.

Тогда все готово.

Answer 3

Вам потребуется найти пересечение двух фигур, в любой точке, где они пересекаются, найти, какая из них видима. Для этого пункта, который даст вам, кто находится на вершине.