После того, как Эндрю в своем ответе указал мне верное направление и назвал проблему для меня, я решил представить результаты своих исследований здесь в отдельном ответе.
Это действительно проблема упаковки, а точнее говоря, проблема вложенности. Проблема математически NP-сложна, и поэтому используемые в настоящее время алгоритмы представляют собой эвристические подходы. Кажется, не существует каких-либо решений, которые могли бы решить проблему за линейное время, за исключением тривиальных наборов задач. Решение сложных проблем занимает от нескольких минут до нескольких часов на современном оборудовании, если вы хотите найти решение с хорошим использованием материала. Существуют десятки коммерческих программных решений, которые предлагают вложение фигур, но я не смог найти никаких решений с открытым исходным кодом, поэтому нет реальных примеров, когда можно было бы увидеть реализованные алгоритмы.
Отличное описание проблемы раскроя и раскроя с историческими решениями можно найти в статье, написанной Бенни Кьером Нильсеном из Копенгагенского университета ( Нильсен ).
Общий подход, по-видимому, заключается в том, чтобы смешивать и использовать несколько известных алгоритмов, чтобы найти лучшее решение для вложенности. Эти алгоритмы включают (управляемый / повторный) локальный поиск , Быстрый поиск по соседству , основанный на Нет- Подходит для многоугольника и эвристика Jostling . Я нашел отличную статью на эту тему с фотографиями того, как работают алгоритмы. Он также имел тесты различных программных реализаций. Эта статья была представлена на Международном симпозиуме по планированию 2006 г. С. Уметани и др. ( Уметани ).
Относительно новый и, возможно, лучший на сегодняшний день подход основан на Гибридный генетический алгоритм (HGA), гибрид, состоящий из имитированный отжиг и генетический алгоритм , который был описан У Цинмином и др. Из Уханьского университета ( Quanming ). Они реализовали это с помощью Visual Studio, базы данных SQL и набора инструментов оптимизации генетического алгоритма (GAOT) в MatLab.