Фракталы

Пример фрактального изображения

Здесь рассказывается о построении фрактальных картинок с помощью JavaScript с выводом в окно Web-браузера. Приводится код программы и сведения о его работе в различных браузерах. Построение фракталов средствами Web-браузеров, разумеется, далеко не лучшая идея в технологическом отношении, но она интересна с точки зрения тестирования браузеров.

Фракталы — очень интересная тема. Однако здесь я не буду останавливаться на подробном разъяснении понятия фрактала и его применениях. В Интернете вы легко можете найти соответствующие сведения. Отмечу лишь, что чаще всего это понятие иллюстрируют различными графическими изображениями (см.рис.), построенными с помощью программ. Такие изображения сочетают в себе одновременно некоторую регулярность (как узоры на ковре) и хаотичность (как облака). Недаром их называют ”упорядоченным хаосом”. Поражает то, что посредством  несложных программ создаются довольно сложные изображения облаков, растений, ландшафтов и т.п. Таким способом построенные изображения называют фрактальными.
Идея фракталов и область их практического применения значительно глубже и шире, чем рисование фантастических или, наоборот, реалистических картинок. Но здесь не об этом.

Алгоритм построения

В общем виде алгоритм построения фрактального изображения заключается в следующем:

1. Выбираем прямоугольную область на числовой плоскости.

2. Для каждой точки z выбранной области вычисляем ее образ, т.е. новую точку z'=F(z), где F() — некоторая функция.

К полученной точке применяем ту же функцию F(), получая следующую точку.

Данную процедуру повторяем несколько раз, задав некоторое правило ограничения количества таких итераций.

3. В зависимости от количества итераций, выполненных на предыдущем этапе, назначается цвет исходной точки.

4. Каждая окрашенная точка отображается на экране.

 

Как известно, точка на плоскости задается парой координат (x,y), где x и y — вещественные числа. В то же время точку можно задать комплексным числом вида x+yi, где i 2 = -1. В качестве примера функции F(z) преобразования точки  z=x+yi можно взять такую:

F(z) = az2  + b,

где z = x+yi — некоторое комплексное число (x, y — координаты точки на числовой плоскости);

a, b — некоторые комплексные числа.

Указанная функция задает так называемое конформное преобразование, при котором фигуры на плоскости преобразуются в себе подобные с изменением масштаба и поворотом.

Пусть zi — точка, полученная на i-ой итерации, тогда на следующей итерации мы получаем точку zi+1 = azi2 + b. Таких итераций можно выполнить сколько угодно, но обычно их количество каким-то образом ограничивают. Например, итеративный процесс прекращают, если полученная точка вышла за пределы круга заданного радиуса с центром в начальной точке или количество выполненных итераций превысило некоторое заданное число. В зависимости от количества выполненных итераций определяется, каким цветом следует окрасить начальную точку.

Программа на JavaScript

Очевидно, программу для реализации описанного выше алгоритма написать нетрудно. Я решил это сделать на JavaScript, чтобы выводить картинки в окно web-браузера. Хотя программа и не очень сложна, она требует довольно больших затрат времени и памяти на выполнение. Поэтому тем, кто интересуется собственно построением фрактальных изображений, лучше использовать другие средства программирования. Впрочем, существует довольно много готовых программ для этой цели.
Я сделал два варианта программы:

  1. Картинка формируется на основе тегов <div>;
  2. Картинка рисуется с применением объекта canvas.

Применение тегов <div>

Программа выполняет необходимые вычисления и формирует строку, содержащую множество  HTML-тегов <div>. Каждый из этих тегов представляет точку генерируемой фрактальной картинки. Стилевые параметры задают размеры (у меня — 1x1px) и цвет точки. Затем данная строка тегов записывается в документ методом document.write().
Ниже приводится CSS- и JavaScript-код программы, рисующей фрактальную картинку.

Опробовать работу программы рисования фрактальной картинки на основе <div> (это может занять от нескольких секунд до 1 мин.)

CSS:

