:: алгоритмы и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Графика » Множество Мандельброта
  Множество Мандельброта

  1. Множества Жюлиа
Будем рассматривать последовательности комплексных чисел {Zn}. Возьмем произвольное комплексное число c. Теперь для любого комплексного числа k рассмотрим последовательность {Zn(k)}:
Z0 = k,
Zi+1= Zi2 + c
Зададим себе вопрос: сходится ли Zn к нулю или стремится к бесконечности при n стремящемся к бесконечности? Пусть J – множество всех комплексных чисел {k}, таких что {Zn(k)}стремится к 0, при n стремящемся к бесконечности. Если теперь мы возьмем все такие kи отобразим их на комплексной плоскости, то получим множество Жюлиа. Меняя c, мы получим бесконечный набор фантастических само подобных образов – множеств Жюлиа.

  2. Множество Мандельброта
Рассмотрим набор множеств Жюлиа и зададимся вопросом: связно ли данное конкретное множество Жюлиа? Пусть M – множество всех множеств Жюлиа, которые связны. Это множество и называется множеством Мандельброта.
Теперь возьмем любое множество Жюлиа J, и комплексное число c, которое его породило. Если J содержится в M, то изобразим точку черным на комплексной плоскости, в противном случае белым. Это и дает нам того “своеобразного снеговика“, которого вы уже наверное видели миллион раз. Его - то мы и будем генерировать.
К счастью, есть более легкий путь изображения множества Мандельброта, чем рисование каждого множества Жюлия и выяснения, связно ли оно. Наш метод будет очень близок к построению множеств Жюлиа. Опять рассмотрим итерационную последовательность для любого k, и выясним, сходится ли она к нулю.
Zi+1= Zi2 + c
Заметим, что c здесь уже не константа.Для любой точки комплексной плоскости мы c присваиваем значение k и выполняем итерации. Этот метод, как ни странно, дает нам то же изображение множества Мандельброта. Итак, алгоритм: 
For each point kon the complex plane do:
    let x=0.
    repeat infinite times:
        x=x^2+k.
    end repeat
    if x goes to infinity,
        k is not
in the set. Color is white.
    else
        k is in
the set. Color is black.

Понятно, что бесконечных циклов быть не должно. Поэтому возьмем некоторое большое число I и проитерируем I раз. Чем большее I мы взяли, тем, понятнее, точнее ответ мы получим. Из практики, число 4000 дает довольно хороший результат. Да, но 4000 раз “крутить“ цикл для каждого пиксела изображения, это многовато. К счастью, мы можем воспользоваться результатами многолетней работы математиков в этой области. Оказывается, если в любой конкретный момент вычислений, для k расстояние от zi(k) начала координат больше 2, то мы можем принять, что данная {Zn(k)} уйдет в бесконечность (При сравнении: расстояние < 2, поэтому его квадрат меньше 4 и корень извлекать не нужно). Итак, теперь наш алгоритм выглядит так: 

For each point k in the complex plane do:
    let x=0.
    repeat 4000 times
        let x=x^2+k
        if x^2 > 4 then Color it white
Break.
    end repeat
    if we reached 4000 then
        Color
it black.

Этот метод дает нам черно-белое изображение множества Мандельброта. Теперь надо подумать о том, как сделать его разноцветным.


  3. Цветное изображение
Если точка принадлежит множеству Мандельброта, то с ней все ясно – рисуем ее черным. Но как быть с точками, не принадлежащими множеству? Общепринятый способ выбора цвета для них – это выбирать цвет в соответствии с тем, как быстро {Zn(k)} стремится к бесконечности (на какой итерации мы ее исключаем из рассмотрения). Например, точка, для которой расстояние до начала координат больше 2 уже на третьей итерации, должна быть почти белой, а та точка, которая “продержалась“ до 3995 итерации – почти черной. Перепишем алгоритм для изображения в градациях серого: 
For each point k in the complex plane do:
    let x:=0.
    for i:=0 to 4000
        let x=x^2+k
        if ( |x|^2 > 4) then Color point k color i
Break;
        end if
    end for
    if (i=4000)
        Color
point k black.
    end if

Конечно, просто рисовать точку цветом i мы не можем. Считая, что у нас есть только 256 градаций серого, а i меняется до 4000. Нам надо как-то отображать i на доступный нам диапазон цветов. Эту проблему мы оставляем вам. После того, как мы получили приличное изображение в градациях серого, очень легко чуть изменить алгоритм для получения цветного изображения. Например, в изображении в градациях серого, если точка вышла из области на n-ой, вы можете рисовать ее цветом (n, n, n). Можете попробовать и что-нибудь поинтереснее типа (n, 255 – n, 50 mod n * 3). Оставляем простор для вашей фантазии. И последнее: обычно, все множество Мандельброта расположено от -2 до 0.5 по действительной оси и от –1.25 до 1.25 по мнимой оси. Ваша программа не должна тестировать точки далеко за пределами этой области.


  4. Вот один из возможных исходников подобной программы.


 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <dos.h>
#include <conio.h>

#define COLOR 100
#define MAS 0.9

typedef struct complex Complex;

void Sqr(Complex *z)
{
  Complex Fool=*z;

  z->x=Fool.x*Fool.x-Fool.y*Fool.y;
  z->y=2*Fool.x*Fool.y;
}

char GetColor(Complex zInit)
{
  Complex z=zInit;
  int Color=COLOR;

  while(z.x*z.x+z.y*z.y <= 4 && Color)
  {
    Sqr(&z);

    z.x+=zInit.x;
    z.y+=zInit.y;

    Color--;
  }

  return Color;
}

void DrawMandelSet(double xMin,double xMax,double yMin,double yMax)
{
  double xInc,yInc;
  Complex zInit;

  int y,x;

  char far *Screen=(char far *)MK_FP(0xa000,0);

  zInit.y=yMin;

  xInc=(xMax-xMin)/320;
  yInc=(yMax-yMin)/200;

  for(y=0;y<200;y++,zInit.y+=yInc)
  {
    zInit.x=xMin;

    for(x=0;x<320;x++,zInit.x+=xInc,Screen++)
    *Screen=GetColor(zInit);
  }
}

void main(void)
{
  _AX=0x13;geninterrupt(0x10);

  DrawMandelSet(-2*MAS,1*MAS,-1*MAS,1*MAS);

  getch();

  _AX=0x03;geninterrupt(0x10);}