Ёжик во фрактальном тумане

nn.png

Каждый, кто хоть чуток сталкивался с фракталами, видел красивые картинки множеств Жюлиа, которые определяются квадратным многочленом; но интересно решать обратную задачу: пусть есть некоторая картинка, а мы ходим по ней придумать такой многочлен, который даст некоторое приближение исходной картинки. Картинка с ёжиком выше демонстрирует эту идею.


Итак, рассмотрим кота K.



Нам нужно придумать такой многочлен f, чтобы внутри кота последовательность f(z), f(f(z)), f(f(f(z))),… была ограниченной, а вне кота — стремилась к бесконечности. Долго над этим вопросом я не думал, а сразу же поискал в интернете и нашёл замечательную статью Kathryn A. Lindsey, «Shapes of polynomial Julia sets», 2013, arXiv:1209.0143. В этой статье доказывается что для «хорошего» кота и для заданной точности δ такой многочлен придумать можно, причём доказательство конструктивно.

Рассмотрим эту конструкцию. Пусть φ' — конформное отображение, которое внешность единичной окружности переводит во внешность кота. Пусть φ(z) = φ'((1 + ε)z) — подправленное на некоторое малое ε исходное отображение.



Далее, пусть ω(z) = cn(zr0)(zr1) ⋅… ⋅ (zrn−1), где c — коэффициент при z в разложении отображения φ в ряд Лорана, а rk = φ(eik/n) — образы корней из единицы n-ой степени. Доказывается, что многочлен f(z) = z(ω(z) + 1) будет искомым при достаточно большом n.

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

Кусочек на древнем наречии

 

Обмазываем zipper клеем на питоне


Чтобы использовать этот пакет, нужно по изображению построить ломаную. Я не стал делать какого-то автоматического решения, а загрузил изображение в редактор Inkscape и обвёл его, а распарсить SVG-формат проще простого. Это удобно тем, что позволяет экспериментировать с ломаной.

 

Парсим пути в SVG-файле




Далее, нам нужно отображение из внешности во внешность, а пакет находит отображение из внутренности во внутренность. Здесь нужно просто сопрячь генерируемое отображение инверсией. То есть φ'(z) = 1 / ψ(1/z), где ψ — отображение, которое генерирует пакет. А на вход пакета надо подавать уже инвертированную ломанную.

 

 

 

 

Сопрягаем




В определении многочлена f ещё участвует коэффициент c. Для приближённого вычисления его значения воспользуемся следующим приёмом. Пусть

f(z) = cz + a + a1/z + a2/z2 + a3/z3 +…

Рассмотрим некоторую конечную, но достаточно большую, часть этого ряда. Подставим в ряд значения корней из единицы n-ой степени, где n больше числа членов этого куска.

f(eik/n) = ceik/n + a + a1e−2πik/n + a2e−4πik/n + a3e−6πik/n + ..., k = 0, ..., n − 1.

Теперь умножим каждую строку на e−2πik/n и сложим все строки. Так как сумма всех корней из единицы равна 0, то справа останется только nc. Поэтому можно положить

c = (f(1) ⋅ 1 + f(ei/n)e−2πi/n +… + f(ei(n − 1)/n)e−2πi(n − 1)/n)) / n.

Соберём всё вместе и проверим, что получилось. На рисунке ниже приведён «тепловой» график логарифма модуля f(z) (чем краснее, тем больше значение). Как видно, внутри кота значения многочлена маленькие, а вне кота многочлен возрастает, так и должно быть. Заметьте также, как распределяются значения f(eik/n) (зелёные точки), из-за этого эффекта пришлось рисовать кота, у которого ноги достаточно далеко находятся друг от друга.



Теперь просто-напросто применяем какой-нибудь алгоритм для рисования множества Жюлиа и получаем кота, граница которого фрактальна.

 

 

 

 

Например, алгоритм времени убегания

 

 




Если же у нас изображение состоит из нескольких областей A1, A2, ..., Aq, то в вышеупомянутой статье предлагается использовать вместо многочлена рациональное отображение f(z), определённое следующим образом. Для каждой области Ar, запишем произведение ωr(z) как сделано выше. Тогда искомая рациональная функция f(z) определяется формулой f(z) = z / (1/ ω1(z) +… + 1 / ωq(z)).

Например, пусть у нас есть ёжик в тумане Ё.



Обведём ёжика и холм (нижняя граница холма находится за пределами картинки).



Ёжик в вакууме.



Холм без ёжика.



Всё вместе.



Увеличенное брюхо ёжика с блохами-ежами.



Как всегда, исходный код можно найти на гитхабе.

Ещё раз повторю ссылку на статью, с помощью которой всё получилось: Kathryn A. Lindsey, «Shapes of polynomial Julia sets», 2013, arXiv:1209.0143. Отмечу, статья легко читается, так что можете поразбирать доказательства за чашкой чая.

habrahabr.ru/post/230009/