Алгоритм упаковки 3d бин
Я ищу детерминированную реализацию для любого алгоритма упаковки 3d бинов, то есть для упаковки множества маленьких и разных кубоидов в один или много больших. Решение может отличаться от оптимального.
Он должен быть написан на C, C++, Java, C#, IronPython, IronRuby или любом другом языке, который можно использовать в.Net-коде.
Я нашел этот алгоритм C http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c, но он не вращает кубоиды, чтобы найти наилучшее соответствие. Я в порядке, не поворачивая их вверх ногами, но горизонтальное вращение должно быть возможным.
6 ответов
Я написал приблизительный алгоритм для случая, который вы описываете, то есть трехмерные прямоугольники с ортогональным вращением в C++. Вы можете найти результаты и алгоритм в опубликованной статье: http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf
Я преобразовал код wknechtel / 3d-bin-pack C в javascript. Можно легко перенести на C#.
https://github.com/keremdemirer/3dbinpackingjs
Вы можете запустить пример расчетов из index.html файл и просмотреть созданный отчет. pack1.js Файл содержит приложение и алгоритм. Я не уверен, как работает алгоритм, но результаты являются удовлетворительными для расчета пакетов.
Эта проблема NP-сложная. Ваша лучшая ставка - это алгоритм приближения (пока гениальный человек не решит какую-либо проблему NP, или очень удачливый человек не наткнется на решение.) К сожалению, я не знаю ни одного хорошо известного алгоритма приближения для этой проблемы.
Общая версия проблемы рассматривается в разделе "Алгоритмы для общих и упаковываемых роботом вариантов трехмерной задачи упаковки в бункеры: http://www.3dbinbox.com/Public/home/
Вы можете взглянуть на мое приближение для этого алгоритма.
Это интеллектуальный алгоритм первого подбора, основанный на максимальном охвате территории.
https://github.com/mohitesh07/3d-bin-packing
Написано на Java
Java-проект с открытым исходным кодом с поддержкой Largest Area Fit First: https://github.com/skjolber/3d-bin-container-packing
Вращается в 2D или 3D.