Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... ·...

12
Cursul 9 Fractali generat ¸i de sisteme de funct ¸ii iterate Vom prezenta ˆ ın continuare o generalizare a metodei transform˘arilor geome- trice folosit˘a de noi pentru generarea fractalilorˆ ın plan. De exemplu, generarea curbei lui Takagi printr-un sistem de dou˘a transform˘ari, T 1 ¸ si T 2 , a constat din considerarea unei figuri init ¸iale F 0 ¸ si transformarea ei repetat˘a, la fiecare etap˘a figura nou˘a fiind format˘a din reuniunea imginilor punctelor vechi prin cele dou˘a transform˘ari: F n+1 = T 1 (F n ) T 2 (F n ). (1) S˘a observ˘am c˘a sistemul de funct ¸ii {T 1 ,T 2 } determin˘a o aplicat ¸ie T prin relat ¸ia T (F )= T 1 (F ) T 2 (F ) ¸ si astfel ¸ sirul de figuri (F n ) n definit de (1) devine ¸ sirul aproximat ¸iilor succesive asociat acestei aplicat ¸ii. Vom ar˘ata c˘a pe mult ¸imea figurilor poate fi definit˘a o metric˘a astfelˆ ıncˆ at ˆ ın acest spat ¸iu metric aplicat ¸ia T s˘a fie o contract ¸ie. Prin urmare figuralimit˘a, curba lui Takagi, este punctul fix al lui T , deci un atractor global. Prin figur˘ a noi ˆ ınt ¸elegem o mult ¸ime de puncte din plan, dar ˆ ın continuare ˆ ın locul planului vom considera un spat ¸iu metric oarecare (X, dsi vom c˘auta s˘a definim un mod convenabil de a m˘asura distant ¸a dintre dou˘a submult ¸imi ale sale. Metrica Hausdorff-Pompeiu ˆ In ultimii ani, ˆ ın grafica computat ¸ional˘ a, de exemplu ˆ ın probleme de re- cunoa¸ stere automat˘a a formelor, a ap˘arut necesitatea de a m˘asura gradul de potrivire a dou˘a figuri sau, altfel spus, de a calcula distant ¸a dintre dou˘a mult ¸imi de puncte (astfel ˆ ıncˆ at distant ¸a nul˘ a s˘a corespund˘a suprapunerii perfecte, de- sigur). De¸ si ˆ ın acest caz mult ¸imile considerate sunt finite ¸ si astfel problema este mult simplificat˘a, de un real folos s-a dovedit totu¸ si o modalitate general˘a de definire a distant ¸ei ˆ ıntre submult ¸imile unui spat ¸iu metric oarecare, ¸ si anume cea propus˘a de Dimitrie Pompeiu (1873–1954) ˆ ın teza sa de doctorat din 1905 ¸ si reluat˘a cu modific˘ari minore de Felix Hausdorff (1868–1942)ˆ ın 1914. Distant ¸a Hausdorff-Pompeiu se define¸ ste, ˆ ın general, ˆ ıntre submult ¸imilem˘ar- ginite ¸ si ˆ ınchise ale unui spat ¸iu metric, noi vom prefera ˆ ıns˘a cazul special al 1

Transcript of Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... ·...

Page 1: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

Cursul 9

Fractali generati de sisteme de functii iterate

Vom prezenta ın continuare o generalizare a metodei transformarilor geome-trice folosita de noi pentru generarea fractalilor ın plan. De exemplu, generareacurbei lui Takagi printr-un sistem de doua transformari, T1 si T2, a constat dinconsiderarea unei figuri initiale F0 si transformarea ei repetata, la fiecare etapafigura noua fiind formata din reuniunea imginilor punctelor vechi prin cele douatransformari:

Fn+1 = T1(Fn) ∪ T2(Fn). (1)

Sa observam ca sistemul de functii {T1, T2} determina o aplicatie T prinrelatia

T (F ) = T1(F ) ∪ T2(F )

si astfel sirul de figuri (Fn)n definit de (1) devine sirul aproximatiilor succesiveasociat acestei aplicatii. Vom arata ca pe multimea figurilor poate fi definita ometrica astfel ıncat ın acest spatiu metric aplicatia T sa fie o contractie. Prinurmare figura limita, curba lui Takagi, este punctul fix al lui T , deci un atractorglobal.

Prin figura noi ıntelegem o multime de puncte din plan, dar ın continuareın locul planului vom considera un spatiu metric oarecare (X, d) si vom cautasa definim un mod convenabil de a masura distanta dintre doua submultimi alesale.

Metrica Hausdorff-Pompeiu

In ultimii ani, ın grafica computationala, de exemplu ın probleme de re-cunoastere automata a formelor, a aparut necesitatea de a masura gradul depotrivire a doua figuri sau, altfel spus, de a calcula distanta dintre doua multimide puncte (astfel ıncat distanta nula sa corespunda suprapunerii perfecte, de-sigur). Desi ın acest caz multimile considerate sunt finite si astfel problema estemult simplificata, de un real folos s-a dovedit totusi o modalitate generala dedefinire a distantei ıntre submultimile unui spatiu metric oarecare, si anume ceapropusa de Dimitrie Pompeiu (1873–1954) ın teza sa de doctorat din 1905 sireluata cu modificari minore de Felix Hausdorff (1868–1942) ın 1914.

Distanta Hausdorff-Pompeiu se defineste, ın general, ıntre submultimile mar-ginite si ınchise ale unui spatiu metric, noi vom prefera ınsa cazul special al

1

Page 2: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

submultimilor compacte, ın care avem asigurata completitudinea si, prin urmare,aplicabilitatea Teoremei de punct fix a lui Banach.

Incepem prin a reaminti cateva notiuni si rezultate privind compactitatea ınspatii metrice. Fie (X, d) un spatiu metric complet. Spunem ca submultimeaA ⊂ X este compacta daca orice sir de elemente din A are cel putin un subsirconvergent la un element tot din A. Stim ca ın spatiile Rn o multime este com-pacta daca si numai daca este marginita si ınchisa, dar aceasta caracterizarenu se pastreaza ın general. Intr-un spatiu metric complet o multime este com-pacta daca si numai daca este total marginita si ınchisa. Submultimea A ⊂ Xeste total marginita daca pentru orice ε > 0 exista un numar finit de elementea1, a2, . . . , anε ın A astfel ıncat

A ⊂ ∪nεi=1S(ai, ε).

In particular, orice multime finita este compacta.Utilitatea multimilor compacte provine, mai ales, din urmatoarea proprietate:

orice functie continua, cu valori reale, definita pe un compact este marginita si ısiatinge marginile. Aceasta datorita faptului ca imaginea printr-o functie continuaa unei multimi compacte este compacta.

In continuare vom nota cu H(X) clasa submultimilor compacte si nevide alelui X.

Definitia 1. Fie A si B doua submultimi compacte si nevide ale lui X si fiea ∈ X un element oarecare. Notam distanta de la a la B prin

d(a,B) = infb∈B

d(a, b), (2)

si excesul lui A fata de B prin

e(A,B) = supa∈A

d(a,B). (3)

Prin distanta Hausdorff-Pompeiu dintre A si B ıntelegem numarul real

h(A,B) = max{e(A,B), e(B,A)}. (4)

Teorema 1 (Hausdorff). Fie H(X) clasa submultimilor compacte si nevideale spatiului metric complet (X, d). Functia h : H(X) × H(X) → R definitade relatia (4) este o metrica pe H(X). Mai mult, spatiul metric (H(X), h) estecomplet.

Demonstratie. Deoarece submultimile A si B sunt compacte iar aplicatiileb 7→ d(a, b) si a 7→ d(a,B) sunt continue, infimumul din (2) si supremumul din(3) sunt atinsi. Prin urmare, din d(a,B) = 0 rezulta a ∈ B si, ın consecinta, dine(A,B) = 0 rezulta A ⊂ B. Obtinem ca pentru orice A si B din H(X) distantah(A,B) este finita si nenula, iar h(A,B)=0 implica A = B.

2

Page 3: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

Proprietatea de simetrie, h(A,B) = h(B,A) este evidenta. Pentru a demon-stra inegalitatea triunghiulara, vom arata mai ıntai ca, pentru orice A, B si Cdin H(X) are loc

e(A,B) ≤ e(A,C) + e(C,B). (5)

In adevar, pentru a ∈ A fixat arbitrat, avem

d(a,B) = infb∈B

d(a, b) ≤ infb∈B

{d(a, c) + d(c, b)}

= d(a, c) + infb∈B

d(c, b) = d(a, c) + d(c, B)

≤ d(a, c) + supc∈C

d(c, B) = d(a, c) + e(C,B)

pentru orice c ∈ C. Trecem la infimum dupa c ∈ C si obtinem

d(a,B) ≤ d(a, C) + e(C,B).

Deoarece a ∈ A a fost fixat arbitrar, putem trece la supremum dupa a ∈ A ininegalitatea de mai sus, si obtinem relatia (5).

Din (5) urmeaza imediat ca

e(A,B) ≤ h(A,C) + h(C,B).

Schimband A si B ıntre ele avem

e(B,A) ≤ h(B,C) + h(C,A),

de unde obtinem inegalitatea dorita:

h(A,B) ≤ h(A,C) + h(C,B).

Am aratat ca (H(X), h) este un spatiu metric. Justificarea completitudiniiacestui spatiu metric este mai laborioasa si depaseste scopul nostru. Mentionamnumai urmatoarea caracterizare a limitei unui sir (An) din H(X) ın metricaHausdorff-Pompeiu: daca An → A∗ (adica h(An, A

∗) → 0), atunci

A∗ = {a∗ ∈ X | exista un sir (an) ın X, cu an ∈ An, a.ı. an → a∗}.�

Pentru A ∈ H(X) si ε > 0 vom nota

A+ ε = {x ∈ X | d(x,A) ≤ ε }.Se poate arata ca au loc urmatoarele caracterizari:

Teorema 2. Pentru orice A si B in H(X) avem

h(A,B) = inf {ε > 0 | A ⊆ B + ε si B ⊆ A+ ε}si

h(A,B) = supx∈X

|d(x,A)− d(x,B)|.

3

Page 4: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

Sisteme de functii iterate

Fie (X, d) un spatiu metric complet si (H(X), h) spatiul metric Hausdorff-Pompeiu corespunzator. Oricarei transformari punctuale S : X → X ıi asociem

transformarea de multime S definita de

S(A) = {S(a), a ∈ A} pentru orice A ⊂ X.

Sa observam ca daca S este continua, orice submultime compacta nevida A ⊂ X

are imaginea S(A) compacta si nevida, deci ın acest caz S : H(X) → H(X).

Dorim sa aflam ce proprietati are S cand S este o contractie. Rezultatul esteurmatorul:

Teorema 3. Daca S : X → X este o contractie cu constanta Lipschitz q

atunci si S : H(X) → H(X) este o contactie cu aceeasi constanta q. Atractorul

contractiei S este multimea A∗ = {a∗}, unde a∗ este atractorul lui S.

Demonstratie. Fie A si B doua submultimi din clasa H(X). Avem

e(S(A), S(B)) = supa∈A

infb∈B

d(S(a), S(b))

≤ q supa∈A

infb∈B

d(a, b) ≤ qe(A,B) ≤ qh(A,B),

de unde urmeaza imediat ca

h(S(A), S(B)) ≤ qh(A,B).

Am aratat astfel ca S este o contractie ın spatiul metric (H(X), h). Notam cuA∗ ∈ H(X) punctul sau fix. Stim ca oricare ar fi A0 ∈ H(X) sirul aproximatiilor

succesive An = S◦n(A0) este convergent, ın metrica Hausdorff-Pompeiu, la A∗.Alegem o submultime initiala formata dintr-un singur element A0 = {a0} sirezulta imediat ca fiecare An are tot cate un singur element, si anume An ={S◦n(a0)}. Fie a ∈ A∗. Din caracterizarea limitei An → A∗ ın (H(X), h) rezultaca S◦n(a0) → a ın (X, d), de unde obtinem ca a este atractorul lui S iar A∗ ={a}. �

Am vazut asadar cum o contractie S pe X induce o contractie S pe H(X),

dar acest fapt nu are nimic spectaculos: atractorul lui S este o multime cu unsigur element: atractorul lui S. Situatia se va schimba ınsa radical cand vomconsidera mai multe contractii pe X.

Mai precis, vom considera un sistem finit de contractii S1, S2, . . . , Sk de la Xın X, cu ajutorul carora definim aplicatia

S : H(X) → H(X)

4

Page 5: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

prin

S(A) =k∪

i=1

Si(A), (6)

pentru orice A ∈ H(X), unde transformarile Si : H(X) → H(X) sunt cele indusede contractiile Si, i = 1, 2, . . . , k.

Teorema 4. Daca fiecare Si : X → X, cu i = 1, 2, . . . , k, este o contractie

cu constanta Lipschitz qi, atunci si aplicatia S : H(X) → H(X) definita de (6)este o contactie, avand constanta Lipschitz q = max{q1, q2, . . . , qk}. Mai mult,

atractorul A∗ al lui S satisface relatia

A∗ =∞∩n=0

S◦n(E), (7)

pentru orice E ∈ H(X) pentru care S(E) ⊂ E.

Atractorul contractiei S se mai numeste si atractorul sistemului de functii

iterate {Si | i = 1, 2, . . . , k}. Pentu a arata ca S este o contractie avem nevoie deurmatoarea lema:

Lema 1. Pentru orice A1, A2, B1 si B2 din H(X) are loc inegalitatea

h(A1 ∪ A2, B1 ∪B2) ≤ max{h(A1, B1), h(A2, B2)}.

Demonstratie. Fie A1, A2, B1 si B2 din H(X). Avem

e(A1 ∪ A2, B1 ∪B2) = supa∈A1∪A2

infb∈B1∪B2

d(a, b)

= max{ supa∈A1

infb∈B1∪B2

d(a, b), supa∈A2

infb∈B1∪B2

d(a, b)}

≤ max{ supa∈A1

infb∈B1

d(a, b), supa∈A2

infb∈B2

d(a, b)}

≤ max{h(A1, B1), h(A2, B2)},de unde rezulta imediat inegalitatea dorita. �

Pentru a demonstra prima afirmatie a Teoremei 4, vom considera doua ele-mente A si B din H(X) fixate arbitrar. Aplicand Lema 1 (extinsa pentru unnumar oarecare de multimi) si Teorema 3, obtinem

h(S(A), S(B)) = h(∪ki=1Si(A),∪k

i=1Si(B)) ≤ maxi

{h(Si(A), Si(B))}

≤ maxi

{qih(A,B)} ≤ qh(A,B).

5

Page 6: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

Din qi ∈ [0, 1) pentru i = 1, 2, . . . , k, rezulta q = max{q1, q2, . . . , qk} ∈ [0, 1),

si, prin urmare, S : H(X) → H(X) este o contractie. Exista astfel o singura

submultime compacta si nevida A∗ ⊂ X invarianta prin S, adica pentru care

S(A∗) = A∗.

Stim ca atractorul A∗ este limita ın metrica Hausdorff-Pompeiu a sirului

iteratelor (S◦n(E)), pentru orice multime initiala E ∈ H(X), vrem sa aratamacum ca aceasta limita poate fi ınlocuita cu intersectia din formula (7). Fie deci

E ∈ H(X) cu proprietatea S(E) ⊂ E (astfel de multimi exista, ın cel mai rau

caz E = A∗ are aceasta proprietate). Rezulta imediat ca S(S(E)) ⊂ S(E) si asa

mai departe, S◦(n+1)(E) ⊂ S◦n(E). Sirul (S◦n(E)) este un sir descrescator (ınsensul incluziunii) de multimi compacte nevide, deci si intersectia sa,

E =∞∩n=0

S◦n(E),

este compacta si nevida, adica din H(X). Tot din monotonia sirului (S◦n(E))urmeaza ca

S(E) = S(∞∩n=0

S◦n(E)) =∞∩n=0

S◦(n+1)(E) = E,

si, tinand cont de unicitatea punctului fix A∗, obtinem egalitatea E = A∗.Avem la dispozitie doua metode pentru a trasa atractorul unui sistem de

functii iterate, pe care le vom prezenta ın continuare presupunand, pentru sim-plificarea expunerii, ca sistemul {Si} este format numai din doua contractii, S1

si S2.Prima metoda se bazeaza pe aproximatia An = S◦n(A0) ≃ A∗ (care trebuie

ınteleasa sub forma: h(An, A∗) ≃ 0), valabila pentru n suficient de mare, unde

A0 ∈ H(X) poate fi aleasa arbitrar. Alegem o multime A0 formata dintr-unsingur element, A0 = {a}, si aplicand ın fiecare etapa toate transformarile Si,formam pe rand

A1 = S(A0) = {S1(a), S2(a)},A2 = S(A1) = {S1(S1(a)), S1(S2(a)), S2(S1(a)), S2(S2(a))},

adicaA2 = {Si1i2(a) | i1, i2 = 1, 2},

unde am notat Si1i2 = Si1 ◦ Si2 . In etapa a n-a vom avea

An = {Si1i2...in(a) | i1, i2, . . . , in = 1, 2}, (8)

cu Si1i2...in = Si1◦Si2◦· · ·◦Sin . Generarea sirului de multimi (An) poate fi stopatacand distanta Hausdorff-Pompeiu dintre doi termeni succesivi, h(An+1, An), estemai mica decat o precizie convenabil aleasa. In practica, deoarece numarul de

6

Page 7: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

elemente al lui An creste ın progresie geometrica, calculul este stopat numai dupacativa pasi, cand acest numar devine prea mare.

Aceasta metoda de aplicare iterativa a unui sistem de transformari geome-trice am folosit-o deja la generarea fractalilor prin motive iterate, de exemplupentru curba lui von Koch, curba lui Hilbert sau chiar la curba lui Takagi. Dacane asiguram ca transformarile folosite sunt contractii, atunci acesti fractali suntatractori ai unor sisteme de functii iterate si, ın acest caz, multimea initiala cucare pornim procesul iterativ poate fi aleasa la ıntamplare, figura finala fiindaceeasi.

Figura 1. Class VonKochIFS

De exemplu, urmatoarea clasa genereaza curba lui von Koch ca atractor aunui sistem de patru contractii iterate.

public class VonKochIFS : FractalForm {

Complex i = Complex.setRoTheta(1.0, Math.PI / 2.0);

Complex omega = Complex.setRoTheta(1 / 3.0, Math.PI / 3.0);

Complex S1(Complex z){

return z / 3.0;

}

Complex S2(Complex z){

return 1 / 3.0 + omega * z;

7

Page 8: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

}

Complex S3(Complex z){

return 2 / 3.0 + omega.conj * (z - 1);

}

Complex S4(Complex z){

return 2 / 3.0 + z / 3.0;

}

void transforma(ref ComList li){

ComList rez = new ComList();

Complex z;

for (z = li.firstZet; !li.ended; z = li.nextZet){

rez.nextZet = S1(z);

rez.nextZet = S2(z);

rez.nextZet = S3(z);

rez.nextZet = S4(z);

}

li = rez;

}

void picteaza(ComList li){

initScreen();

Complex z;

for (z = li.firstZet; !li.ended; z = li.nextZet){

setPixel(z, PenColor);

}

}

public override void makeImage()

{

setXminXmaxYminYmax(-0.1, 1.1, -0.3, 0.9);

ScreenColor = Color.White;

ComList fig = new ComList();

//figura initiala

fig.nextZet = 2 + 3 * i;

int nrEtape = 7;

for (int n = 0; n < nrEtape; n++)

{

transforma(ref fig);

picteaza(fig);

if (!resetScreen()) return;

delaySec(0.5);

}

initScreen();

for (Complex z = fig.firstZet; !fig.ended; z = fig.nextZet)

{

setPixel(S1(z), Color.Red);

setPixel(S2(z), Color.Yellow);

8

Page 9: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

setPixel(S3(z), Color.Green);

setPixel(S4(z), Color.Blue);

}

resetScreen();

}

}

Rezultatul este aratat ın Figura 1.A doua metoda de trasare a atractorului unui sistem de functii iterate consta ın

urmatoarele: alegem un punct initial a ∈ X arbitrar caruia ıi aplicam pe rand cateuna din transformarile Si aleasa aleator ın mod uniform (de exemplu). Obtinem unsir de puncte (an) din X dat de relatia

an = Si1i2...in(a),

unde i1, i2, . . . , in au valori aleatoare ın multimea de indici, cu probabilitati egale.Din relatia (8) rezulta ca an ∈ An pentru orice n, si prin urmare

0 ≤ d(an, A∗) ≤ h(An, A

∗) → 0 pentru n → ∞.

Am aratat astfel ca, pentru n suficient de mare, an apartine practic atractorului A∗.Se poate arata ca, datorita modului de alegere a transformarilor Si, sirul (an) estedistribuit, pentru n → ∞, ın mod uniform ın vecinatatea atractorului. Practic, dupace generam “ın gol” primii 1000 (sa zicem) de termeni ai sirului (an), ıncepem sa ıiafisam pe urmatorii 10000, de exemplu. Figura obtinuta este o aproximatie destul debuna atractorului.

Ca exemplificare, reluam generarea, prin aceasta metoda, a curbei lui von Koch.

public class VonKochIFSRandom : FractalForm

{

Complex i = Complex.setRoTheta(1.0, Math.PI / 2.0);

Complex omega = Complex.setRoTheta(1 / 3.0, Math.PI / 3.0);

Random zar = new Random();

Complex S1(Complex z){

return z / 3.0;

}

Complex S2(Complex z){

return 1 / 3.0 + omega * z;

}

Complex S3(Complex z){

return 2 / 3.0 + omega.conj * (z - 1);

}

Complex S4(Complex z){

return 2 / 3.0 + z / 3.0;

}

Complex R(Complex z){

switch (zar.Next(4)){

case 0: return S1(z);

case 1: return S2(z);

9

Page 10: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

case 2: return S3(z);

default: return S4(z);

}

}

public override void makeImage() {

setXminXmaxYminYmax(-0.1, 1.1, -0.3, 0.9);

ScreenColor = Color.White;

initScreen();

Complex z = 20 + 30 * i;

for (int n = 0; n <= 1000000; n++){

z = R(z);

if (n <= 1000) continue;

setPixel(z, getColor(n));

if (n % 100 == 0) resetScreen();

}

}

}

Rezultatul este asemanator cu cel anterior, dar metoda utilizata acum nu maipresupune ocuparea unui volum imens de memorie.

Figura 2. Class VonKochIFSRandom

10

Page 11: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

Un exemplu celebru de atractor al unui sistem de functii iterate este Feriga luiBarnsley, generata de patru transformari afine ale planului. Acest exemplu a fostprezentat de Michael Barnsley cartea sa, Fractals Everywhere, una dintre cele maipopulare lucrari despre fractali. Cu numere complexe, implementarea ar fi urmatoarea:

public class Barnsley : FractalForm {

Complex i = Complex.setRoTheta(1.0, Math.PI / 2.0);

Random nrand = new Random();

Complex S1(Complex z){

double x = z.Re, y = z.Im;

return new Complex(0 * x + 0 * y + 0,

0 * x + 0.2 * y + 0);

}

Complex S2(Complex z){

double x = z.Re, y = z.Im;

return new Complex(0.85 * x + 0.05 * y + 0,

-0.04 * x + 0.85 * y + 1.6);

}

Complex S3(Complex z){

double x = z.Re, y = z.Im;

return new Complex(0.2 * x - 0.26 * y + 0,

0.23 * x + 0.22 * y + 1.6);

}

Complex S4(Complex z){

double x = z.Re, y = z.Im;

return new Complex(-0.15 * x + 0.28 * y + 0,

0.26 * x + 0.24 * y + 0.44);

}

Complex R(Complex z){

double rnd = nrand.NextDouble();

if (rnd < 0.05) return S1(z);

if (rnd < 0.86) return S2(z);

if (rnd < 0.93) return S3(z);

return S4(z);

}

public override void makeImage(){

setXminXmaxYminYmax(-5, 5, 0, 10);

initScreen();

Complex z = 20 + 30 * i;

for (int n = 0; n <= 1000000; n++) {

z = R(z);

if (n <= 1000) continue;

setPixel(z, getColor(575+n%150));

if (n % 100 == 0) resetScreen();

}

11

Page 12: Fractali generat¸i de sisteme de funct¸ii iteratenecula/down_files/fractali2017/curs_09_ifs... · Cursul 9 Fractali generat¸i de sisteme de funct¸ii iterate Vom prezentaˆın

}

}

Rezultatul este aratat ın Figura 3.Remarcam ca ın exemplul precedent probabilitatile de alegere a transformarilor Si

nu mai sunt egale. Stim ca atractorul A∗ verifica egalitatea:

A∗ = S1(A∗) ∪ S2(A

∗) ∪ S3(A∗) ∪ S4(A

∗).

Dupa fiecare salt, ın functie de transformarea aleasa, punctul curent se va gasi ıntr-oanumita regiune S1(A

∗), S2(A∗), S3(A

∗) sau S4(A∗), si este firesc ca probabilitatea

de a sari ıntr-o astfel de regiune sa fie proportionala cu aria acesteia. Acest mod dealegere optimizeaza viteza de umplere a atractorului, metoda functionand totusi, mailent, si cu probabilitati egale.

Interpretarile geometrice sunt urmatoarele: numarand de jos ın sus, S4(A∗) este

prima frunza de pe partea dreapta, S3(A∗) este prima frunza din stanga, S2(A

∗) estetoata feriga mai putin aceste doua frunze, iar S1(A

∗) este codita de ınceput a ferigii(pana la prima frunza din dreapta).

Figura 3. Class Barnsley

12