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

4 de julio de 2013

La sección de oro

Introducción

“Donald en el País de las Matemágicas” (Walt Disney Productions, 1959) es un corto animado que dura 27 minutos y muestra de manera entretenida el papel que juegan las matemáticas en el mundo real. En México, dicho corto se puede encontrar en el DVD titulado “Fábulas de Disney, Volumen tres”.


El corto completo también está disponible en YouTube con doblaje en español latinoamericano. Una de las partes que más me gusta es la referente a la explicación de la sección de oro (conocida también como número áureo, razón áurea, razón dorada, media áurea, proporción áurea y divina proporción, entre otros). Invito al lector a que vea el video; estoy seguro que le resultará muy interesante. A mi me gusta ponérselos a mis alumnos antes de introducir el tema de gráficas de tortuga.



Calculando \(\varphi\) de manera algebraica

La sección de oro, representada por la letra griega \(\varphi\) (fi), es un número irracional (esto quiere decir que no se puede escribir como una fracción). Se obtiene dividiendo una línea en dos partes, una larga y otra corta, de manera que la parte larga dividida entre la corta es igual al total de toda la línea dividido entre la parte larga. Gráficamente se puede expresar de la siguiente forma:


Toda la línea mide una unidad. Las dos partes de la línea son (x) y (1 - x), que corresponden a la parte larga y corta respectivamente. Por tanto, la sección de oro se puede expresar usando la ecuación (1): \begin{equation} \varphi = \frac{1}{x} = \frac{x}{1-x} \tag{1} \end{equation} \begin{equation} 1(1 - x) = x(x) \end{equation} \begin{equation} 1 - x = x ^ 2 \end{equation} \begin{equation} x ^ 2 + x - 1 = 0 \tag{2} \end{equation} Usando simples despejes algebraicos, la razón de la ecuación (1) se puede transformar hasta llegar a (2). Para encontrar el valor de x a partir de la ecuación cuadrática (3) se puede usar la fórmula general (4) (conocida también coloquialmente en México como “la fórmula del chicharronero”, ya que hasta el señor que vende chicharrones la conoce). \begin{equation} a x ^ 2 + b x + c = 0 \tag{3} \end{equation} \begin{equation} x = \frac{-b + \sqrt{b^2 - 4ac}}{2a} \tag{4} \end{equation} A partir de (2), tenemos que a = 1, b = 1 y c = –1. Haciendo las sustituciones correspondientes en (4), se puede determinar finalmente en (5) el valor de \(\varphi\) según su definición en (1). \begin{equation} x = \frac{-(1) + \sqrt{(1)^2 - 4(1)(-1)}}{2(1)} \end{equation} \begin{equation} x = \frac{-1 + \sqrt{1 + 4}}{2} \end{equation} \begin{equation} x = \frac{\sqrt{5}-1}{2} \end{equation} \begin{equation} \varphi = \frac{1}{x} = \frac{2}{\sqrt{5}-1} = 1.61803398874989484820\ldots \tag{5} \end{equation}

Usando números de Fibonacci para calcular \(\varphi\)

Otra forma de calcular la sección de oro es utilizando los números de Fibonacci. Se puede obtener una aproximación de \(\varphi\) al dividir fib(n) entre fib(n-1), para n > 1. Entre mayor sea el valor de n, mejor será la aproximación de \(\varphi\). Poniendo esto en código de Python para n = 100 tenemos:
def fib(n):
    a = 1
    b = 0
    for i in range(n):
        a, b = b, a + b
    return b

def fi(n):
    return fib(n) / fib(n - 1)

print('\N{Mathematical Italic Small Phi} =', fi(100))
NOTA: Todo el código de Python presentado en este artículo requiere Python 3.x.

La salida producida es:
𝜑 = 1.618033988749895
El resultado es exactamente el esperado hasta el decimocuarto dígito después del punto decimal.

Usando \(\varphi\) para calcular los números de Fibonacci

También es posible calcular el elemento n-ésimo de la sucesión de Fibonacci utilizando la razón áurea \(\varphi\) a partir de la siguiente fórmula:
\begin{equation} \textrm{fib} (n) = \frac{\varphi^n - (1 - \varphi)^n}{\sqrt{5}} \end{equation} Podemos verificar que dicha fórmula produce los valores correctos corriendo el siguiente programa:
from math import sqrt

fi = 1.618033988749895

def fib(n):
    return (fi ** n - (1 - fi) ** n) / sqrt(5)

for i in range(16):
    print("fib({0}) = {1}".format(i, fib(i)))
Esta es la salida correspondiente:
fib(0) = 0.0
fib(1) = 1.0
fib(2) = 1.0
fib(3) = 2.0
fib(4) = 3.0000000000000004
fib(5) = 5.000000000000001
fib(6) = 8.000000000000002
fib(7) = 13.000000000000002
fib(8) = 21.000000000000004
fib(9) = 34.00000000000001
fib(10) = 55.000000000000014
fib(11) = 89.00000000000003
fib(12) = 144.00000000000006
fib(13) = 233.00000000000006
fib(14) = 377.00000000000017
fib(15) = 610.0000000000003
Podemos notar algunos pequeños errores asociados a la perdida de precisión en los dígitos posteriores al punto decimal. Esto es inherente al uso de números de punto flotante. Aún así, los resultados son bastante próximos a los valores esperados.

La espiral dorada

La espiral dorada (también conocida como espiral áurea) es una espiral logarítmica cuyo factor de crecimiento es \(\varphi\). Resulta relativamente sencillo dibujar dicha espiral usando Python y gráficas de tortuga. El truco consiste en saber cómo dibujar un arco. El módulo turtle de Python tiene una función llamada circle() que recibe dos argumentos (realmente son tres, pero podemos ignorar el tercer argumento): un radio R (en pixeles) y un ángulo θ (en grados). La siguiente imagen muestra la manera de interpretar los argumentos de la función circle():


Si θ = 360 (o si dicho argumento se omite), entonces la función circle() dibuja un círculo completo con radio R.

La espiral dorada está conformada por n arcos dibujados de forma consecutiva, cada arco de 90° y con un radio que se multiplica por \(\varphi\) en cada iteración. En este caso, decimos que n es el orden de la espiral. El siguiente código muestra como combinar todos estos elementos:
from turtle import *      # Importar las funciones de gráficas 
                          # de tortuga.

fi = 1.618033988749895    # Definir 𝜑 (sección de oro).

def espiral(n):
    radio = 10            # Definir radio inicial del primer 
                          # arco.    
    for i in range(n):    # Repetir n veces.
        circle(radio, 90) # Dibujar el arco de un cierto radio 
                          # y 90 grados.
        radio *= fi       # Aumentar radio por el factor 𝜑.

hideturtle()       # Esconder la tortuga.
color('SteelBlue') # Establecer color de la pluma: azul 
                   # metálico.
pensize(20)        # Establecer tamaño de la pluma: 20 pixeles.
speed('fastest')   # Establecer velocidad de tortuga: máxima.
setheading(270)    # Apuntar la tortuga hacia el sur.
espiral(8)         # Dibujar espiral de orden 8.
done()             # Evitar que la ventana se cierre 
                   # inmediatamente.
Al ejecutar el programa obtenemos la siguiente figura:

Espiral dorada de orden 8.
Podemos producir una imagen más interesante si dibujamos los cuadrados que contienen a cada uno de los arcos. Al hacer esto podemos observar que la espiral dorada está contenida dentro de una serie (conceptualmente infinita) de rectángulos dorados.
from turtle import *

fi = 1.618033988749895

def cuadro(longitud):
    """Dibuja un cuadrado relleno cuyos lados son de tamaño
       'longitud'.
    """
    begin_fill()
    for i in range(4):
        fd(longitud)
        lt(90)
    end_fill()

def rectangulo_dorado(n, longitud):
    """Dibuja un rectángulo dorado compuesto de 'n'
       cuadrados. El primer cuadrado tiene sus lados de
       tamaño 'longitud'.
    """
    for i in range(n):
        cuadro(longitud)

        # Mover la tortuga a la esquina contraria y girarla
        # 90 grados a la izquierda.
        fd(longitud)
        lt(90)
        fd(longitud)

        longitud *= fi

def espiral_dorada(n, radio):
    """Dibuja una espiral dorada compuesta de 'n' arcos. El
       primer arco tiene un radio de tamaño 'radio'.
    """
    for i in range(n):
        circle(radio, 90)
        radio *= fi

def espiral(n, radio):
    """Dibuja una espiral dorada de orden 'n' sobre el
       rectángulo dorado que lo alberga.
       El primer arco/cuadro tiene un radio/lado de tamaño
       'radio'.
    """

    color('White')
    fillcolor('SteelBlue')
    pensize(1)
    rectangulo_dorado(n, radio)

    # Regresa la tortuga al centro de la pantalla pero sin
    # dibujar por su paso.
    penup()
    home()
    pendown()

    color('Gold')
    pensize(4)
    espiral_dorada(n, radio)

hideturtle()
speed('slow')
espiral(11, 2)
done()
El código anterior es más elaborado pero el resultado bien vale la pena:

Espiral dorada de orden 11 sobre su
rectángulo dorado correspondiente.