Начнём с дисклеймера. В данной статье я позиционирую себя скорее как математик, а не как веб-разработчик. С радостью приму любые замечания, касающиеся технической реализации этого чуда. С не меньшей радостью готов услышать другие варианты его названия («квадратный генератор фракталов» звучит как-то не очень). И, наконец, со значительно меньшей радостью я воспринял бы новость, что эту штуку уже придумали до меня, однако если это так — сообщите. Истина превыше всего.
Однако из-за чего весь этот сыр-бор? За подробностями прошу под хабракат.
Тривия
В самом строгом смысле, фрактал — это множество точек некоторого метрического пространства (в данном случае — евклидовой плоскости), обладающее самоподобием, т.е. имеющее подмножества, из которых с помощью преобразования подобия можно получить исходное множество. Зачастую фракталами называют также множества, которые «приблизительно» самоподобны, «стохастически» самоподобны и так далее. Здесь, однако, мы будем рассматривать исключительно труЪ-фракталы.
Фрактальное изображение — это, как ни странно, изображение фрактала. От изображаемого объекта оно отличается следующими особенностями:
- Конечное разрешение. В то время как фракталы зачастую имеют бесконечно мелкие детали, цифровое изображение ограничено размером пикселя.
- Цвет. В то время как множества на плоскости не имеют цвета, как и чёрные дыры — волос, изображения этих множеств ничто не мешает раскрасить в цвета любимой футбольной команды.
И, наконец, генератор фрактальных изображений — это программка, позволяющая создавать оные изображения пачками. Для этих целей создаются как большие навороченные приложения, такие, например, как Apophysis, так и маленькие кустарные поделки, вроде моей скромной веб-рисовательницы, о которой речь пойдёт ниже.
Математическая модель
Вначале дадим несколько определений. Множеством состояний назовём целочисленный отрезок [m; n], где m — неположительно, а n — положительно. Соответственно, наименьшее множество состояний — это {0; 1}. Элементы этого множества мы назовём, соответственно, состояниями.
Неположительные числа мы назовём стабильными состояниями, положительные — нестабильными состояниями. Соответственно, множество состояний будет содержать хотя бы одно стабильное состояние и хотя бы одно нестабильное.
Правилом назовём матрицу 2х2, состоящую из целых чисел, принадлежащих множеству состояний. Каждому состоянию поставим в соответствие некоторое правило. При этом всякому стабильному состоянию s будет соответствовать правило [[s; s]; [s; s]] (именно поэтому оно зовётся стабильным), нестабильным же состояниям могут быть поставлены в соответствие произвольные правила.
Задав множество состояний и соответствующие его элементам правила, мы можем приступить к построению фрактала. Сначала мы возьмём квадрат и присвоим ему состояние 1. Затем разделим его на четыре квадратика поменьше, присвоив им состояния согласно правилу, соответствующему состоянию 1. Над маленькими квадратиками мы надругаемся аналогичным образом, и так далее.
В идеальном математическом случае мы будем продолжать этот процесс до бесконечности. В итоге фракталом мы назовём множество точек, которые на каждой итерации попадали в квадраты с нестабильными состояниями.В этом случае, кстати, нам достаточно единственного стабильного состояния, поскольку по сути они не отличаются ничем кроме номера.
Мы, однако, собираемся строить неидеальное и нематематическое изображение. Поэтому мы остановим процесс, как только маленькие квадратики станут размером с пиксель, а затем раскрасим их разными цветами, в зависимости от состояния. Вуаля, фрактальное изображение готово.
Реализация
Что ж, пожалуй, настало время дать ссылку на моё творение. Вот она. бесплатный, поэтому я надеюсь, что до этого места дочитали немногие :)
На текущий момент реализованы следующие фичи:
- задание правил и состояний (без этого было бы как-то грустно);
- задание цвета в формате RGB для каждого стабильного состояния и для всех нестабильных скопом (как показала практика, различные цвета для нестабильных состояний — некрасивое излишество);
- анимация построения фрактального изображения;
- валидация: если вместо номера состояния вы введёте слово «писька», границы соответствующей ячейки приобретут тревожный красный цвет, и вы не сможете начать построение фрактала;
- возможность экспорта/импорта настроек: вместо того, чтобы пересылать другу изображение, достаточно отправить ему правила и состояния, скукоженные в строчку текста;
- кнопка «Помощь», при нажатии на которую открывается эта статья.
Изображение рисуется на канвасе с помощью волшебной функции putImageData. Когда речь идёт об объектах размером с пиксель, использование графических примитивов, мягко говоря, неоправданно. Интерфейс реализован с активным применением всем известной библиотеки Knockout.js, о которой я в процессе узнал немало нового и интересного.
Что стоит попробовать
Воспользовавшись вышеупомянутой функцией импорта, попробуйте построить некоторые фрактальные изображения. Возможно, вам понравится.
Перекошенный треугольник Серпинского (задан по умолчанию):
[1,1,1,0];[0,0,0];[255,255,255]
Поеденный молью ковёр Серпинского:
[2,3,4,5][1,1,1,0][1,1,0,1][1,0,1,1][0,1,1,1];[200,200,0];[0,200,0]
Покосившаяся лестница Кантора (для пущего эстетизма смотреть, наклонив голову влево на 45°):
[0,3,2,-1][0,-1,1,-1][0,1,0,-1];[0,0,255][255,0,0];[0,0,255]
Какая-то штука:
[1,-1,0,2][1,0,-1,2];[0,0,255][255,0,0];[255,0,255]
Что хотелось бы добавить
Если тщательно вдуматься, становится понятно, что данные изображения суть визуализация работы недетерминированного конечного автомата. Впрочем, не-математикам в это лучше не вдумываться.
Аккуратная реализация ковра Серпинского и лестницы Кантора требовала, чтобы квадрат на каждой итерации делился не на 4, а на 9 маленьких квадратиков. Я не стал добавлять такую возможность — мало веселья, много геморроя.
Можно строго доказать, что множество точек, которые на каждой итерации принадлежат квадрату в нестабильном состоянии, всегда будет фракталом.
В принципе, для любого изображения подходящего размера можно подобрать настройки, позволяющие сгенерировать его с помощью этой веб-рисовалки. Однако количество правил и состояний будет огромным, а процесс визуализации — неинтересным.
Доклад окончен, спасибо за внимание.
Автор: Sirion
