11 de julio de 2013

La curva de dragón: el fractal de Parque Jurásico

Hace precisamente 20 años, en 1993, se estrenó a nivel mundial la película “Parque Jurásico”. Esta cinta de ciencia ficción, dirigida por Steven Spielberg, trata sobre el colapso de un parque temático ubicado en una remota isla de Costa Rica, cuyas atracciones principales eran dinosaurios genéticamente reconstruidos. La cinta está basada en una novela del mismo nombre, escrita por Michael Crichton y publicada en 1990.

Personalmente me encanta la película, sin embargo, por trillado que suene, soy de la opinión que la novela es aún mucho mejor.

John Michael Crichton,
autor del libro “Parque Jurásico”.

El grueso de la novela se divide en siete secciones que el autor llama “iteraciones”. Justo al inicio de cada una de estas iteraciones viene un dibujo junto con una cita atribuida al Dr. Ian Malcolm, uno de los personaje centrales de la novela. Por ejemplo:


Ian Malcolm es un matemático, experto en teoría del caos. Durante el transcurso de la historia, Malcolm hace varias predicciones basadas en esta teoría sobre las consecuencias negativas que podrían ocurrir al momento de intentar controlar la naturaleza. Lamentablemente, dichas predicciones resultan ser acertadas.

La figura que se muestra al inicio de cada iteración es un fractal conocido como “curva de dragón” o “dragón de Heighway”. Gracias a su aparición en la novela de Crichton, también se le conoce hoy en día como “fractal de Parque Jurásico”. John Heighway, Bruce Banks y William Harter, físicos de la NASA, fueron los primeros en investigar sobre este fractal a mediados de los años sesenta.

En la novela, Malcolm utiliza las curvas de dragón como una manera de simular las acciones “caóticas” que sucederían dentro del parque. Las siguientes dos imágenes muestran las curvas de dragón de la cuarta y séptima iteración, respectivamente. En la segunda figura podemos ver que el fractal tiene una apariencia similar a lo que podría ser un dragón. De ahí es donde toma su nombre.



La teoría del caos en esencia establece que pequeñas variaciones en las condiciones iniciales de un sistema dinámico pueden implicar grandes diferencias en su comportamiento futuro. El ejemplo clásico es:  “el aleteo de las alas de una mariposa puede provocar un Tsunami al otro lado del mundo”. La curva de dragón no tiene realmente que ver con esto, ya que puede ser producida de manera totalmente predecible a través de un algoritmo. Sin embargo, eso no hace que este fractal sea menos interesante.

En las siguientes secciones veremos dos maneras de generar la curva de dragón.

Construyendo la curva de dragón con papel

Tomamos una hoja tamaño carta y cortamos una tira por la parte larga de la hoja. La tira puede ser de unos 2 o 3 centímetros de ancho.


Paso 1: Doblar la tira a la mitad, tomando el extremo izquierdo y doblando hacia la derecha. La tira queda dividida en dos partes iguales. Todos los dobleces en lo sucesivo se deben hacer en este mismo sentido.


Paso 2: Si desdoblamos la tira y nos aseguramos que el doblez quede en un ángulo recto, obtenemos la siguiente figura que es una curva de dragón de orden 1:


Paso 3: Volvemos a doblar la tira en dos como estaba al final del paso 1, y hacemos un nuevo doblez a la mitad, otra vez tomando el extremo izquierdo y doblando hacia la derecha. La tira queda dividida en cuatro partes iguales:


Paso 4: Al desdoblar la tira, cuidando que todos los dobleces queden como ángulos rectos, tenemos ahora una curva de dragón de orden 2:


Vale la pena notar que la misma figura del paso 2 aparece aquí dos veces. La segunda vez aparece rotada 90° del punto en donde termina la primera.

Paso 5: Volvemos a doblar la tira como estaba hasta el paso 3 y hacemos otro doblez a la mitad. La tira queda ahora dividida en ocho partes iguales:


Paso 6: Al desdoblar la tira tenemos un curva de dragón de orden 3:


Notar aquí también que la figura del paso 4 se repite dos veces. Igualmente, la segunda instancia aparece rotada 90°.

Paso 7: Nuevamente regresamos a los dobleces del paso 5, y hacemos otro doblez por la mitad. Ahora la tira queda dividida en dieciséis partes iguales:


Paso 8: Desdoblamos la tira por última vez y nos queda una curva de dragón de orden 4, la cual es simétrica al dibujo de la primera iteración de la novela de “Parque Jurásico”:


Ahora es la figura del paso 6 la que se repite dos veces. La segunda figura también está rotada en un ángulo recto.

Todo este proceso se puede repetir en teoría un número infinito de veces. Sin embargo existe un límite físico respecto al número de dobleces que se le pueden realizar a una tira de papel. La buena noticia es que tenemos menos límites al momento de programar nuestra computadora.

Programando la curva del dragón en Python

Podemos usar gráficas de tortuga para dibujar la curva del dragón. Hay varias formas de realizar la implementación, pero una manera sencilla de hacerlo es calcular primero todos los giros que tiene que hacer la tortuga antes de comenzar a dibujar.

El algoritmo consiste en producir una cadena de letras I y D, donde I representa un giro de 90° a la izquierda y D un giro de 90° a la derecha. El pseudocódigo del algoritmo recursivo quedaría así:
  • Para una curva de orden 0, el resultado es una cadena vacía, ya que no se requiere hacer giro alguno.
  • Para una curva de cualquier otro orden n, donde n > 0:
    • Sea c la cadena de la curva de dragón de orden n – 1.
    • Sea r la cadena en reversa de c.
    • Sea i la cadena formada por los elementos de r, pero invirtiendo cada I por D y cada D por I.
    • El resultado consiste en concatenar los siguientes tres elementos: c, I, i.
La traducción directa a Python 3.x se muestra a continuación. Por simplicidad se usan listas de caracteres para representar las diversas cadenas que aparecen en el pseudocódigo en lugar de utilizar strings.
def curva(n):
    """Devuelve una lista de caracteres con los giros
       requeridos para dibujar la curva de dragón de orden
       n. La letra 'I' significa girar a la izquierda, 
       mientras que la letra 'D' significa girar a la 
       derecha.
    """
    if n == 0:
        return []
    else:
        c = curva(n - 1)
        r = c[::-1]
        i = ['I' if g == 'D' else 'D' for g in r]
        return c + ['I'] + i
El siguiente código usa la función curva() para mostrar los giros requeridos con el fin de dibujar las curvas de dragón de órdenes 0 al 5:
for i in range(6):
    print('orden {0}: {1}'.format(i, ''.join(curva(i))))
La salida sería:
orden 0:
orden 1: I
orden 2: IID
orden 3: IIDIIDD
orden 4: IIDIIDDIIIDDIDD
orden 5: IIDIIDDIIIDDIDDIIIDIIDDDIIDDIDD
Una vez que tenemos los giros necesarios para la curva de dragón resulta muy directo el mecanismo para realizar el dibujo usando gráficas de tortuga:
  • Mover la tortuga hacia adelante x pixeles.
  • Por cada elemento g en la lista de giros de la curva de dragón de orden n, hacer lo siguiente:
    • Si g es I, girar la tortuga 90° a la izquierda.  
    • Si g es D, girar la tortuga 90° a la derecha.
    • Mover la tortuga hacia adelante x pixeles.
El código correspondiente en Python queda así:
from turtle import *

def dragon(n, x):
    """Dibuja una curva de dragón de orden n en donde
       cada segmento de la curva es de longitud x.
    """
    fd(x)
    for g in curva(n):
        if g == 'I':
            lt(90)
        else: # g == 'D'
            rt(90)
        fd(x)
Agregando un poco de código para inicializar la tortuga de manera conveniente, ya tenemos un programa que dibuja una curva de dragón de orden 8:
hideturtle()       
pensize(3)         
color('SteelBlue')
speed('fastest')   
setheading(180)    
dragon(8, 15)      
done()
Se puede observar que el dibujo resultante es idéntico al que aparece como cuarta iteración de la novela de Crichton.

dragon(8, 15)

Algunos otros ejemplos variando los valores de n (orden) y x (longitud) de la curva:

dragon(0, 200)

dragon(4, 50)

dragon(11, 5)

dragon(16, 1)

En la última figura el tamaño de la pluma utilizada (establecida con la función pensize()) es 1 en lugar de 3.


Referencias

No hay comentarios.:

Publicar un comentario