<style>
/* Общие параметры для отображаемой точки */
div.fract {position:absolute;width:1px;height:1px}
</style>

JavaScript-код:

function fractal(x0,y0,xk,yk,dx,kmax,lmax,a,b,mode){ // конструктор

/* Описание:
   Данный объект генерирует строку тегов для вывода на экран браузера
   фрактальной картинки,вычисленной по простой формуле.
   В прямоугольнике с координатами углов (x0,y0) и (xk,yk)
   тестируются все точки через интервал dx путем итерационного преобразования:
     z(i+1)=F(z(i)),
     где z - комплексное число вида x+yi;
         F() -функция преобразования комплексного числа в другое комплексное число.
   Если на какой-то итерации точка выйдет за круг радиуса lmax с центром
   в начальной точке или же количество итераций превысит kmax, исходная точка
   окрашивается в цвет, зависящий от номера итерации.
   Собственно формула преобразования задается кодом функции next(), а исследование судьбы точки
   при итерационном преобразовании — кодом функции explore().
   
   Параметры (свойства):
   x0,y0 - начальное число (вещественная и мнимая части комплексного числа)
   xk,yk - конечное число (вещественная и мнимая части комплексного числа)
   dx - приращение числа в итерации при вычислении функции F()
   kmax - максимальное количество итераций (ограничение)
   lmax - радиус круга с центром в начальной точке (при выхде из него итерации прекращаются)
   mode - задает формулу преобразования координат точек, т.е. функцию z(i+1)=F(z(i)):
   если не указан, то z(i+1)=a*z(i)*z(i)+b (a,b — некоторые комплексные числа);
   в противном случае z(i+1) определяется несколько иначе (см. функцию next()).
   В исходном варианте функция преобразования имеет вид z(i+1)=a*z(i)*z(i)+b.
   
   Метод get() возвращает строку тегов,описывающих фрактальную картинку;
   Свойство resume содержит строку отчета о работе; 
   
*/
/* Параметры: */
/* Примеры значений, которые вы можете изменить: */
this.x0=x0||-1.5;
this.y0=y0||-1.5;      
this.xk=xk||1.5;
this.yk=yk||1.5;
this.dx=dx||0.01;   // приращение чисел
this.kmax=kmax||100;// ограничение итераций
this.lmax=lmax||30; // радиус области
this.a=a;  // множитель a в формуле zi+1=a*F(zi)+b
this.b=b;  // слагаемое b в формуле zi+1=a*F(zi)+b
this.mode=mode||null;  // вид преобразования
this.resume="";
if (!a) this.a=new Array(1,0);
if (!b) this.b=new Array(0,0);

/* Метод, возвращающующий строку тегов для вывода: */
this.get=function() {  
  var time=new Date(); // хронометраж для отчета
  var t0=time.getTime();
var x,y,n;
var x0s=0;
var y0s=0;
var i=0;
var str="";
for (y=this.y0;y<this.yk;y=y+this.dx){
  x0s=0;
  for (x=this.x0;x<this.xk;x=x+this.dx){
    n=explore(x,y,this.kmax,this.lmax,this.a,this.b,this.mode);// судьба точки; возвращает номер итерации
    /*** Цвет точки: *******/
    if (n>this.kmax) n=this.kmax;
    var color="000000"+toh(16715266-n*(16581891/this.kmax));
    color="#"+color.substr(color.length-6);
    /* Код для отображения точки: */
    str+='<div class="fract" style="background:'+color+
      '; top:'+y0s+'px;left:'+x0s+'px"'+
      'title="'+x.toFixed(3)+','+y.toFixed(3)+'"></div>';
    x0s++;
    i++;
  }
  y0s++;
}

  var time=new Date(); // хронометраж для отчета
      t0=time.getTime()-t0;
/* Отчет: */
this.resume="Отчет\nТочек: "+i+"\nВремя: "+t0+"мс"+"\nБайт: "+str.length;

return str;
}

/*** Функции  ***********************************************/

function explore(x,y,kmax,lmax,a,b,mode){ /* исследует судьбу
                           точки; возвращает номер итерации */
var z,k,q,w;
z=new Array(x,y)
k=0;
while (true){
  z=next(z[0],z[1],a,b,mode);
  if (x==z[0]&&y==z[1]) return kmax; 
  k++;
  q=(x-z[0]);q=q*q;w=(y-z[1]);w=w*w;
  if ((q+w)>lmax*lmax)
    return k; // если вышли за пределы области 
  if (k>kmax) return kmax;// если количество итераций слишком велико 
}
}
/***************************************************/

function next(x,y,a,b, mode){  // возвращает координаты следующей точки
/* Возможны различные формулы вычисления */
// Sqrt 
if (mode){
  var x1=Math.sqrt(Math.abs(x*x-y*y));
  var y1=Math.sqrt(2*x*y);
  
}
if (!mode){ // Квадрат (по умолчанию)
  var x1=x*x-y*y;
  var y1=(2*x*y);
}
x=x1*a[0]-y1*a[1]+b[0];
y=y1*a[0]+x1*a[1]+b[1];
return new Array(x,y);
}
/***************************************************/
function toh(n){ // возвращает 16-е число, соответствующее 10-му числу n
n=Math.round(n);
var  hchars="0123456789abcdef"     /* строка, содержащая все
                                   шестнадцатеричные цифры */
  if (n<16) return hchars.charAt(n);
  var i=n%16;
  return toh((n-i)/16)+hchars.charAt(i) 
}
}
/*****************************************************************/

