Матрица статей        Список статей        Всячина        Контакты       

Треугольник Серпинского

Построение треугольника Серпинского с помощью рекурсии

В 1915 году польский математик Вацлав Серпинский придумал занимательный объект, известный как решето Серпинского. Этот треугольник один из самых ранних известных примеров фракталов. Существует несколько способов построения этого фрактала. Один из них представляет следующий процесс. Берётся сплошной равносторонний треугольник, на первом шаге из центра удаляется перевёрнутый треугольник. На втором шаге удаляется три перевёрнутых треугольника из трёх оставшихся треугольников. Продолжая этот процесс, на -ом шаге удаляем перевёрнутых треугольников из центров оставшихся треугольников. Конца этому процессу не будет, и в треугольнике не останется живого места, но и на части он не распадётся - получится объект состоящий из одних только дырок. Это и есть треугольник Серпинского. Треугольник Серпинского также называют салфеткой Серпинского.


Треугольник Серпинского

program FracSierp2;
uses CRT, Graph;

var
	gd, gm : Integer;

const
	iter = 5;

procedure tr(x1, y1, x2, y2, x3, y3: Real);
begin
	Line(Round(x1), Round(y1), Round(x2), Round(y2));
	Line(Round(x2), Round(y2), Round(x3), Round(y3));
	Line(Round(x3), Round(y3), Round(x1), Round(y1));
end;

procedure draw(x1, y1, x2, y2, x3, y3: Real; n: Integer);
var
	x1n, y1n, x2n, y2n, x3n, y3n : Real;
begin
	if  n > 0  then 
	begin
		x1n := (x1 + x2) / 2;
		y1n := (y1 + y2) / 2;
		x2n := (x2 + x3) / 2;
		y2n := (y2 + y3) / 2;
		x3n := (x3 + x1) / 2;
		y3n := (y3 + y1) / 2;
		tr(x1n, y1n, x2n, y2n, x3n, y3n);
	
		draw(x1, y1, x1n, y1n, x3n, y3n, n - 1);
		draw(x2, y2, x1n, y1n, x2n, y2n, n - 1);
		draw(x3, y3, x2n, y2n, x3n, y3n, n - 1);
	end;
end;

begin
	gd := Detect;
	InitGraph(gd, gm, '');
	tr(320,10,600,470,40,470);
	draw(320,10,600,470,40,470,iter);{}
	ReadKey;
	CloseGraph;
end.

IFS-алгоритм построения

Треугольник Серпинского также легко можно построить с помощью трех IFS-преобразований. Эти преобразования имеют вид:

Программа для построения треугольника Серпинского этим методом на языке Pascal приведена ниже.

program FracSierp;
uses CRT, Graph;
var
	gd, gm : Integer;
procedure draw;
const iter = 50000;
var
	t, x, y, p : Real;
	k : LongInt;
	mx, my, rad : Integer;
begin
	mx := 320;
	my := 479;
	rad := my;
	Randomize;
	x := 0.0;
	y := 0.0;
	for k := 1 to iter do 
	begin
		p := Random;
		t := x;
		if p >= 1/3 then 
		begin
			x :=  0.50 * x + 0.00 * y + 0.0;
			y :=  0.00 * t + 0.50 * y + 0.5;
		end
		else
		if p >= 2/3 then 
		begin
			x :=  0.50 * x + 0.00 * y - 0.25;
			y :=  0.00 * t + 0.50 * y + 0.0;
		end
		else 
		begin
			x :=  0.50 * x + 0.00 * y + 0.25;
			y :=  0.00 * t + 0.50 * y + 0.0;
		end;
		PutPixel(mx + Round(rad * x), my - Round(rad * y), 2);
	end;
end;

begin
	gd := Detect;
	InitGraph(gd,gm,'');
	draw;
	ReadKey;
	CloseGraph;
end.

Треугольник Серпинского

program Sierp10;
uses CRT, Graph;
var
	gd, gm: Integer;
	l, x, y: Real;
