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