La Corba C de Lévy

La Corba C de Lévy és una corba fractal auto-similar que té una forma que recorda una lletra C molt ornamentada. Es pot construir de forma recursiva seguint l’algorisme següent:

  1. A partir d’un segment rectilini, es pren el punt del centre i es desplaça perpendicularment una distància igual a la meitat de la longitud del segment.

  2. S’uneixen els tres punts, formant dos nous segments.

  3. Es repeteixen el passos anteriors en cadascún del dos segments.

La Corba C de lévy és el límit de fer el procediment anterior de manera infinita.

Volem fer una funció que calculi la Corba C de Lévy, fins a un cert nivell d’aproximació. Direm que la Corba C de Lévy de nivell n és el resultat fer n passos de la recursió, és a dir, d’aplicar n vegades la divisió recursiva d’un segment en dos altres. Es tracta, per tant, de corbes poligonals. La figura adjunta correspon a les corbes C de Lévy dels nivells n=0 fins a n=7.

../../../_images/corba_c_levy.png

Representarem un punt del pla com una tupla amb les seves dues coordenades cartesianes. Una poligonal es representa per tant com una llista de punts. Per a comprovar que realitzeu bé els càlculs, podeu dibuixar una poligonal utilitzant pylab/matplotlib. Facilitem la funció dibuixa_poligonal() que podeu trobar al fitxer dibuixa_pol.py, que permet dibuixar una poligonal qualsevol.

  1. En el mòdul levy (fitxer levy.py), dissenyeu-hi la funció recursiva:

    levy.divideix_levy(llistap)

    Donada una llista de punts que representa una poligonal, retorna una nova llista de punts dividida afegint un punt enmig de cada segment. Els nous punts s’obtenen segons la divisió per a obtenir una corba C de Lévy (pas 1 de l’algorisme).

    Fixeu-vos que la si la llista passada com a paràmetre té n punts, la llista retornada per aquesta funció n’ha de tenir 2n-1. Per a calcular el punt que cal inserir en la subdivisió d’un segment, podeu utilitzar el següent mètode:

    Siguin \(p = (p_x, p_x)\) i \(q = (q_x, q_y)\) els extrems d’un segment de recta. Les coordenades del nou punt \(r = (r_x, r_y)\) de divisió segons l’algorisme indicat són

    \begin{eqnarray} r_x & = & (p_x + q_x + p_y - q_y) / 2 \\ r_y & = & (p_y + q_y + q_x - p_x) / 2 \end{eqnarray}

    Per exemple,

    >>> divideix_levy([(1.0,2.0), (7.0,4.0)])
[(1.0, 2.0), (3.0, 6.0), (7.0, 4.0)]
>>> divideix_levy([(0.0,0.0), (0.0,4.0), (6.0,4.0), (6.0,-2.0)])
[(0.0, 0.0), (-2.0, 2.0), (0.0, 4.0), (3.0, 7.0), (6.0, 4.0), (9.0, 1.0), (6.0, -2.0)]

    Disposeu de jocs de prova al fitxer test-divlevy.txt.

  2. En el mateix mòdul levy (fitxer levy.py), dissenyeu-hi la funció recursiva:

    levy.corba_levy(lpunts, n)

    Donada una llista amb dos punts (un segment de recta) i un enter positiu n, retorna la poligonal (una llista de punts) corresponent a la corba C de Lévy de nivell n.

    Per exemple,

    >>> corba_levy([(0.0,0.0), (10.0, 0.0)], 0)
[(0.0, 0.0), (10.0, 0.0)]
>>> corba_levy([(2.0,0.0), (10.0, 0.0)], 2)
[(2.0, 0.0), (2.0, 4.0), (6.0, 4.0), (10.0, 4.0), (10.0, 0.0)]
>>> corba_levy([(0.0,5.0), (10.0, 5.0)], 4)
[(0.0, 5.0), (-2.5, 5.0), (-2.5, 7.5), (-2.5, 10.0), (0.0, 10.0), (0.0, 12.5), (2.5, 12.5), (5.0, 12.5), (5.0, 10.0), (5.0, 12.5), (7.5, 12.5), (10.0, 12.5), (10.0, 10.0), (12.5, 10.0), (12.5, 7.5), (12.5, 5.0), (10.0, 5.0)]

    Disposeu de jocs de prova al fitxer test-corbalevy.txt.

    Avís

    Aneu amb compte a l’hora de fer el càlcul d’una corba C de Lévy de nivell n, ja que està composta per \(2^n\) segments!

Solució

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