Triangle de Sierpiński

El Triangle de Sierpiński és un conjunt fractal descrit per primer cop per Wacław Sierpiński el 1915. Es defineix de forma recursiva seguint l’algorisme següent:

1. A partir d’un triangle, s’uneixen els punts mitjans dels seus costats, dividint el triangle inicial en quatre altres triangles.

2. S’elimina el triangle interior.

3. Es repeteixen els passos anteriors per cadascun dels tres triangles que queden.

El triangle de Sierpiński és el límit de fer el procediment anterior de manera infinita.

Volem fer una funció que calculi el triangle de Sierpiński, fins a un cert nivell d’aproximació. Direm que el triangle de Sierpiński de nivell n és el resultat fer n passos de la recursió, és a dir, d’aplicar n vegades la divisió recursiva dels triangles en quatre. Així, els triangles de la figura són els de nivell n = 0, 1, 2, 3 i 4.

En el mòdul sierpinski.py dissenyeu la funció recursiva:

sierpinski.sierpinski(t, n)

Retorna la llista de triangles en què queda dividit el triangle de Sierpiński de nivell n, partint d’un triangle equilàter t. A tal efecte, representarem un triangle com una tupla de tres punts del pla; i un punt del pla com una tupla amb dues coordenades reals. Com exemple, podeu començar amb el triangle equilàter format pels 3 vèrtexs següents: (0,1000), (-866,-500), (866,-500).

Per a comprovar que heu realitzat bé els càlculs, podeu dibuixar els triangles obtinguts utilitzant pylab/matplotlib. Facilitem la funció dibuixa() que podeu trobar al fitxer dibuixa_sierpinski.py que permet dibuixar un iterable de triangles. També facilitem aquest fitxer amb diversos tests test-sierpinski.txt

Avís

Aneu amb compte a l’hora de fer el càlcul d’un triangle de Sierpiński de nivell n, ja que està compost per \(3^n\) petits triangles!

Solució

Disposeu d’una solució al fitxer sierpinski.py.