Desenarea fractalilor

Fractalii (ro, en) sunt figuri geometrice la care o parte este similară întregului. Astfel, fractalii pot fi desenaţi înlocuind succesiv într-o figură iniţială o parte simplă (un segment) cu o copie micşorată a întregii figuri. Acest procedeu poate fi definit riguros prin reguli de rescriere care formează o gramatică, obţinându-se aşa-zisele L-sisteme.

Vom desena fractalul dragon. Acesta poate fi descris cu ajutorul a două părţi numite X şi Y, rescrise la fiecare pas după regulile:

X -> X+YF
Y -> FX-Y

unde F reprezintă un segment înainte, + şi - rotiri de 90 de grade la stânga şi respectiv dreapta. Desenarea porneşte de la secvenţa iniţială FX. În desenul final, după repetarea dorită a regulilor de rescriere, X şi Y se ignoră.

Rezolvăm problema în paşi, scriind funcţii cât mai simple pentru părţile componente, şi ne preocupăm doar la sfârşit de detaliile de implementare a desenării (care poate fi făcută în multe feluri).

Scriem programul în dialectul OCaml al limbajului ML, dar principiile pe care le urmăm sunt valabile independent de limbaj.

Întâi implementăm regulile de rescriere, definind o funcţie care transformă fiecare simbol (caracter) într-o listă de simboluri. Caracterele '+', '-' şi 'F' nu se transformă, deci rezultatul e o listă cu un singur element, chiar caracterul respectiv.

let transf c =
  if c = 'x' then ['x';'+';'y';'f']
  else if c = 'y' then ['f';'x';'-';'y']
  else [c]

Folosim o listă pentru şirul simbolurilor de desenat. Lista e transformată aplicând individual funcţia transf fiecărui element. Aceasta se poate face cu funcţia predefinită List.map care are două argumente: funcţia de aplicat şi lista de prelucrat. Aplicând de exemplu List.map transf ['f';'x'] obţinem şirul după primul pas de transformare: [['f']; ['x'; '+'; 'y'; 'f']] Remarcăm însă că aceasta este o listă având ca elemente alte liste (două în acest caz). Folosim funcţia List.concat care concatenează toate elementele dintr-o listă de liste într-o listă (pe un singur nivel). Astfel, putem defini un pas de prelucrare:

let step lst = List.concat (List.map transf lst)

(Această prelucrare este simplă dar nu prea eficientă, concatenarea parcurgând rezultatul parţial în mod repetat. Gândiţi-vă la o implementare mai bună).

Va trebui să aplicăm această funcţie de n ori (cu n dat), pentru a obţine lista de simboluri care defineşte desenarea dragonului. Definim recursiv aplicarea unei funcţii de n ori, ţinând cont că f⁰(x) = x şi fⁿ(x) = f^n-1(f(x)) pentru n > 0. Scriem atunci:

let rec powf f n x = if n = 0 then x else powf f (n-1) (f x)

şi putem testa, de exemplu:

let inc2 x = x + 2
powf inc2 5 3 = 13  (* 3 incrementat cu 2 de 5 ori*)

sau puteam scrie şi direct: powf ((+) 1) 5 3 unde (+) 2 este funcţia care adună 2 la argument.
În cazul nostru, de exemplu powf step 2 ['f';'x'] = ['f';'x';'+';'y';'f';'+';'f';'x';'-';'y';'f']

Ca rezultat după n paşi avem deci şirul

let evolve n = powf step n ['f';'x']

Ne punem acum problema desenării efective. Pentru simplitate, alegem să scriem prelucrările pentru desenat într-un fişier SVG (Scalable Vector Graphics) pentru a putea fi vizualizat ulterior. Pentru aceasta, producem o secvenţă de comenzi h şi v care desenează un segment orizontal şi respectiv vertical de dimensiune dată. De exemplu, "h 5 v -3" înseamnă desenarea din punctul curent al unui segment de 5 unităţi la dreapta şi apoi 3 unităţi în jos. Cum desenarea fractalului nostru implică rotirea cursorului, e necesar să reţinem poziţia lui, şi implementăm funcţii de rotire:

let dir = ref 0
let minus() = dir := (!dir + 1) mod 4
let plus() = dir := (!dir + 3) mod 4

Prima linie declară dir ca fiind o variabilă (o valoare modificabilă); iar celelalte două funcţii actualizează valoarea ei (care reprezintă unghiul fată de axa x în multipli de 90 de grade). Sintaxa !dir reprezintă valoarea lui dir, iar := e atribuirea. Nişte calcule simple arată că un avans înainte de lungime len se scrie cu operaţiile de avans orizontal sau vertical astfel:

let f len = if !dir mod 2 = 0
  then (print_string " h "; print_int (len * (1 - !dir)))
  else (print_string " v "; print_int (len * (2 - !dir)))

În final, desenarea unui simbol ('+', '-' sau 'F') din listă se scrie (alegând lungimea segmentului de 8 unităţi):

let draw_elt c =
  if c = 'f' then f 8
  else if c = '-' then minus()
  else if c = '+' then plus()

let draw_list n = List.iter draw_elt (evolve n)

şi apelul draw_list 10 ne va produce comenzile pentru desenarea unui dragon cu 10 nivele de detaliere. Comenzile rezultate pot fi inserate în structura unui fişier SVG, de exemplu:

<?xml version="1.0" encoding="UTF-8" standalone="no">
<svg
   xmlns:svg="http://www.w3.org/2000/svg"
   xmlns="http://www.w3.org/2000/svg"
   version="1.0"
   width="400"
   height="800"
   id="svg001">
  <defs
     id="defs001"/>
  <path
     d="M 200 400 h 8 v -8 ... RESTUL COMENZILOR ... h -8 v -8"
     style="fill:none;stroke:#0000ff;stroke-width:2px"
     id="path001"/>
</svg>

rezultând imaginea dorită.

În rezumat:

am descompus problema în subprobleme mai mici: prelucrarea unui simbol; prelucrarea listei de simboluri; repetarea prelucrării, etc., scriind pentru fiecare parte funcţii, separând cât mai mult părţile independente între ele (de exempliu, modul de prelucrare al unui simbol e independent de parcurgerea listei de simboluri)
am scris funcţii cât mai generale (de exemplu, cea care aplică o funcţie de n ori)
am folosit cât mai mult funcţiile de bibliotecă existente (de exemplu, pentru lucrul cu liste)
am izolat accesul la detaliile de implementare la un număr redus de funcţii (exemplu, funcţiile minus, plus şi f care folosesc direcţia curentă)
am păstrat independenţa logicii programului (generarea mutărilor) de modul de reprezentare (desenarea propriu-zisă)

Acestea sunt principii generale. Respectarea lor ne ajută să programăm bine şi frumos: să scriem programe corecte, uşor de înţeles, de adaptat şi întreţinut, oricare ar fi limbajul pe care îl alegem.

Marius Minea

Last modified: Mon Oct 4 15:0:00 EET 2010