begin
	gd:=Detect;
	InitGraph(gd, gm, 'c:\bp\bgi');
	x:=0; y:=0;
	Randomize;
	while not Keypressed do 
	begin
		l := 2/3*pi*random(3);
		x := x/2+cos(l);
		y := y/2+sin(l);
		PutPixel(320 + Round(x*130), 240 + Round(y*130), 14);
	end;
	Readkey;
	CloseGraph;
end.

Построение с помощью треугольника Паскаля

Треугольник Серпинского можно построить, используя треугольник Паскаля по модулю 2.


Треугольник Серпинского

package ru.xaoc.fractalworld.numbertriangles;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Main {
    public static Image draw(int[][] A) {
        int r = A.length;
        int s = A[0].length;
        BufferedImage image = 
		new BufferedImage(s, r, BufferedImage.TYPE_INT_RGB);
        Graphics2D graphics = image.createGraphics();
        graphics.setColor(Color.WHITE);
        graphics.fill(new Rectangle2D.Double(0, 0, s, r));
        graphics.setColor(Color.BLACK);
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < s; ++j) {
                if (A[i][j] != 0) {
                    graphics.fillRect(j, i, 1, 1);
                }
            }
        }
        return image;
    }

    public static int[][] generatePascalTriangle(int n, int m) {
        int[][] T = new int[n][n];
        for (int i = 0; i < n; ++i) {
            T[i][0] = 1;
            for (int j = 1; j <= i; ++j) {
                T[i][j] = (T[i - 1][j - 1] + T[i - 1][j]) % m;
            }
            for (int j = i + 1; j < n; ++j) {
                T[i][j] = 0;
            }
        }
        return T;
    }

    public static Image drawSierpinskiTriangle(int n, int m) {
        return draw(generatePascalTriangle(n, m));
    }

    public static Image image;

    public static void main(String[] args) {
        image = drawSierpinskiTriangle(512, 2);
        // image = drawSierpinskiTriangle(729, 3);
        // image = drawSierpinskiTriangle(512, 4);
        // image = drawSierpinskiTriangle(625, 5);
        // image = drawSierpinskiTriangle(512, 8);

        int width = image.getWidth(null);
        int height = image.getHeight(null);
        JFrame frame = new JFrame();
        frame.addNotify();
        frame.setSize(frame.getInsets().left +
                frame.getInsets().right + width,
                frame.getInsets().top +
                frame.getInsets().bottom + height);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        frame.add(new JPanel() {
            @Override
            public void paintComponent(Graphics g) {
                Graphics2D G = (Graphics2D) g;
                if (image != null) {
                    G.drawImage(image, 0, 0, null);
                }
            }
        });
        frame.setVisible(true);
    }
}

Ниже приведены изображения треугольника Паскаля по модулю 3, 4, 5 и 8.


Треугольник Серпинского Треугольник Серпинского Треугольник Серпинского Треугольник Серпинского

Вариации на тему треугольника Серпинского

Изменим процедуру построения треугольника следующим образом, будем делить отрезки не пополам, а в некотором отношении (т.е. соединять не середины отрезков, а некоторые другие точки). Тогда мы получим нечто следующее:

Вариации на тему треугольника Серписнского

program FractSerp2;
uses CRT, Graph;

var
	gd, gm : Integer;

const
	Iter = 6;
	r    = 0.8;

procedure Tr(x1, y1, x2, y2, x3, y3: Real);
begin
	Line(round(x1), round(y1), round(x2), round(y2));
	Line(round(x2), round(y2), round(x3), round(y3));
	Line(round(x3), round(y3), round(x1), round(y1));
end;


procedure Draw(x1, y1, x2, y2, x3, y3: Real; n: Integer);
var
	x1n, y1n, x2n, y2n, x3n, y3n : Real;

