Викиучебник

Множество Мандельброта

Мно́жество Мандельбро́та — это множество таких точек c на комплексной плоскости, для которых рекуррентное соотношение при задаёт ограниченную последовательность. То есть, это множество таких c, для которых существует такое действительное R, что неравенство |zn|<R выполняется при всех натуральных n.

Множество Мандельброта


Построение множества править

Несложно доказать, что как только модуль zn окажется больше 2 (или, в терминах действительной и мнимой частей, xn2+yn2>4), последовательность станет стремиться к бесконечности. В случае |c|≤2 это можно доказать с помощью метода математической индукции. При |c|>2 точка c заведомо не принадлежит множеству Мандельброта, что также можно вывести методом индукции, используя равенство z0=0. (Хотя в этом случае может существовать другое z0, для которого соответствующая последовательность ограничена по модулю, но для некоторого n выполняется неравенство |zn|>2.)

Сравнение |zn| с этим числом (в англоязычной литературе его называют «bail-out») позволяет выделять точки, не попадающие внутрь множества. Для точек, лежащих внутри множества, последовательность не будет иметь тенденции к бесконечности и никогда не достигнет этого числа, поэтому после определённого числа итераций расчёт необходимо принудительно завершить. Максимальное число итераций, после которых число считается попавшим внутрь множества, задается в программе.

Изображение, полученное таким способом, является лишь приближением к реальному множеству Мандельброта. Более качественные результаты можно получать, увеличивая максимальное количество итераций, однако при этом пропорционально вырастает и время расчётов.

Примеры программ править

Пример программы построения множества (на языке программирования PHP) править 

<?php
/* Множество Мандельброта. */
/* Время создания */
set_time_limit(120);
function re_microtime() {
    list($usec, $sec) = explode(" ", microtime()); 
    return ((float)$usec + (float)$sec); }
/* Засекаем */
$time_start = re_microtime(); 

/* Размер картинки */
$img_w = 900;
$img_h = 600;

/* Начало и конец чертежа */
$x_min = -2;
$x_max = 1;
$y_min = -1;
$y_max = 1;

/* Подсчёт шага */
if($x_min >= 0 && $x_max >= 0){
	$step = ($x_min + $x_max)/$img_w;
} elseif($x_min < 0 && $x_max >= 0) { 
	$step = ($x_max - $x_min)/$img_w;
} else {
	$step = (-$x_min + $x_max)/$img_w; }

$img = imagecreatetruecolor($img_w,$img_h);
$c = array();

$yy = 0;
for($y = $y_min; $y < $y_max; $y = $y + $step){
	$xx = 0;
	for($x = $x_min; $x < $x_max; $x = $x + $step){

		$c['x'] = $x;
		$c['y'] = $y;
		$X = $x;
		$Y = $y;
		$ix=0; $iy=0; $n=0;

		while(($ix*$ix + $iy*$iy < 5) and ($n < 64)){
			$ix = $X*$X - $Y*$Y + $c['x'];
			$iy = 2*$X*$Y + $c['y'];
			$X = $ix;
			$Y = $iy;
			$n++;
		}

		$col = imagecolorallocate($img, 255-$n*5, 0, 0);
		imagesetpixel($img, $xx, $yy, $col);

	$xx++; }
$yy++; }

$time_end = re_microtime(); 
header("Content-type: image/png");
/* выводим в заголовках время создания */
header ("X-Exec-Time: ".($time_end - $time_start));
imagepng($img);
imagedestroy($img);
?>

