Материал конференции: "Труды Международной конференции по компьютерной графике и зрению "Графикон" (19-21 сентября 2023 г., Москва)"
Авторы:Чеканин В.А.
Оптимизированное размещение объектов нерегулярной формы на основе выбора наилучших вариантов ориентации ортогональных многогранников
Аннотация:
Статья посвящена вопросу повышения качества решений NP-трудных задач оптимизированной расстановки плоских и объёмных объектов нерегулярной формы. Для быстрого построения компоновки большого числа объектов сложной формы решается задача расстановки ортогональных многогранников, полученных посредством вокселизации исходных объектов произвольной геометрии с последующим объединением полученного набора вокселов. Предложена жадная эвристика размещения ортогональных многогранников, реализующая выбор наилучшего варианта ориентации текущего объекта, при котором формируемая компоновка будет наиболее плотной в сравнении с прочими доступными вариантами ориентации. Проведен анализ эффективности применения жадной эвристики размещения на задачах плоского фигурного раскроя и упаковки трехмерных объектов нерегулярной формы. Показано, что предложенная жадная эвристика обеспечивает очень быстрое получение решений высокого качества. Представлены результаты тестирования жадной эвристики размещения при её использовании в составе генетического алгоритма для оптимизации решений задачи компоновки.
Ключевые слова:
Задача упаковки, вокселизация, ортогональный многогранник, жадная эвристика, генетический алгоритм