begin
	if n > 0 then
	begin
		x1n := (x1*r + x2) / (1+r);
		y1n := (y1*r + y2) / (1+r);
		x2n := (x2*r + x3) / (1+r);
		y2n := (y2*r + y3) / (1+r);
		x3n := (x3*r + x1) / (1+r);
		y3n := (y3*r + y1) / (1+r);
		Tr(x1n, y1n, x2n, y2n, x3n, y3n);
		Draw(x1, y1, x1n, y1n, x3n, y3n, n - 1);
		Draw(x2, y2, x1n, y1n, x2n, y2n, n - 1);
		Draw(x3, y3, x2n, y2n, x3n, y3n, n - 1)
	end
end;

begin
	gd := Detect;
	Randomize;
	InitGraph(gd,gm,'c:\bp\bgi');
	Tr(320,10,600,470,40,470);
	Draw(320,10,600,470,40,470,iter);{}
	Readkey;
	CloseGraph;
end.

Снова изменим процедуру. Теперь на каждом шаге стороны треугольников будем разбивать случайным образом. Получится примерно следующее:

Вариации на тему треугольник Серписнского

program FractSierp2;

uses CRT, Graph;

var
	gd, gm : Integer;

const
	Iter = 8;

procedure Tr(x1, y1, x2, y2, x3, y3: Real);
begin
	Line(Round(x1), Round(y1), Round(x2), Round(y2));
	Line(Round(x2), Round(y2), Round(x3), Round(y3));
	Line(Round(x3), Round(y3), Round(x1), Round(y1))
end;

procedure Draw(x1, y1, x2, y2, x3, y3: Real; n: Integer);
var
	x1n, y1n, x2n, y2n, x3n, y3n : Real;
	r, q: Real;
begin
	if  n > 0  then 
	begin
		r := Random;
		q := Random;
		x1n := (x1*r + x2*q) / (q+r);
		y1n := (y1*r + y2*q) / (q+r);
		r := Random;
		q := Random;
		x2n := (x2*r + x3*q) / (q+r);
		y2n := (y2*r + y3*q) / (q+r);
		r := Random;
		q := Random;
		x3n := (x3*r + x1*q) / (q+r);
		y3n := (y3*r + y1*q) / (q+r);
		Tr(x1n, y1n, x2n, y2n, x3n, y3n);
		Draw(x1, y1, x1n, y1n, x3n, y3n, n - 1);
		Draw(x2, y2, x1n, y1n, x2n, y2n, n - 1);
		Draw(x3, y3, x2n, y2n, x3n, y3n, n - 1)
	end
end;

begin
	gd := Detect;
	Randomize;
	InitGraph(gd,gm,'c:\bp\bgi');
	repeat
        	ClearDevice;
		Tr(320, 10, 600, 470, 40, 470);
		Draw(320, 10, 600, 470, 40, 470, Iter);
	until Readkey = #27;
	CloseGraph
end.

Ещё один способ построения


Треугольник Серпинского

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

Более подробно этот метод объяснён в статье Построение аттракторов СИФ с помощью алгоритма времени убегания.

program Sierp;
uses Graph, Crt;
type
	TComplex = record
		X : Real;
		Y : Real;
	end;
const
	iter = 50;
	max  = 127;
var
	z : TComplex;
	x, y, n : Integer;
	gd, gm  : Integer;
	mx, my  : Integer;
begin
	gd := Detect;
	InitGraph(gd,gm,'c:\bp\bgi');
	Mx := GetMaxX div 2;
	My := GetMaxY div 2;
	for y := -my to my do
		for x := -mx to mx do
		begin
			n := 0;
         		z.x := X * 0.005;
			z.y := Y * 0.005;
			while (sqr(z.x) + sqr(z.y) < max) and (n < iter) do 
			begin
				if z.y > 0.5 then 
				begin
					z.x := 2*z.x;
					z.y := 2*z.y-1;
				end 
				else if z.x > 0.5 then 
				begin
					z.x := 2*z.x-1;
					z.y := 2*z.y;
				end 
				else
				begin
					z.x := 2*z.x;
					z.y := 2*z.y;
				end;
				Inc(n);
			end;
			PutPixel(mx + x,my + y,16 - (n mod 16));
			if KeyPressed then 
				break;
		end;
	Readkey;
	CloseGraph;
end.

Смотрите также:

Ссылки: