5. Iterated Function Systems

Werner Van Belle¹^*⁺ - werner@yellowcouch.org, werner.van.belle@gmail.com
Thomas Unger¹⁺ - thomas.unger@ucd.ie

1- Programming Technology Lab (PROG) Department of Computer Science (DINF) Vrije Universiteit Brussel (VUB); Pleinlaan 2; 1050 Brussel; Belgium
* Corresponding author; + Equal Contribution

Abstract : Takes a detour in Iterated Function Systems (IFS)

Reference: Werner Van Belle, Thomas Unger; Iterated Function Systems;

Info

Neem een vast coordinaten systeem. Een punt in het vlak RxR kan dan geschreven worden als P = (x,y) relatief ten opzichte van dat coordinaat systeem. Punten kunnen opgeteld en afgetrokken worden door hun coordinaten respectievelijk op te tellen of af te trekken. Een punt kan vermenigvuldigd worden met een reeel getal door elke coordinaat van het punt te vermenigvuldigen met dit getal.

Een lineare afbeelding is een transformatie die met elk punt P in het vlak een punt F(P) associeert zodat:

F(P1+P2)=F(P1)+F(P2)

Voor alle punten P1 en P2 en

F(sP)=sF(P)

Voor elk reeel getal s en alle punten P

Een lineare transformatie ten opzichte van het huidige coordinatensysteem kan gerepresenteerd worden door een matrix

waarbij, als P = (x,y) en F(P)=(u,v), dan

Een affiene lineare transformatie is een lineartie transformatie gevolgd door een translatie. Met andere woorden, als F een lineare mapping is en Q=(e,f) is een punt dan is de nieuwe mapping:

Als hierin P = (x,y) en w(P) = (u,v) dan kan de transformatie geschreven worden als

Een geitereerd functiesysteem kan nu beschreven worden als een verzameling van affiene transformaties w1,w2,w3,…,wn. Voor een gegeven initiele tekening A worden kleine affiene kopies gemaakt: w1(A), w2(A)… wn(A). De oorspronkelijke tekening wordt dan vervangen door de nieuwe tekening.

W wordt de hutchinson operator genoemd. De essentie van een geitereerd functie systeem is het herhalen van de operator W. We vertrekken met een bepaalde starttekening A0. Hieruit bekomen we A1=W(A0). A2=W(A1) en zo verder. Een IFS genereerd een sequentie van dergelijke tekeningen om zo te convergeren tot een eindtekening , dewelke de attractor van het IFS genoemd wordt. Merk op dat deze onafhankelijk is van de gegeven starttekening.^¹

Oef1: Implementeer een IFS

Shrijf een programma dat gegeven een aantal affiiene transformaties de eindtekening op het scherm tekend. Noot: zoek de parameters van de affiene transformatie om de sierpinski driehoek te kunnen visualiseren.

Oef2: Test uw algoritme met de volgende parameters

The Twin Christmas Tree

a	b	c	d	e	f
0	-0.5	0.5	0	0.5	0
0	0.5	-0.5	0	0.5	0.5
0.5	0	0	0.5	0.25	0.5

A Dragon With Treefold Symmetry

a	b	c	d	e	f
0	0.577	-0.577	0	0.951	0.5893
0	0.577	-0.577	0	0.4413	0.7893
0	0.577	-0.577	0	0.0952	0.9893

Crystal with Five Transformations

a	b	c	d	e	f
0.382	0	0	0.382	0.3072	0.619
0.382	0	0	0.382	0.6033	0.4044
0.382	0	0	0.382	0.0139	0.4044
0.382	0	0	0.382	0.1253	0.0595
0.382	0	0	0.382	0.492	0.0595

A Tree

a	b	c	d	e	f
0.195	-0.488	0.344	0.443	0.4431	0.2452
0.462	0.414	-0.252	0.361	0.2511	0.5692
-0.058	-0.07	0.453	-0.111	0.5976	0.0969
-0.035	0.07	-0.469	-0.022	0.4884	0.5069
-0.637	0	0	0.501	0.8562	0.2513

Barnsley’s Fern

a	b	c	d	e	f
0.849	0.037	-0.037	0.849	0.075	0.183
0.197	-0.226	0.226	0.197	0.4	0.049
-0.15	0.283	0.26	0.237	0.575	-0.084
0	0	0	0.16	0.5	0

Solution Oef1:

#include <vga.h>

static struct transform {float a,b,c,d,e,f;} t[3] =
       {{0.0,-0.5,0.5,0.0,0.5,0.0},
	{0.0,0.5,-0.5,0.0,0.5,0.5}, 
	{0.5,0.0,0.0,0.5,0.5,0.5}};

float Fx(int nr, float x, float y)
{return x*t[nr].a + y*t[nr].b + t[nr].e;}

float Fy(int nr, float x, float y)
{return x*t[nr].c + y*t[nr].d + t[nr].f;}

void drawifs(float x, float y,int d)
{
   if (d>0) 
     {  drawifs(Fx(0,x,y),Fy(0,x,y),d-1);
	drawifs(Fx(1,x,y),Fy(1,x,y),d-1);
	drawifs(Fx(2,x,y),Fy(2,x,y),d-1);
     }
   else
     vga_drawpixel(x*0,y*0);
}

void main(void)
{
   vga_setmode(G640x480x16);
   vga_setcolor(4);
   drawifs(0,0,5);
   sleep(0);
}

1 De affiene transformaties die we zullen gebruiken zijn effectief contracties. De IFSen die we zullen implementeren zijn deterministisch. Het is evengoed mogelijk random IFSen te genereren.

http://werner.yellowcouch.org/
werner@yellowcouch.org