С нашего последнего разговора прошло пять недель. Вы, дорогой читатель, наверняка подумали, что ваш покорный слуга всё это время бездельничал. Но это не так.Сразу после публикации прошлой статьи ко мне обратился подписчик по имени Сергей. Он занимается лазерной резкой металла и после прочтения материала решил, что я смогу проапгрейдить его алгоритмы расчёта. Очевидно, после прочтения моих статей вы уже поняли: как охотничий пёс при виде зайца не может остановиться, так и я при виде интересной задачи просто не могу пройти мимо. Получив задачу, я вник в суть и сделал то, что мы с вами так любим, — полноценный веб-сервис. Написан он в лучших традициях хакерского стиля: с динамическим обновлением и, конечно же, «заряженным» движком под капотом.
В правом верхнем углу задаем путь к папке с DXF-файлами. Количество нужных деталей указывается прямо в названии файла через нижнее подчеркивание (например,
part_20.dxf).Чуть ниже расположен блок управления листами.
Еще ниже находятся параметры алгоритма. Сейчас на панели выведено всего 4 конфигурации, хотя «под капотом» их более 50. Движок можно настроить очень гибко, но пока я не стал перегружать интерфейс лишними тумблерами.
В самом центре — окно визуализации раскроя:
Система посчитала, что выгоднее вообще не трогать основные листы, и целиком разместила заказ на остатках: для этого ей хватило четырёх обрезков размером 1000×1000 мм.
Наш стек: FastAPI + PostgreSQL + Celery + Redis.
Уверен, дорогой читатель, что к середине статьи ты находишься в лёгком недоумении: при чём здесь кликбейтный заголовок про ёлочки, если речь идёт о промышленной резке металла? Спешу успокоить — связь самая прямая.
Существует ежегодная рождественская олимпиада Santa 2025 - Christmas Tree Packing Challenge от Kaggle. Её участники как раз решали сложнейшую задачу двумерной укладки (2D Packing) тех самых 200 ёлочек в минимальный квадрат. Призовой фонд там уже раздали, но математика никуда не делась. Нюанс конкурса в том, что фигурки нужно размещать строго по очереди — от 1-й до 200-й
На скриншоте хорошо видны КИМ (коэффициенты использования материала). На первых 64 ёлочках средний показатель держится в районе 45%. Как алгоритм поведёт себя дальше — покажет время, сам ещё до конца не знаю. До призовых мест на Kaggle такое решение, конечно, вряд ли дотянет, но общий математический смысл задачи становится предельно понятен.
Ниже я покажу наглядный пример того, как именно происходит этот процесс:
Иногда алгоритму удаётся собрать очень красивые комбинации. Однако из-за жёсткого условия конкурса (упаковка строго в квадрат) такие удачные батчи — большая редкость. Например, на 35-й ёлочке КИМ достигает внушительных 53%, но удержать такую плотность на дистанции крайне сложно.
Для решения задачи на Kaggle мы немного изменили условия подачи листа, а в остальном использовали наш промышленный жадный алгоритм. Прогнав его по 200 «ёлочкам», получили КИМ около 40%. Это уровень примерно 3-го места — вообще-то неплохо, но мы решили «дожать» результат методом трехфазного термодинамического двигателя.
Геометрическая концепция (Front-Propagation)
Функция реализует алгоритм послойного наращивания монолитного кристалла (концепция «Живого Материка») изнутри наружу. Вместо стягивания деталей к абстрактному центру листа, алгоритм на старте находит самый массивный батч («материк») и поочередно вколачивает в его контур ближайшие блоки-рекруты.
Силовые векторы рассчитываются строго «кожа к коже» через кратчайшие расстояния shapely.ops.nearest_points. Это заставляет ветки «ёлочек» проваливаться прямо в каверны соседа, выжимая остатки воздуха на свободную периферию листа.
На этом моменте мы пока остановимся: файлы загружаются, а Kaggle уже ждет наш итоговый report.csv.
Оставим интригу — какое же место займет наш ТРЁХФАЗНЫЙ ТЕРМОДИНАМИЧЕСКИЙ ДВИГАТЕЛЬ РАСКРОЯ (ВЕРСИЯ 15.0 — ДВУХЭТАПНЫЙ КРИСТАЛЛИЗАТОР) на https://www.kaggle.com/competitions/santa-2025/submissions? Тем более что параллельно мы уже внедряем следующий алгоритм — разрезание «Материка» и принудительное выдавливание оставшихся пустот и воздуха.
Продолжение следует!
