Как "думает" алгоритм генерации расскладки.

Ранее в статье Автоматическая генерация раскладок я уже рассказывал о этой функции. Сегодня мы заглянем в скрытую часть работы этой функции.

Для этого нам не придется вникать в особенности алгоритма. Наученный опытом прошлой разработки этой функции, я предусмотрел возможность отладки еще на ранних этапах проектирования.

Отладочная информация представляет из себя последовательность кадров с позициями детали и контура. Обычные png файлы. Они то нам и помогут посмотреть прямо сейчас как выглядит генерация раскладки изнутри. 

Это коротюсенькое видео потребовало потратить изрядное количество времени на подготовку. Около трех часов заняло сохранение всех кадров. После этого последовала череда неудачных попыток конвертировать кадры в видео. Как оказалось проблема была в именах файлов. Пришлось их переименовать. А их там аж 29455 файла. Пришлось воспользоватся помощью KRename. Который как оказалось не принимает с диалога выбора файлов больше чем 2000 файлов (точное число не помню). Пришлось попотеть что бы программа узнала о всех файлах. Еще времени чтобы все это переименовалось.

В конечном счете я воспользовался вот этой командой для конвертирования 

avconv -framerate 200 -i img%d.png -s:v 1280x720 -c:v libx264 -profile:v high -crf 20 -pix_fmt yuv420p layout.mp4. Команда генерирует видео которое хорошо подходит для публикации на YouTube.

По количеству файлов не сложно догадаться что посекундный показ каждого затянет процесс на часы. Поэтому пришлось сжать все это дело до приемлемых рамок.

Ну и осталось описать что же мы должны увидеть на видео. Данная раскладка рассчитывается на листе формата А2 альбомной ориентации. Мы последовательно ищем положения деталей (зеленый цвет) относительно контура уже укладенных деталей (синий цвет). Для пустого листа это верхняя кромка. Соответственно смещая и поворачивая детали мы проверяем эти положения на пригодность и рассчитываем площадь описного прямоугольника для подходящих. В конце выбираем "наилучшее" положение для детали.

Таким вот не хитрым способом мы деталь за деталью укладываем их. Конечно это очень упрощенное описание и я опустил кучу деталей. Но должно быть достаточно для понимания сути происходящего.