Мой ближайший сосед Эйлер, или математик берётся за вышивку

На связи Ginger. Я знаю, что вы не забыли, но мне надо как-то начать. Итак, я {одной из своих бриллиантовых граней🤩} математик. Днём работаю в биоинженерии и drug discovery🤪. А по вечерам делаю платформу, создающую арт-вышивку из фото вашего питомца, которую можно носить, дарить или продавать как собственный мерч😎. И это второй эпизод сериала про неожиданные математические задачи, повстречавшихся мне среди катушек ниток.

Всё началось невинно: хотелось сервис, который берёт фото кота (или собаки, или хомяка — никакой дискриминации🐈🐖🐶🐹🦈), отдаёт его ИИ, а результат превращает в файл для вышивальной машины за минуту вместо 3-5 дней ручного труда. Фото ➖дизайн ➖мастерская ➖готовая вещь 🌟, пока вы гладите своего питомца🐆🐈

Звучит просто? Ага. Как почти всё в жизни… пока не столкнешься с физическим миром.

Генерации картинок опустим, nano banana и gpt-image по апи все умеют.

Превратить PNG в SVG тоже решенная задача.

Первая творческая задача: превратить SVG в набор стежков.

SVG это кривые Безье, а кривую можно семплировать в точки. Каждая точка — стежок. Отсюда и математика. SVG это граф, набор путей, каждый из которых — цепочка рёбер. Когда машина переходит с одного пути на другой, она делает JUMP — прыжок иглой с протяжкой нити. Прыжки это плохо: торчащие нитки на изнанке, потерянное время, потенциальные проблемы с машинами. А если прыжок длинный, приходится ещё и обрезать нить (TRIM).

И тут я поймала себя на мысли: это же задача о кёнигсбергских мостах.

Классика теории графов. Как и положено калининградцам, я гуляла только по 3м из них, а в VIII в Эйлер гулял по всем 7ми, и в 1736 году доказал, что обойти все мосты Кёнигсберга ровно по разу нельзя, потому что у графа мостов есть вершины нечётной степени.

В вышивке та же история. Если бы все пути складывались в эйлеров граф, машина прошла бы весь дизайн одним непрерывным движением. Но в реальности — десятки разрозненных контуров, каждый сам себе компонента связности. Прыжки и обрезки неизбежны.

Раз неизбежны — минимизируем. Порядок обхода я строю строила раньше ближайшим соседом: от точки, где игла только что закончила, ищу ближайшее начало или конец следующей цепочки (строчку можно шить в любую сторону — беру ту ориентацию, где ближе). Это тот самый момент, когда ближайший сосед впервые в жизни пригодился мне в проде. O(n²), 30 строк кода. Жаль, недолго. В июле на замену ему пришел китайский почтальон.

Почему заменила: локально все хорошо, глобально — силуэт шьется кусками, 20 обрезок там, где хватает 4.
Но настоящая мораль — я оптимизировала не ту задачу…Надо было не «посетить вершины» (задача коммивояжера), а «покрыть рёбра» (задача китайского почтальона).
Правильная постановка задачи > оптимизация неправильной.

Результат по Эйлеру: тонкий контурный рисунок, ~1-3к стежков, как карандашный набросок. Работает для тонких тканей, которые не выдержат 10-20тыс проколов иглой. Просто, элегантно, минималистично. Но для футболок и свитшотов выглядит слишком просто.

Поэтому, в следующей серии будет сатиновая атласная строчка, скелеты и немного дифференциальной геометрии.

Стек: Python, pyembroidery, svgelements, NumPy, SciPy, scikit-image. 
Дизайны и мокапы рисуют по очереди nano-banana и gpt-image. 
Фронтэнд: Next.js + Express + Telegram-бот. 

Часть 1 тут.

Поиграться:
petstitch.art
@PetStitch_bot

Бэкстейдж проекта:
@robin_bobbin_tensorflow