Пример программы построения множества (на языке программирования C#) править 

using System;

namespace Mnoj
{
    class Program
    {
        static void Main(string[] args)
        {
            double realCoord, imagCoord;
            double realTemp, imagTemp, realTemp2, arg;
            int iterations;
            for (imagCoord = 1.2; imagCoord >= -1.2; imagCoord -= 0.05)
            {
                for (realCoord = -0.6; realCoord <= 1.77; realCoord += 0.03)
                {
                    iterations = 0;
                    realTemp = realCoord;
                    imagTemp = imagCoord;
                    arg = (realCoord * realCoord) + (imagCoord * imagCoord);
                    while ((arg < 4) && (iterations < 40))
                    {
                        realTemp2 = (realTemp * realTemp) - (imagTemp * imagTemp) + realCoord;
                        imagTemp = (2 * realTemp * imagTemp) + imagCoord;
                        realTemp = realTemp2;
                        arg = (realTemp * realTemp) + (imagTemp * imagTemp);
                        iterations += 1;
                    }
                    switch (iterations % 4)
                    {
                        case 0:
                            Console.Write(".");
                            break;
                        case 1:
                            Console.Write("o");
                            break;
                        case 2:
                            Console.Write("0");
                            break;
                        case 3:
                            Console.Write("@");
                            break;
                    }
                }
                Console.Write("\n");
            }
            Console.ReadKey();
        }
    }
}

Пример программы построения множества (на языке программирования паскаль) править 

uses
  System.Drawing, 
  System.Windows.Forms,
  System.Threading,
  FormsABC; 

procedure DrawMandelbrot(g: Graphics; w,h: integer; scale: real; dx,dy: integer);
const max = 10;
begin
  for var ix:=0 to w-1 do
  for var iy:=0 to h-1 do
  begin
    var x := 0.0;
    var y := 0.0;
    var cx := scale * (ix - dx);
    var cy := scale * (iy - dy);
    var i := 1;
    while i<255 do
    begin
      var x1 := x*x-y*y+cx;
      var y1 := 2*x*y+cy;
      x := x1;
      y := y1;
      if (abs(x)>max) and (abs(y)>max) then break;
      i += 1;
    end;
    if i>=255 then 
      g.FillRectangle(Brushes.Red,ix,iy,1,1)
    else 
      g.FillRectangle(new SolidBrush(Color.FromArgb(255,255-i,255-i)),ix,iy,1,1)
  end;
end;

var 
  Scale := new RealField('Масштаб: ');
  l1 := new FlowBreak;
  dx := new IntegerField('dx: ');
  l2 := new FlowBreak;
  dy := new IntegerField('dy: ');
  l3 := new FlowBreak(20);
  b := new Button(' Нарисовать ');
  p: PaintBox;


procedure Draw;
begin
  var g := p.Graphics;
  DrawMandelbrot(g,p.Width,p.Height,Scale.Value,dx.Value,dy.Value);
  p.Invalidate;
end;

procedure My(o: Object);
begin
  Draw;
end;

procedure Click;
begin
  ThreadPool.QueueUserWorkItem(My);
end;

begin
  MainForm.Title := 'Множество Мандельброта';
  MainForm.SetSize(700, 600);
  MainPanel.Dock := Dockstyle.Left;
  MainPanel.Width := 120;
  Scale.Value := 0.0035;
  dx.Value := 430;
  dy.Value := 280;
  b.Click += Click;

  ParentControl := MainForm;
  p := new PaintBox;
  p.Dock := DockStyle.Fill;
  ThreadPool.QueueUserWorkItem(My);
end.

Пример программы построения множества (на языке программирования C++ с использованием SFML) править 

///Heared.hpp
#pragma once

#include <SFML\Graphics.hpp>
//#include <boost\math\bindings\rr.hpp>

typedef long double TYPE;


template<typename T>
struct Complex
{
	T re;
	T im;

	Complex operator += (const Complex & other)
	{
		re += other.re;
		im += other.im;

		return *this;
	}

	Complex operator + (const Complex & other)
	{
		Complex c(*this);
		return c += other;
	}
	Complex operator *= (const Complex & other)
	{
		Complex c;
		c.re = re * other.re - im * other.im;
		c.im = re * other.im + im * other.re;

		*this = c;
		return *this;
	}

	Complex operator * (const Complex & other)
	{
		Complex c(*this);
		return c *= other;
	}
	Complex operator = (const Complex & other)
	{
		re = other.re;
		im = other.im;
		return *this;
	}

	Complex(): re((T)0), im((T)0)
	{
	}

	Complex(const Complex& other) : re(other.re), im(other.im)
	{
	}
	Complex(const T& re, const T& im) : re(re), im(im)
	{
	}
	Complex(const T& re) : re(re), im((T)0)
	{
	}

	T module_sqr()const
	{
		return re * re + im * im;
	}
};



//void drawM(sf::Vector2<TYPE> x, sf::Vector2<TYPE> y);

///draw.cpp
#include "Header.hpp"

void step_clr(sf::Color & clr)
{
	clr.r = clr.r + 5 < 0x100 ? clr.r + 5 : 0xff;
	clr.g = clr.g + 3 < 0x100 ? clr.g + 5 : 0xff;
	clr.b = clr.b + 2 < 0x100 ? clr.b + 5 : 0xff;
}

void drawM(sf::Vector2<TYPE> x, sf::Vector2<TYPE> y)
{
	const TYPE epsilon = 0.005;
	sf::Vector2i sizewindow((int)((x.y - x.x) / epsilon), (int)((y.y - y.x) / epsilon));
	sf::RenderWindow window(sf::VideoMode(sizewindow.x, sizewindow.y), "Mandelbroth");
	sf::Image im;
	const int max_it = 250;
	const int infinity_sqr = 10000;
	im.create(sizewindow.x, sizewindow.y);

	sf::Color clr;
	int xim = 0, yim = 0;
	for (TYPE currx = x.x; currx <= x.y; currx += epsilon, ++xim)
	{
		yim = 0;
		while (xim >= sizewindow.x)
			--xim;
		for (TYPE curry = y.x; curry <= y.y; curry += epsilon, ++yim)
		{
			while (yim >= sizewindow.y)
				--yim;
			clr = sf::Color::Black;
			Complex<TYPE> curr;

			im.setPixel(xim, yim, sf::Color::Black);

			for (int i = 0; i < max_it; ++i)
			{
				if (curr.module_sqr() >= infinity_sqr)
				{
					im.setPixel(xim, yim, clr);
					break;
				}
				curr = curr * curr + Complex<TYPE>(currx, curry);
				step_clr(clr);
			}
		}
	}

	sf::Sprite s;
	sf::Texture t;
	t.loadFromImage(im);
	s.setTexture(t);
	while (window.isOpen())
	{
		sf::Event event;

		while (window.pollEvent(event))

		{

			if (event.type == sf::Event::Closed)

				window.close();

		}

		window.clear();

		window.draw(s);

		window.display();

	}


}

///main.cpp
#include "Header.hpp"
#include "draw.cpp"
#include <iostream>

int main()
{
	TYPE x1, x2, y1, y2;

	//std::cin >> x1 >> x2 >> y1 >> y2;
	x1 = -2.5;
	x2 = 2;

	y1 = -1.5;
	y2 = 1.5;
	drawM(sf::Vector2<TYPE>(x1, x2), sf::Vector2<TYPE>(y1, y2));
}

Добавление цвета править

 
Фрагмент границы множества Мандельброта в цветном варианте

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

Порядок определения, попадает ли точка z0 внутрь множества (традиционно закрашиваемого чёрным цветом) или нет (закрашивается цветом, зависящим от скорости движения к бесконечности) следующий: на каждой итерации для zn=xn+yn·i вычисляется значение модуля  , которое затем сравнивается с «границей бесконечности» (обычно берётся значение, равное 2). Здесь важно обратить внимание, что уже на данном этапе можно ввести определённую оптимизацию вычислений, если проверять не  , а  , что значительно снизит время расчётов.

Таким образом, если |zn|2 ≤ 4 при любом числе итераций (на практике — при всех вычисленных итерациях), то цвет точки чёрный, в противном случае он зависит от последнего значения n, при котором |zn|2 ≤ 4. Значение n, фактически, обозначает скорость движения zn в бесконечность, и может быть просто индексом в таблице цветов, или использоваться как параметр в более сложном алгоритме.

Данный алгоритм определяет, что если точка удаляется больше чем на 2 от начала координат, то она лежит снаружи множества Мандельброта. Для того, чтобы определить, что точка лежит внутри множества есть много способов. Самое простое решение — ограничить количество итераций неким максимумом. Если точка не вышла за указанную границу, можно считать, что она находится внутри множества.

Точкам около границы множества нужно больше итераций для ухода в бесконечность. Поэтому такие области прорисовываются заметно дольше. Чем дальше от границ множества, тем выше скорость ухода в бесконечность. Для таких точек требуется меньше итераций.

Пример добавления цвета (на PHP) править 

<?php

// Default: http://<host>/<dir>/<filename>.php?iter1=64&width=600&height=400&coef=32

function BN($n, $l, $r) {return $n>$l && $n<=$r;}
function SQR($a) {return $a*$a;}

define("COEF",	$_GET["coef"]);
$iter1	=	$_GET["iter1"];
$width	=	$_GET["width"];
$height	=	$_GET["height"];

header("Content-type: image/png");

$img	=	imagecreatetruecolor($width, $height);
$iter2	=	0.01/($width/300);
$yy	=	-1;

for ($y = -1; $y < 1; $y = $y + $iter2) {
	$yy++; $xx=-1;
	for($x = -2; $x < 1; $x = $x + $iter2) {
		$xx++;
		$Cx	=	$x;
		$Cy	=	$y;
		$X	=	$x;
		$Y	=	$y;
		$ix	=	0;
		$iy	=	0;
		$n	=	0;
		while ((SQR($ix) + SQR($iy) < 4) and ($n < $iter1)) {
			$ix 	=	SQR($X) - SQR($Y) + $Cx;
			$iy 	=	2*$X*$Y + $Cy;
			$X	=	$ix;
			$Y	=	$iy;
			$n++;
		}
		if(BN($n,0,7)) $col = imagecolorallocate($img,COEF*$n,0,0);
		elseif(BN($n,7,14)) $col = imagecolorallocate($img,COEF*$n,COEF*$n,0);
		elseif(BN($n,14,21))$col = imagecolorallocate($img,COEF*$n,0,COEF*$n);
		elseif(BN($n,21,28))$col = imagecolorallocate($img,0,COEF*$n,0);
		elseif(BN($n,28,35))$col = imagecolorallocate($img,COEF*$n,COEF*$n,0);
		elseif(BN($n,35,42))$col = imagecolorallocate($img,0,COEF*$n,COEF*$n);
		elseif(BN($n,42,49))$col = imagecolorallocate($img,0,0,COEF*$n);
		elseif(BN($n,49,56))$col = imagecolorallocate($img,COEF*$n,0,COEF*$n);
		elseif(BN($n,56,64))$col = imagecolorallocate($img,0,COEF*$n,COEF*$n);
		imagesetpixel($img, $xx, $yy, $col);
	}
}
imagepng($img);
imagedestroy($img);
?>

Пример добавления цвета (на C++) править 

///draw.cpp
#include "Header.hpp"

void step_clr(float & red, float & green, float & blue)
{
	red = (int)(red + 5) < 0xff ? red + 5 : 0xff;
	if((int)red == 0xff)
		green = (int)(green + 3.5) < 0xff ? green + 3.5 : 0xff;
	if((int)green == 0xff)
		blue = (int)(blue + 2.2) < 0xff ? blue + 2.2 : 0xff;
}

void drawM(sf::Vector2<TYPE> x, sf::Vector2<TYPE> y)
{
	const TYPE epsilon = 0.005;
	sf::Vector2i sizewindow((int)((x.y - x.x) / epsilon), (int)((y.y - y.x) / epsilon));
	sf::RenderWindow window(sf::VideoMode(sizewindow.x, sizewindow.y), "Mandelbroth");
	sf::Image im;
	const int max_it = 250;
	const int infinity_sqr = 10000;
	im.create(sizewindow.x, sizewindow.y);

	sf::Color clr;
	int xim = 0, yim = 0;
	for (TYPE currx = x.x; currx <= x.y; currx += epsilon, ++xim)
	{
		yim = 0;
		while (xim >= sizewindow.x)
			--xim;
		for (TYPE curry = y.x; curry <= y.y; curry += epsilon, ++yim)
		{
			while (yim >= sizewindow.y)
				--yim;
			clr = sf::Color::Black;
			Complex<TYPE> curr;
			float red = 0, green = 0, blue = 0;

			im.setPixel(xim, yim, sf::Color::Black);

			for (int i = 0; i < max_it; ++i)
			{
				if (curr.module_sqr() >= infinity_sqr)
				{
					clr = sf::Color(red, green, blue);
					im.setPixel(xim, yim, clr);
					break;
				}
				curr = curr * curr + Complex<TYPE>(currx, curry);
				step_clr(red, green, blue);
			}
		}
	}

	sf::Sprite s;
	sf::Texture t;
	t.loadFromImage(im);
	s.setTexture(t);
	while (window.isOpen())
	{
		sf::Event event;

		while (window.pollEvent(event))

		{

			if (event.type == sf::Event::Closed)

				window.close();

		}

		window.clear();

		window.draw(s);

		window.display();

	}


}
Источник — https://ru.wikibooks.org/w/index.php?title=Множество_Мандельброта&oldid=163862