Я искал лучший алгоритм для создания автоматического вложения неправильного многоугольника в 2D. Мне нужно это, чтобы utitilze на программном обеспечении CAD / CAM. Вот как выглядит мой алгоритм:
Сначала, с данным листом и набором полигонов, я создал подмножество полигонов, у которых общий размер полигонов в 10 раз больше , чем заданная площадь листа. Я сделал это, чтобы он мог создавать более разнообразные решения
Во-вторых, подмножество полигонов сортируются по:
- Размер полигонов (площадь)
- Длина Ширина
- Длина по высоте
Верстка
Я использовал Нижнее левое размещение , чтобы аккуратно упаковать полигоны в левый нижний угол листа. Сумма Минковского, No-Fit-Polygon (NFP) , используется для определения оптимального размещения каждого полигона. Поскольку некоторые полигоны имеют скошенные ребра, были созданы NFP для скошенных ребер и NFP для нормальных ребер. Полигон будет размещен в зависимости от типа ребер. Вложение будет использовать потоки, чтобы сократить время выполнения.
Предложения
Существует большая вероятность того, что этот алгоритм вложенности может застрять в локальных минимумах. Чтобы предотвратить это, я думал об использовании Генетический алгоритм для сортировки по порядку полигонов. Моя проблема в том, что у меня возникают проблемы с поиском способа использования функции пригодности для проверки эффективности этой последовательности. Кроме того, время выполнения NFP не очень эффективно, если нужно проверить много полигонов. Я думал о приближении сетки, но будет много потерянного пространства, если сетка не такая точная.
Я изо всех сил для предложений или советов, чтобы создать оптимальный алгоритм автоматического вложения