Пример вызова:

myfr=new fractal(); // создаем экз. объекта fractal
/* Устанавливаем значения свойств: */
myfr.x0=-1;
myfr.xk=1;
myfr.lmax=100;
myfr.kmax=30;
myfr.a=new Array(1,0.5);
myfr.b=new Array(0.5,0.5);
/* Получаем строку HTML-кода и записываем в документ: */
document.write(myfr.get());
alert(myfr.resume) // выводим отчет

 

Тестирование браузеров

Если, например, картинка содержит 300x300=90 000 точек, то строка тегов, записываемая в документ методом write(), имеет объем порядка 9Мб. Очевидно, отображение в окне браузера такого большого объема данных потребует заметных затрат времени и памяти: от нескольких секунд до нескольких минут.

Временные затраты зависят от производительности процессора, доступной оперативной памяти, а также от браузера. Для меня оказалось неожиданным, что зависимость временных затрат от браузера весьма существенна.

Я проверил пять браузеров на создание картинки из 90 000 точек: Internet Explorer 7 и 8, Firefox 3.06, Opera 9.63, Safari 3.2, Chrome 1.0. Испытания производились на двух компьютерах: 2.4ГГц, 512Мб и 1.6ГГц, 1Гб. Лучшие результаты показал второй компьютер (с большей оперативной памятью, но менее быстродействующим процессором). Chrome и Safari потребовалось не более 10с, а Firefox — 30c. Internet Explorer задумался слишком надолго. Собственно вычисления производятся всеми браузерами примерно одинаково быстро. Задержки возникают при выводе потока данных методом document.write(). Таким образом, дело не в объеме собственно вычислений, а в отображении потока данных, осуществляемого методом write(), который поддерживается различными браузерами, как это выясняется, по-разному. Вот тут-то и обнаруживается, что Internet Explorer делает это совсем плохо при достаточно больших объемах (мегабайты) выводимых данных. Firefox и Opera справляются с этой задачей, но заметно хуже, чем Safari и Chrome.

Места между браузерами по оперативности решения тестовой задачи распределились следующим образом:
1. Chrome и Safari;
2. Firefox (отстает от Chrome и Safari примерно в 2 раза);
3. Opera;
4. Internet Explorer вообще не справился с данной задачей.

Опробовать работу программы рисования фрактальной картинки на основе <div>

Перейти к описанию программы рисования фрактальной картинки на основе canvas

Hosted by uCoz