Я пытаюсь решить проблему вложения / укрытия, когда полигон должен быть покрыт материалом.
Материал поставляется в прямоугольниках с заданными размерами (например, прямоугольники размеров 3х4 и 2х6).
Цель состоит в том, чтобы использовать исходные прямоугольники или вырезанные из них кусочки, чтобы покрыть целевой многоугольник, а затем сварить их вместе. Это должно быть сделано с использованием как можно меньшего количества исходного материала (т.е. должна использоваться минимальная площадь исходных прямоугольников). Когда материал режется, происходит потеря некоторого материала (например, полоса шириной 1 см материала теряется). Также количество резки и сварки должно быть сведено к минимуму. Таким образом, цель оптимизации - это сочетание трех целей: минимизировать материал, длину резки и длину сварки.
Я пытался найти похожие проблемы - проблемы с вложенностью и прикрытием похожи, но не достаточно.
Кто-нибудь знает подобные проблемы, или есть какой-либо предложенный подход для решения?
Например: если мы хотим покрыть многоугольник на изображении 1 прямоугольниками размером 2x5, возможное решение изображено на изображении 2 , где каждый исходный прямоугольник окрашен в другой цвет. Обратите внимание, что коричневый прямоугольник был разрезан на две части, покрывающие левую верхнюю и левую средние части многоугольника.