Алгоритм для нахождения оптимального способа покрыть плоскость цветными прямоугольниками
Предположим, что я открываю Краску MS, тяну набор сплошных прямоугольников, сохраняю ее как png и даю ее Вам:
Теперь необходимо узнать, как я потянул эти прямоугольники. Для этого изображения Ваш алгоритм генерировал бы инструкции как,
- Потяните зеленый прямоугольник (заполняющий все пространство)
- Потяните розовый прямоугольник
- Потяните желтый прямоугольник
- Потяните синий прямоугольник
Или другими словами, учитывая изображение, я хочу генерировать его с помощью наименьшего количества прямоугольных команд в качестве возможного. Прямоугольная команда тянет сплошной прямоугольник, учитывая свое положение, длину, ширину и цвет. Как я могу приблизиться к этой проблеме?
Алгоритм должен быть достаточно устойчивым к образам процесса, не только оттянутым путем размещения прямоугольников, но также и сложных изображений как фотографии.
3 ответа
Вам нужно будет найти пересечение двух фигур, в любой точке, где они пересекаются, найдите, какая из них видна. В этом случае вы узнаете, какой из них находится на вершине.
Вы, наверное, хорошо об этом знаете, но я почти уверен, что даже с двумя цветами эта проблема является NP-полной. См. Раздел об ортогональных многоугольниках здесь . Проблемы, на которые они смотрят, похожи, но не совсем одинаковы.
Эвристически я подозреваю, что поиск больших монохроматических прямоугольников не приведет вас слишком далеко от оптимального. Как только вы это сделаете, попробуйте объединить смежные прямоугольники одного цвета, перемещая смежный прямоугольник разного цвета вперед в z-порядке.
Это многоступенчатый процесс.
Начните со следующих списков: R и S. R - это прямоугольники (прямоугольник, который он рисует, используется для построения окончательного изображения, по порядку). S - это сечение (каждая область пикселей одинакового цвета).
1) Обнаружение любых «идеальных» форм; любой прямоугольник, цвет которого НЕ ГДЕ, КРОМЕ этого прямоугольника. Должно быть не менее 1, так как последний прямоугольник не мог перекрываться. Добавьте его в КОНЕЦ R.
2) Продолжайте (1), пока не останутся безупречные формы.
3) Следующая часть непростая. Для каждого раздела: если этот раздел плюс некоторая совокупная часть всех прямоугольников в R образует идеальный прямоугольник, вставьте этот прямоугольник в начало списка перед всеми другими существующими прямоугольниками в R.
4) Повторите (3) ) пока их больше нет.
Тогда все готово.