«Квадратный» генератор фрактальных изображений на HTML5 Canvas + Knockout.js

в 12:18, , рубрики: canvas, Knockout.js, Веб-разработка, математика, фракталы, метки: , , ,

Начнём с дисклеймера. В данной статье я позиционирую себя скорее как математик, а не как веб-разработчик. С радостью приму любые замечания, касающиеся технической реализации этого чуда. С не меньшей радостью готов услышать другие варианты его названия («квадратный генератор фракталов» звучит как-то не очень). И, наконец, со значительно меньшей радостью я воспринял бы новость, что эту штуку уже придумали до меня, однако если это так — сообщите. Истина превыше всего.

Однако из-за чего весь этот сыр-бор? За подробностями прошу под хабракат.

«Квадратный» генератор фрактальных изображений на HTML5 Canvas + Knockout.js

Тривия

В самом строгом смысле, фрактал — это множество точек некоторого метрического пространства (в данном случае — евклидовой плоскости), обладающее самоподобием, т.е. имеющее подмножества, из которых с помощью преобразования подобия можно получить исходное множество. Зачастую фракталами называют также множества, которые «приблизительно» самоподобны, «стохастически» самоподобны и так далее. Здесь, однако, мы будем рассматривать исключительно труЪ-фракталы.

Фрактальное изображение — это, как ни странно, изображение фрактала. От изображаемого объекта оно отличается следующими особенностями:

  1. Конечное разрешение. В то время как фракталы зачастую имеют бесконечно мелкие детали, цифровое изображение ограничено размером пикселя.
  2. Цвет. В то время как множества на плоскости не имеют цвета, как и чёрные дыры — волос, изображения этих множеств ничто не мешает раскрасить в цвета любимой футбольной команды.

И, наконец, генератор фрактальных изображений — это программка, позволяющая создавать оные изображения пачками. Для этих целей создаются как большие навороченные приложения, такие, например, как 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

Источник

Поделиться

* - обязательные к заполнению поля