Catifa de Sierpiński

../../../_images/Catifa_sierpinski.png

La Catifa de Sierpiński és un conjunt fractal descrit per primer cop per Wacław Sierpiński el 1916. Es defineix de forma recursiva:

  1. Comencem amb un quadrat.

  2. El quadrat es subdivideix en 9 quadrats més petits, tots de la mateixa mida, i eliminem el quadrat central.

  3. Es repeteix el pas anterior recursivament per cadascún dels 8 quadrats restants.

La catifa de Sierpiński és el límit d’aquest procés després d’un nombre infinit d’iteracions. Per a representar-la gràficament a la pràctica s’aproxima amb un nombre petit d’iteracions.

Representarem un quadrat com una instància de la classe Quadrat, la qual usa la classe Punt2D. Per tant caldrà disposar de les seves implementacions que són als fitxers quadrat.py i punt2D.py, respectivament. Estudieu l’especificació d’aquestes classes que bàsicament necessitareu per crear-ne instàncies.

En el mòdul catifa (fitxer catifa.py) dissenyeu les dues funcions següents:

catifa.subdivideix(quadrat)

Donat un quadrat (instància de la classe Quadrat) retorna un conjunt (set) amb els 8 quadrats (8 instàncies de la classe Quadrat) en què es subdivideix segons el mètode de la catifa de Sierpiński.

Exemple:

>>> q1 = Quadrat(Punt2D(0.0, 0.0), 2187.0)
>>> sq = subdivideix(q1)
>>> for q in sorted(sq):
...    print(q)
Quadrat(Punt2D(0.0, 0.0), 729.0)
Quadrat(Punt2D(0.0, 729.0), 729.0)
Quadrat(Punt2D(0.0, 1458.0), 729.0)
Quadrat(Punt2D(729.0, 0.0), 729.0)
Quadrat(Punt2D(729.0, 1458.0), 729.0)
Quadrat(Punt2D(1458.0, 0.0), 729.0)
Quadrat(Punt2D(1458.0, 729.0), 729.0)
Quadrat(Punt2D(1458.0, 1458.0), 729.0)

Nota

Disposeu de jocs de proves al fitxer test-subdivideix.txt.

catifa.catifa(quadrat, n)

Funció recursiva que donat un quadrat (instància de la classe Quadrat), retorna un conjunt (set) amb els quadrats (instàncies de la classe Quadrat) en què queda subdividit el quadrat inicial fins al nivell n, és a dir, aplicant n vegades la definició recursiva de la catifa de Sierpiński: si el paràmetre n val 0, aquesta funció ha de retornar un conjunt amb un sol quadrat (l’original); si n val 1, ha retornar un conjunt amb 8 quadrats; etc.

Aquesta funció ha de cridar a la funcio subdivideix().

Per a comprovar que heu realitzat bé els càlculs, podeu usar la funció dibuixa() (fitxer dibuixa_catifa.py) que permet dibuixar un iterable de quadrats usant la biblioteca pylab/matplotlib. També facilitem el fitxer test-catifa.txt on hi ha les crides a la funció catifa() i a la funció dibuixa() per diversos valors de n:

>>> qi = Quadrat(Punt2D(0.0, 0.0), 2187.0)

>>> sq = catifa(qi, 0)
>>> len(sq)
1
>>> dibuixa(sq)

>>> sq = catifa(qi, 1)
>>> len(sq)
8

Avís

Aneu amb compte a l’hora de fer el càlcul d’una catifa de Sierpiński de nivell n, ja que està composta per \(8^n\) quadrats !

La classe Quadrat conté dos mètodes més que són necessaris per la funció dibuixa() i pels tests que es faciliten. No són necessaris per dissenyar les funcions que es demanen.

Solució

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