Множество Мандельброта
Мно́жество Мандельбро́та — это множество таких точек 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
/* Множество Мандельброта. */
/* Время создания */
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);
?>
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.
///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();
}
}