75160

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Доклад

Название: 

Оптимизированное размещение объектов нерегулярной формы на основе выбора наилучших вариантов ориентации ортогональных многогранников

ISBN/ISSN: 

2618-8317

Наименование конференции: 

  • 33-я Международная конференция по компьютерной графике и машинному зрению (GraphiCon 2023, Москва)

Наименование источника: 

  • Труды 33-й Международной конференции по компьютерной графике и машинному зрению (GraphiCon 2023, Москва)

Город: 

  • Москва

Издательство: 

  • Институт прикладной математики им. М.В. Келдыша РАН

Год издания: 

2023

Страницы: 

794-803
Аннотация
Статья посвящена вопросу повышения качества решений NP-трудных задач оптимизированной расстановки плоских и объёмных объектов нерегулярной формы. Для быстрого построения компоновки большого числа объектов сложной формы решается задача расстановки ортогональных многогранников, полученных посредством вокселизации исходных объектов произвольной геометрии с последующим объединением полученного набора вокселов. Предложена жадная эвристика размещения ортогональных многогранников, реализующая выбор наилучшего варианта ориентации текущего объекта, при котором формируемая компоновка будет наиболее плотной в сравнении с прочими доступными вариантами ориентации. Проведен анализ эффективности применения жадной эвристики размещения на задачах плоского фигурного раскроя и упаковки трехмерных объектов нерегулярной формы. Показано, что предложенная жадная эвристика обеспечивает очень быстрое получение решений высокого качества. Представлены результаты тестирования жадной эвристики размещения при её использовании в составе генетического алгоритма для оптимизации решений задачи компоновки.

Библиографическая ссылка: 

Чеканин В.А. Оптимизированное размещение объектов нерегулярной формы на основе выбора наилучших вариантов ориентации ортогональных многогранников / Труды 33-й Международной конференции по компьютерной графике и машинному зрению (GraphiCon 2023, Москва). М.: Институт прикладной математики им. М.В. Келдыша РАН, 2023. С. 794-803.