Capítulo 3 - Fractales

Continuemos con otro ejemplo. En este capítulo veremos algo de teoría acerca de fractales, y cómo crear la imagen de un fractal a partir de su ecuación. Las aplicaciones de las imágenes de fractales no son muy populares, pero sí tienen un toque artístico y estético para algunas personas. Desde nuestro punto de vista, es un buen ejemplo para manipular los píxeles de la pantalla individualmente y también para tratar vectores, como un adelanto al tema.

Concepto

El término fractal viene de "dimensión fraccional" - en inglés, fractional dimension. La definición de un fractal es un objeto o cantidad que muestra auto-semejanza para todas las escalas. El objeto no tiene por qué demostrar la misma estructura en todas las escalas, pero sí el mismo tipo de estructura. Para que los lectores se hagan una idea, piensen que la longitud de un fractal es la longitud del borde (o la "costa") medida con reglas de diferentes longitudes. Cuanto más corta sea la regla, más grande es la longitud medida. Esta conclusión es conocida como la paradoja de la costa.

Las imágenes de fractales pueden ser generadas a partir de una definición recursiva. Tal definición puede ser el trazado de líneas rectas basándose en una gramática. Este conjunto de reglas se denomina reglas de producción, como es el caso de la curva de Koch, en la Figura 1.

También podemos dibujar el conjunto de valores que forman parte de una definición recursiva, como es el caso del fractal de Mandelbrot, en la Figura 2.

Explicaremos estos fractales en mayor detalle a continuación.

Fractales: Curva de Koch

La curva de Koch se construye dividiendo un segmento en tres partes iguales. El segundo segmento - el segmento del medio - forma la base de un triángulo equilátero, pero sin representar este segmento - la base. Esto significa que tenemos un segmento horizontal seguido de dos segmentos, estos dos últimos en forma de triángulo, y luego seguido de un tercer segmento horizontal. Esta estructura es la primitiva para construir esta curva. En siguientes repeticiones, cada segmento de esta curva primitiva es a su vez sometido al mismo algoritmo: segmento horizontal seguido de dos segmentos terminando en la "punta" de un triángulo equilátero y seguido por un tercer segmento horizontal.

La estructura primitiva se puede definir usando la siguiente regla o axioma de producción:

A → AIADDAIA,

donde A indica avanzar, lo cual implica trazar una línea recta,

I es girar a la izquierda, y

D es girar a la derecha.

En el caso de la curva de Koch, cada giro se hace con un ángulo de 60° = π/3 radianes. Los ángulos son 60° porque la curva de Koch se construye en base a un triángulo equilátero. Todos los ángulos de un triángulo equilátero son 60°.

Podemos observar el estado inicial de la curva de Koch, que simplemente es una línea recta, en la Figura 3. Siguiendo la regla que tenemos, avanzamos una sola vez.

Para la primera iteración, obtenemos la secuencia: AIADDAIA con un ángulo de giro de 60°. Realmente estamos sustituyendo la regla de avanzar, inicialmente establecida, por la secuencia descrita por la regla de producción:

1. Avanzar el primer tercio.
2. Girar 60° a la izquierda.
3. Avanzar otro tercio.
4. Girar 60° a la derecha.
5. Girar 60° a la derecha.
6. Avanzar otro tercio.
7. Girar 60° a la izquierda.
8. Avanzar el último tercio.

Obtenemos una imagen como en la Figura 4.

En la segunda iteración, realizamos el mismo método basándonos en nuestra regla de producción. Aplicamos: A → AIADDAIA para cada 'A'. Esto implica que sustituimos cada 'A' por su definición para lograr el siguiente producto: AIADDAIA I AIADDAIA DD AIADDAIA I AIADDAIA. He aquí el elemento recursivo. Al seguir esta regla obtenemos una imagen como la presentada en la Figura 5.

Podríamos reescribir la definición de esta regla para reflejar la recursividad:

A₀ → Avanzar

A_n+1 → A_nIA_nDDA_nIA_n

donde n indica el número de repeticiones.

Para trazar estas líneas y seguir la regla de producción, nos basamos en la idea de un cursor gráfico. Este cursor contiene una pareja de coordenadas que describe su posición actual y un ángulo que describe su orientación. Necesitamos definir previamente la longitud inicial de A₀. Cada vez que "avancemos", calculamos la siguiente posición usando a) la posición actual del cursor como punto inicial, b) tomando un tercio de la longitud inicial, y c) aplicando trigonometría (senos y cosenos) con el ángulo del cursor. La razón de usar un tercio de la longitud es para reducir el tamaño de cada figura para que la imagen final se limite a una distancia adecuada. Si usáramos la misma longitud inicial para cada segmento, entonces obtendríamos una imagen bastante grande cuantas más iteraciones hiciéramos; es decir, cuanto mayor sea el valor de n. La imagen sería tan grande que posiblemente parte de ella sobresalga la pantalla. Por esta razón, optamos por dividir el segmento inicial en partes de menor longitud, para que la curva final sea más manejable.

Algoritmo

El algoritmo para trazar la curva de Koch se divide en dos partes. La primera parte, Iniciar_Koch(), es básicamente invocar la función recursiva, Dibujar_Koch(). La segunda parte, Dibujar_Koch(), es el algoritmo de la función recursiva en sí.

Para Iniciar_Koch(), el algoritmo es:

Iniciar_Koch( Punto_Inicial, Longitud, Número_Iteraciones )
Declarar:  Cursor  como un punto y un ángulo
Inicializar  Cursor:
Cursor.punto  ← Punto_Inicial
Cursor.ángulo ← 0
Dibujar_Koch( Cursor, Longitud, Número_Iteraciones )
Terminar

Como ángulo inicial, elegimos 0 radianes. Esto implica que estamos en dirección horizontal y con una orientación hacia la derecha.

Longitud es la distancia entre el punto inicial y final.

Para Dibujar_Koch(), el algoritmo es:

Dibujar_Koch( Cursor, Dist, N )
Si N = 0  entonces,		// A(vanzar)
Cursor.punto ← Avanzar( Cursor, Dist )
Terminar
Si no, entonces,		// Recursividad: A→AIADDAIA
Dibujar_Koch( Cursor, Dist/3, N-1 )		// A
Cursor.ángulo ← Cursor.ángulo + π/3		// I
Dibujar_Koch( Cursor, Dist/3, N-1 )		// A
Cursor.ángulo ← Cursor.ángulo - π*2/3		// DD
Dibujar_Koch( Cursor, Dist/3, N-1 )		// A
Cursor.ángulo ← Cursor.ángulo + π/3		// I
Dibujar_Koch( Cursor, Dist/3, N-1 )		// A
Terminar

Dist es la distancia o longitud de cada segmento.

N es el número de iteraciones.

Para Avanzar(), el algoritmo es:

Real Avanzar( Cursor, D )
Declarar  P  como un punto: (x,y)
P.x ← Cursor.punto.x + D*cos( Cursor.ángulo )
P.y ← Cursor.punto.y + D*sen( Cursor.ángulo )
Dibujar_Línea( Cursor.punto.x, Cursor.punto.y, P.x, P.y )
Terminar( P )

D es la distancia o longitud del segmento a trazar.

Dibujar_Línea() es la función básica, en cualquier API o librería gráfica, para trazar una línea recta desde un píxel a otro.

En el algoritmo, debemos actualizar el Cursor después de cada operación: avanzar o girar. Una vez acabada un avance, actualizamos la posición de Cursor.punto con la nueva posición (calculada). Para realizar un giro, agregamos o restamos el ángulo en Cursor.ángulo.

Observaciones

Para trazar las líneas rectas, podemos usar directamente los valores de los píxeles. Sin embargo, como los píxeles deben ser valores enteros, no podemos guardarlos como tales en Cursor.punto. Si lo hiciéramos, entonces perderíamos información al truncarse la parte decimal. Esto implicaría que la imagen contendría errores visibles, especialmente al repetir muchas veces: n > 1. Para evitar este efecto, guardamos los píxeles en Cursor.punto como valores decimales. En el momento de trazar la línea recta, debemos convertir tales valores decimales a enteros usando cualquier método de redondeo. De esta forma, sólo truncamos los valores en el momento propicio (al trazar una línea recta), pero manteniendo la información en nuestro cursor gráfico y así no producir errores de aproximación.

En el algoritmo anterior, no hemos tenido en cuenta la orientación del eje-Y de la pantalla (en píxeles). Esto es porque la función Dibujar_Línea() se hace cargo de ello. De todas formas, podemos implementar este cambio de orientación con simplemente cambiar el signo del ángulo: girar a la izquierda es negativo y girar a la derecha es positivo. Según las reglas de trigonometría,

cos( -x ) =  cos( x ), y
sen( -x ) = -sen( x )

En nuestro algoritmo, esto implica que el valor de la coordenada X permanece invariado, mientras que el de la coordenada Y es de sentido negativo. Esto es justo lo que necesitamos, ya que la mayoría de los sistemas gráficos definen la orientación del eje-Y como positivo desde arriba a abajo, en vez de la orientación convencional del plano cartesiano.

Explicación Detallada

Para aquellos lectores que les interese conocer más acerca de las matemáticas relacionadas con estos conceptos, expondremos una explicación acerca de este fractal. No es necesario seguir esta explicación para dibujar fractales, por lo que el lector puede saltarse este apartado.

La dimensión fraccional - también denominada dimensión de capacidad o dimensión de Hausdorff - para la curva de Koch se basa en la longitud y número de tramos de cada iteración. Dejemos que N_n sea el número de tramos, según la iteración n, y L_n, la longitud de cada tramo, según la iteración n.

N0 = 1,     (Imagen de la Figura 3)
N1 = 4,     (Imagen de la Figura 4)
N2 = 16,    (Imagen de la Figura 5)
N3 = 64,
.
.
.
Nn = 4n,

L0 = 1,     (Imagen de la Figura 3)
L1 = 1/3,   (Imagen de la Figura 4)
L2 = 1/9,   (Imagen de la Figura 5)
L3 = 1/27,
.
.
.
Ln = 1/3n = 3-n

El cálculo de la dimensión de la capacidad, d_cap, es:

                   ln Nn                ln 4n                 n * ln 4
dcap = - lim n→∞ ------ = - lim n→∞ ------- = - lim n→∞ ----------- =
                   ln Ln                ln 3-n               -n * ln 3

                 ln 4     ln 4
     = lim n→∞ ------ = ------ = 1,261859507...
                 ln 3     ln 3

(Nota: ∞ se refiere al concepto matemático de "infinito").

La dimensión de la curva de Koch es 1,262, aproximadamente. Podemos comprobar este valor aplicando la siguiente fórmula:

Nn = Ln-dcap ⇒ Nn = (3-n)-1,262 ⇒ Nn = 4n

Aquí vemos que d_cap es el exponente para L_n que equivale a N_n.

Ejercicios

Enlace al paquete de este capítulo.

1. Escriba un programa que dibuje la curva de Koch. Se puede implementar el algoritmo mostrado en el capítulo. Prueben con varios valores de N; N=2,3,4. Después de muy pocas pasadas no se notará visualmente gran diferencia de detalle en la imagen. Prueben con una resolución aceptable: 300x300 ó 500x500. También se puede cambiar el ángulo inicial de 0 radianes a π/4 radianes (=45°), o al que guste.
2. Uno de los ejemplos más populares es crear el Copo de Nieve de Koch. Esto se hace creando la curva de Koch basada en un triángulo equilátero en vez de una línea recta horizontal. Dicho de otra forma,
   B → IA_nDDA_nDDA_n, con un ángulo de 60° (=π/3 radianes) para formar el triángulo equilátero a partir de la "base".
   A₀ → Avanzar,
   A_n+1 → A_nIA_nDDA_nIA_n,
   
   Hemos agregado otra "regla", B, para describir la estructura que formará la base: un triángulo equilátero. Básicamente, estaremos dibujando 3 curvas de Koch situadas en cada lado del triángulo, con las "puntas" hacia fuera. Después de unas cuantas iteraciones, la figura dará forma a un copo de nieve.
   
   

   

   
   El ejercicio consiste en crear un programa que dibuje el copo de nieve de Koch descrito anteriormente.
3. Otro ejemplo popular es realizar el Anti-Copo de Nieve de Koch. Esto consiste en dibujar las curvas de Koch con las puntas hacia el interior del triángulo al igual que tener un triángulo invertido; el triángulo se apoya con su pico y con un lado hacia en la parte superior en vez de en la inferior. Existen varias formas de realizar este fractal. Podemos optar por cambiar la regla de:
   
   1. A_n+1 para que la punta de la curva de Koch se oriente hacia la derecha. Es decir,
      A_n+1 → A_nDA_nIIA_nDA_n, o
      
   2. B para que la forma de dibujar el triángulo equilátero básico ya tenga una orientación inversa. Esto implicaría que,
      B → IA_nIIA_nIIA_n, a partir del "pico" del triángulo invertido.
      
   
   

   

   
   Escriba un programa que dibuje el anti-copo de nieve descrito en este ejercicio.
4. Con estas reglas de producción, podemos construir muchos tipos de figuras. Escriba un programa para dibujar cada figura descrita por las siguientes reglas de producción:
   
   1. La Isla de Gosper,
      B → A_nDA_nDA_nDA_nDA_nDA_n, describe un hexágono regular,
      A₀ → Avanzar,
      A_n+1 → A_nIA_nDA_n,
      Todos los giros se hacen con un ángulo de 60° (= π/3 radianes).
      Resolución: 400x400.
      Longitud original (del Avance): 250 píxeles.
      División del tramo: d=1/3.
      Calcule A₄.
      
      

      

   2. Fractal de Cesàro,
      B → A_nIA_nIA_nIA_n, con un ángulo de 90° (=π/2 radianes), describe un cuadrado,
      A₀ → Avanzar,
      A_n+1 → A_nIA_nDDA_nIA_n,
      Los giros de A_n se hacen con un ángulo de 60° (=π/3 radianes). Esta regla es la misma que la curva de Koch, pero la regla de la base es un cuadrado. Los picos de la curva de Koch apuntan al interior del cuadrado. Esto "restará" al cuadrado original. Obtendremos una imagen parecida a un copo de nieve.
      Resolución: 400x400.
      Longitud original (del Avance): 250 píxeles.
      División del tramo: d=1/3.
      Calcule A₄.
      
      

      

5. Una limitación, que podemos observar con las reglas de producción presentadas en este capítulo, es que son lineales. Seguimos avanzando, a medida que leemos - e interpretamos - los símbolos, hasta terminar según la profundidad en que nos encontremos. Ahora agregaremos la característica de recordar un lugar en nuestra regla y poder volver a ello. Podemos agregar otros dos símbolos a nuestra gramática que forman las reglas de producción; éstos son: [ y ]. El corchete abierto, [, representa que el Cursor es agregado a una pila. El corchete cerrado, ], indica que se saca - y se usa - el Cursor de la pila. Observen que la información guardada es tanto la posición como el ángulo del Cursor.
   Escriba un programa que dibuje una figura para cada una de las siguientes reglas de producción:
   
   1. árbol sin hojas pero con muchas ramas,
      A₀ → Avanzar,
      A_n+1 → A_n[IA_n]A_n[DA_n]A_n,
      ángulo inicial: 90° (=π/2 radianes) - para que el árbol esté "de pie".
      Todos los giros se hacen con un ángulo de 27° (= 0,471239 radianes).
      Resolución: 400x400.
      Longitud original (del Avance): 400 píxeles.
      División del tramo: d=1/3.
      Calcule A₆.
      
      

      

   2. Fractal de Hielo, basado en un triángulo,
      B → IA_nDDA_nDDA_n, con un ángulo de 60° para formar el triángulo equilátero,
      A₀ → Avanzar,
      A_n+1 → A_nA_nA_nIIA_nDDDA_nIIA_nDDDA_nIIA_nA_nA_n,
      Todos los giros se hacen con un ángulo de 60° (= π/3 radianes).
      Resolución: 400x400.
      Longitud original (del Avance): 380 píxeles.
      División del tramo: d=1/6
      Calcule A₄.
      
      

      

   3. Fractal de Hielo, basado en un triángulo,
      B → A_nIIA_nIIA_n, con un ángulo de 60° para formar el triángulo equilátero,
      éste es el mismo fractal que el anterior en b), pero el fractal "crecerá" hacia el interior del triángulo.
      
      

      

   4. Fractal de Hielo, basado en un cuadrado,
      B → A_nIA_nIA_nIA_n, con un ángulo de 90° (=π/2 radianes), describe un cuadrado regular,
      A₀ → Avanzar,
      A_n+1 → A_nA_nIA_nDDA_nIA_nA_n,
      Todos los giros se hacen con un ángulo de 90° (= π/2 radianes).
      Resolución: 400x400.
      Longitud original (del Avance): 267 píxeles.
      División del tramo: d=1/4.
      Calcule A₄.
      
      

      

   5. Fractal de Hielo, basado en un cuadrado,
      B → A_nDA_nDA_nDA_n, con un ángulo de 90° (=π/2 radianes), describe un cuadrado regular,
      éste es el mismo fractal pero el fractal "crecerá" en el interior del cuadrado.
      
      

      

   6. árbol con ramas y hojas,
      A₀ → Avanzar,
      A_n+1 → A_nA_n[IA_n][DA_n],
      ángulo inicial: 90° (=π/2 radianes) - para que el árbol esté "de pie".
      Todos los giros se hacen con un ángulo de 30° (= π/6 radianes).
      Resolución: 400x400.
      Longitud original (del Avance): 200 píxeles.
      División del tramo: d=1/2.
      Calcule A₇.
      
      

      

6. Ahora agregaremos otro símbolo a nuestra gramática. Se trata de la letra E que indica avanzar en el tramo que se encuentra pero en forma de espejo. Tenemos que invertir las instrucciones de la regla al igual que cambiar todos los casos de Izquierda a Derecha y de Derecha a Izquierda. Por ejemplo, si tenemos la siguiente regla:
   A₀ → Avanzar,
   E₀ → Avanzar,
   A_n+1 → IE_nA_nDA_nDE_nIA_n, con un ángulo de giro de 90° (= π/2 radianes), y
   E_n+1 → A_nDE_nIA_nIA_nE_nD
   
   Como pueden observar, E_n+1 invierte el orden de la regla de A_n+1 y luego cambia todos los giros I y D a D e I, respectivamente.
   
   Para A₁, la regla es simplemente: IE₀A₀DA₀DE₀IA₀, como E₀ es igual a A₀, entonces la regla es equivalente a: IA₀A₀DA₀DA₀IA₀
   Para A₂, la regla se convierte en: IE₁A₁DA₁DE₁IA₁
   Esta regla se expandirá a: I A₀DE₀IA₀IA₀E₀D IE₀A₀DA₀DE₀IA₀ D A₀DE₀IA₀IA₀E₀D D IE₀A₀DA₀DE₀IA₀ I A₀DE₀IA₀IA₀E₀D
   
7. Cree un programa para que trace cada uno de los siguientes fractales:
   
   1. Curva basada en Peano,
      A₀ → Avanzar, y
      A_n+1 → IE_nA_nDA_nDE_nIA_n, con un ángulo de giro de 90° (= π/2 radianes)
      ángulo inicial: -132,825° (= -2,3182 radianes) o si lo prefieren: 227,175° (= 3,9650 radianes).
      Resolución: 400x400.
      Longitud original (del Avance): 231 píxeles
      División del tramo: d=√(1/5) = 0,44721.
      Calcule A₅.
      
      

      

   2. Curva de Peano-Gosper,
      A₀ → Avanzar,
      A_n+1 → A_nIE_nIIE_nDA_nDDA_nA_nDE_nI,
      Todos los giros se hacen con un ángulo de 60° (= π/3 radianes).
      Resolución: 400x400.
      Longitud original (del Avance): 300 píxeles.
      División del tramo: d=√(1/7) = 0,37796.
      Calcule A₅.
      
      

      

   3. Curva de Peano-Sierpinski,
      A₀ → Avanzar,
      A_n+1 → IE_nDA_nDE_nI,
      Todos los giros se hacen con un ángulo de 60° (= π/3 radianes).
      Resolución: 400x400.
      Longitud original (del Avance): 400 píxeles.
      División del tramo: d=1/2.
      Calcule A₈.
      
      

      

Fractales: Triángulo de Sierpinski

El segundo ejemplo de fractales que veremos es el triángulo de Sierpinski. Este triángulo también se basa en un método recursivo, como el ejemplo anterior. Comenzamos con un triángulo equilátero, como muestra la imagen de la Figura 1.

En cada pasada, dividimos el triángulo en tres triángulos más pequeños. Los lados de cada "sub-triángulo" equilátero tienen la mitad de longitud que los del triángulo original, el cual estamos dividiendo. Con la mitad de longitud, el área de cada subtriángulo es un cuarto del original. Por lo tanto, podemos rellenar el triángulo original con cuatro triángulos pequeños. En el fractal de Sierpinski, sólo nos interesamos con tres subtriángulos, por lo que el triángulo invertido en el centro es realmente un "agujero". Esto se observa más claramente en la Figura 2.

Con la tercera pasada, dividimos cada subtriángulo como si fuera el original. De nuevo obtenemos tres triángulos más pequeños y un agujero en el centro. El total será de nueve triángulos y cuatro agujeros. Esto se percibe más claramente en la Figura 3.

Nuevamente, podemos observar el elemento recursivo en este fractal, para generar el triángulo de Sierpinski. Comenzamos con tres puntos (A, B, y C) formando las coordenadas de los vértices del triángulo original. Luego, la función recursiva averiguará la mitad de cada lado (AB, BC, y CA) usando los vértices. El orden para subdividir cada triángulo es irrelevante: el izquierdo, el derecho, y luego el superior, o cualquier orden que se quiera seguir.

Algoritmo

El algoritmo para dibujar el triángulo de Sierpinski se puede separar en dos partes principales. La primera parte, Iniciar_Sierpinski(), es sencillamente la invocación a la función recursiva, Dibujar_Sierpinski(). La segunda parte es el algoritmo de la función recursiva en sí, Dibujar_Sierpinski().

Para Iniciar_Sierpinski(), el algoritmo es:

Iniciar_Sierpinski()
Declarar:  A, B, y C  como puntos
Inicializar:  A, B, y C
Dibujar_Sierpinski( A, B, C, Número_Iteraciones )
Terminar

A, B, y C son los vértices del triángulo original.

Para Dibujar_Sierpinski(), el algoritmo es:

Dibujar_Sierpinski( A, B, C, N )
Si N = 0  entonces,		// Triángulo Mínimo
Dibujar_Triángulo_Relleno( A, B, C )
Terminar
Si no, entonces,		// Dividir en 3 triángulos
AB ← Mitad( A, B )
BC ← Mitad( B, C )
CA ← Mitad( C, A )
Dibujar_Sierpinski( A, AB, CA, N-1 )
Dibujar_Sierpinski( AB, B, BC, N-1 )
Dibujar_Sierpinski( CA, BC, C, N-1 )
Terminar

A, B, y C son los vértices del triángulo o subtriángulo.

N es el número de iteraciones.

Para Mitad(), el algoritmo es:

Real Mitad( P1, P2 )
Resultado.x ← (P1.x + P2.x) / 2
Resultado.y ← (P1.y + P2.y) / 2
Terminar( Resultado )

En el algoritmo, no dibujamos nada hasta llegar al triángulo más pequeño; o sea, N = 0. En los otros niveles de profundidad, N > 0, sólo dividimos cada lado en tres triángulos más pequeños y calculamos las dimensiones de cada subtriángulo.

La función Dibujar_Triángulo_Relleno() hace referencia a una función de la biblioteca o API gráfica para dibujar un triángulo según las vértices dadas en orden. Esto es, se trazan las líneas del primer vértice al segundo (A→B), del segundo al tercero (B→C), y del tercero al primero (C→A). El triángulo es dibujado y rellenado con los colores previamente establecidos.

Observaciones

Como sucedió con la curva de Koch, podemos usar directamente los valores de los píxeles para describir los vértices del triángulo. Sin embargo, como los píxeles deben ser valores enteros, no podemos guardarlos como tales en A, B, y C. Si lo hiciéramos, entonces perderíamos información al ser truncada la parte decimal. Esto implicaría que la imagen contendría errores visibles: los lados de los triángulos no son tan rectos, especialmente al repetir muchas veces: n > 1. Para evitar este efecto, guardamos los píxeles en A, B, y C como valores decimales. En el momento de dibujar el triángulo, debemos convertir tales valores decimales a enteros usando cualquier método de redondeo. De esta forma, sólo truncamos los valores en el momento propicio (al dibujar un triángulo), pero manteniendo la información y así no producir errores de aproximación.

En el algoritmo anterior, no hemos tenido en cuenta la orientación del eje-Y de la pantalla (en píxeles), esto es porque hemos usado píxeles directamente. Por lo tanto, estamos calculando y dibujando en el mismo plano: la pantalla o píxeles. Esto implica que no necesitamos realizar ningún tipo de conversión o cambio de coordenadas.

Explicación Detallada

Para aquellos lectores que les interese conocer más acerca de las matemáticas relacionadas con estos conceptos, expondremos una explicación acerca de este fractal. La dimensión de capacidad para el triángulo de Sierpinski se basa en la longitud y número de triángulos pintados de cada iteración.

Dejemos que N_n sea el número de triángulos, según la iteración n, y L_n, la longitud de cada lado, según la iteración n.

N0 = 1,     (Imagen de la Figura 1)
N1 = 3,     (Imagen de la Figura 2)
N2 = 9,     (Imagen de la Figura 3)
N3 = 27,
.
.
.
Nn = 3n,

L0 = 1,     (Imagen de la Figura 1)
L1 = 1/2,   (Imagen de la Figura 2)
L2 = 1/4,   (Imagen de la Figura 3)
L3 = 1/8,
.
.
.
Ln = 1/2n = 2-n

El cálculo de la dimensión de la capacidad, d_cap, es:

                   ln Nn                ln 3n                 n * ln 3
dcap = - lim n→∞ ------ = - lim n→∞ ------- = - lim n→∞ ----------- =
                   ln Ln                ln 2-n               -n * ln 2

                 ln 3     ln 3
     = lim n→∞ ------ = ------ = 1,584962501...
                 ln 2     ln 2

(Nota: ∞ se refiere al concepto matemático de "infinito").

El triángulo de Sierpinski comienza como un objeto de dos dimensiones; o sea, una superficie. En cada iteración, se le "agregan" agujeros al triángulo. Llevado a infinito, obtenemos más agujeros que superficie, hasta quedarnos con un objeto de líneas rectas. Sin embargo, una línea recta es un objeto unidimensional. Es decir, hemos ido de un objeto 2D a un objeto 1D. La pregunta principal es ¿qué dimensión tiene este objeto? Según hemos visto, la dimensión debe quedar entre 1 y 2 dimensiones. Esta idea conlleva a la idea de una dimensión fraccional. En el caso del triángulo de Sierpinski, obtenemos una dimensión aproximada de 1,6, que efectivamente queda dentro de nuestro intervalo de 1 y 2 dimensiones.

Para dar un ejemplo, como explicación, imaginaos que tenemos un queso suizo con más agujeros que queso, hasta tal punto que tenemos un hilo de queso, pero todo agujero.

Ejercicios

Enlace al paquete de este capítulo.

1. Escriba un programa que dibuje el triángulo de Sierpinski. Se puede usar el algoritmo presentado en este capítulo. Use las siguientes restricciones y condiciones iniciales:
   Resolución: 500 x 500.
   Calcule, con N=5 iteraciones.
2. El triángulo de Sierpinski no tiene por qué ser equilátero. Construya el triángulo de Sierpinski para cada triángulo descrito por sus vértices, use las siguientes restricciones:
   Resolución: 500 x 500
   Calcule, con N=4 iteraciones.
   
   1. A = (0, 0), B = (499, 499), y C = (0, 499);
   2. A = (250, 0), B = (375, 499), y C = (125, 499);
   3. A = (300, 50), B = (400, 400), y C = (10, 200);
3. Escriba el triángulo de Sierpinski, pero ahora se perturbará los vértices. Cada vez que se calculen los puntos medios para cada subtriángulo, se agregará un valor aleatorio en una orientación aleatoria. La forma más sencilla de hacer esto es seleccionando un intervalo para la perturbación. Por ejemplo, elegimos un intervalo de 5 píxeles. Necesitamos generar números aleatorios entre -2 y +2. Si por casualidad generamos el valor 0 (cero), entonces no realizamos ninguna perturbación. Las perturbaciones se deberán hacer en ambas direcciones: eje-X y eje-Y. Para una coordenada (x, y) agregamos dos valores aleatorios, a y b, a cada elemento, obteniendo (x+a, y+b).

4. En lugar de usar triángulos, podemos usar cuadrados. Comenzamos con un cuadrado como figura original. En la primera iteración, dividimos nuestro cuadrado original en 9 cuadrados más pequeños de igual tamaño. El cuadrado central está vacío y queda como agujero, mientras que los demás son rellenados formando un borde. En las demás iteraciones, cada subcuadrado es sometido al mismo proceso. A este fractal se le denomina Alfombra de Sierpinski. La siguiente figura puede servir de ejemplo:

   
   

   

   Escriba un programa para representar la alfombra de Sierpinski con las siguientes restricciones y valores iniciales:
   Resolución: 500 x 500.

   Calcule, con N=4 iteraciones.

Fractales: Mandelbrot

El tercer y último ejemplo de fractales que daremos es el famoso fractal de Mandelbrot. Este fractal se basa en una ecuación y un método iterativo. La imagen que mostramos no es una gráfica de una ecuación sino un conjunto de valores.

Partimos de la ecuación: Z_n+1 = Z_n² + C, donde Z y C son números complejos y n ≥ 0. Inicialmente, Z₀ = C. Z es la variable, C una constante, y n el índice para la secuencia y por tanto para la iteración. Brevemente, los números complejos se componen de dos partes distintas: la parte real x y la parte imaginaria y. Podemos escribir un número complejo como z = x + iy, donde x e y son números reales e i es el número complejo definido como i = √-1. También se puede reescribir usando la siguiente notación: (x, y).

Para la ecuación de Mandelbrot, podemos reescribirla en la forma de sus componentes:

(xn+1,yn+1) = (xn2-yn2+xc, 2xnyn+yc)

Visto de otro modo:

xn+1 = xn2 - yn2 + xc,
yn+1 = 2xnyn + yc

donde Z_n = (x_n, y_n) y C = (x_c, y_c).

El método para obtener el fractal, basada en esta ecuación, trata de averiguar si un número complejo cualquiera para C pertenece al conjunto de Mandelbrot. Si C pertenece al fractal, entonces se colorea de negro (por ejemplo), y si no, pues de blanco. La forma de saber si C pertenece o no al fractal de Mandelbrot es calculando la siguiente iteración y comprobando su distancia a un valor limitante, r. Esto es, |Z_n| < r, donde |Z_n| es la distancia o longitud del número complejo.

Esto se puede reescribir como:

|Z_n| = |√(x_n²+y_n²)|< r

Generalmente, se usa un radio (valor limitante) r = 2 para el fractal de Mandelbrot.

Ahora que tenemos las condiciones impuestas, deberemos iterar el proceso. Sin embargo, necesitamos otro valor limitante para saber cuándo terminar. Este valor deberá ser grande para dejar suficiente tiempo al proceso con el fin de comprobar que el valor de Z_n no se salga fuera del radio r. Podemos usar un nivel de tolerancia de 3.000, 10.000, o incluso 20.000. Pero la verdad es que este valor depende del área del fractal en que nos fijemos. Si magnificamos una parte del fractal es posible que perdamos algunos detalles porque nuestro nivel de tolerancia no era muy grande. La causa de esto es que algunos valores de Z_n sean malinterpretados como valores no pertenecientes al conjunto de Mandelbrot, cuando en verdad sí pertenecen.

Cambio de Coordenadas

Según vimos en el capítulo 2, debemos realizar un cambio de coordenadas, ya que los sistemas de coordenadas que usamos no son idénticos. Como nuestro proceso usa la fórmula de Mandelbrot, nos encontramos en el sistema de coordenadas complejas. Sin embargo, podemos pasarnos al sistema cartesiano con facilidad. El problema está en que al terminar nuestros cálculos, debemos representar algo en la pantalla. Por este motivo debemos cambiar del sistema cartesiano al sistema gráfico de la pantalla.

En el caso de generar el fractal de Mandelbrot, iremos píxel a píxel comprobando si éstos pertenecen al conjunto de Mandelbrot o no. Para hacer esto, debemos conocer previamente las dimensiones de nuestra vista. Como dijimos en el capítulo 2, no podemos representar todos los valores, porque éstos son infinitamente muchos, cuando sólo disponemos de la pantalla que es finito: limitado. Por lo tanto, debemos escoger las dimensiones para los valores de X y para los valores de Y. Luego, debemos convertir tales valores a sus equivalentes en píxeles.

Digamos que queremos representar la imagen entre x = [-6, +6] e y = [-4, +4] a una resolución de 500 x 500. Necesitamos saber qué representa cada píxel (x_p,y_p) en términos de estas dimensiones, ya que cada pareja de valores corresponderá a un valor de C en nuestra fórmula de Mandelbrot. Siguiendo nuestro ejemplo, obtenemos que,

        |xui - xuf|     |-6 - 6|
dxup = ------------ = --------- =
         anchurap         500

       12 unidades
    = ------------- = 0,024 unidades/píxel
       500 píxeles

        |yui - yuf|     |-4 - 4|
dyup = ------------ = --------- =
         alturap          500

        8 unidades
    = ------------- = 0,016 unidades/píxel
       500 píxeles

En nuestro ejemplo, cada píxel representa 0,024 unidades en el eje X y 0,016 unidades en el eje Y del plano cartesiano. Los valores de dx_up y dy_up son nuestros incrementos para comprobar cada píxel para C en nuestra fórmula de Mandelbrot.

Algoritmo

De nuevo, separaremos el algoritmo para dibujar el fractal de Mandelbrot en dos partes principales:

• La primera parte, Iniciar_Mandelbrot(), es el cálculo para cambiar de píxeles a unidades cartesianas y la invocación a la función iterativa, Mandelbrot().
• La segunda parte es el algoritmo del proceso iterativo, Mandelbrot().

Para Iniciar_Mandelbrot(), el algoritmo es:

Iniciar_Mandelbrot()
Inicializar valores para: xui, xuf, yui, yui, xpi, xpf, ypi, ypf,
  num_max_iteraciones, radio, C
anchurau Fracta |xuf - xui|
alturau  ← |yuf - yui|
anchurap ← |xpf - xpi + 1|
alturap  ← |ypf - ypi + 1|
dxup ← anchurau / anchurap
dyup ← alturau / alturap
Bucle: xp ← xpi hasta xpf con incremento de 1
Bucle: yp ← ypi hasta ypf con incremento de 1
C.x ← xui + xp * dxup
C.y ← yui - yp * dyup
Color ← Mandelbrot( C, num_max_iteraciones, radio )
PonPíxel( xp, yp, Color )
Terminar

• C puede almacenar una coordenada en unidades cartesianas - un número complejo.
• Necesitamos dos bucles anidadas porque necesitamos recorrer y comprobar todos los píxeles en pantalla.
• La función PonPíxel() hace referencia a una función de la biblioteca o API gráfica para establecer un color para un píxel determinado, según las coordenadas dadas.

Para Mandelbrot(), el algoritmo es:

Color Mandelbrot( C, max_iter, r )
bEsMandelbrot ← Verdadero
Z ← C
Z_Sig ← Ecuación( Z, C )
Bucle: k ← 1 hasta max_iter  con incremento de 1 y
       mientras que  bEsMandelbrot = Verdadero
Si Distancia( Z_Sig ) < r  entonces
Z ← Z_Sig
Z_Sig ← Ecuación( Z, C )
Si no, entonces
bEsMandelbrot ← Falso
Si bEsMandelbrot = Verdadero, entonces
Terminar( Negro )
Si no, entonces
Terminar( Blanco )

C, Z, y Z_Sig pueden almacenar una coordenada en unidades cartesianas, cada una.

En este algoritmo, tenemos dos condiciones para terminar el bucle:

1. k > max_iter, y
2. bEsMandelbrot = Falso

Esta última condición se basa en que la distancia de Z ≥ r. Es decir, Z se dispara hacia el infinito.

Al final, la función Mandelbrot() terminará devolviendo o bien el color negro, si el valor de C pertenece al conjunto de Mandelbrot, o bien blanco, si el valor de C no pertenece a dicho conjunto.

Para Ecuación(), el algoritmo es:

Complejo Ecuación( Z, C )
Resultado.x ← Z.x*Z.x - Z.y*Z.y + C.x
Resultado.y ← 2*Z.x*Z.y + C.y
Terminar( Resultado )

Aplicamos la fórmula Z_n+1 = Z_n + C, pero descomponiéndola en partes reales e imaginarias para usarse en el plano cartesiano.

Para Distancia(), el algoritmo es:

Real Distancia( Z )
  1. Resultado ← Raíz_Cuadrada_de( Z.x*Z.x + Z.y*Z.y )
  2. Terminar( Resultado )

Observaciones

En este método, comprobamos cada píxel para saber si tal coordenada en el plano complejo-cartesiano corresponde al conjunto de Mandelbrot. Esto se realiza en base a su fórmula y según las condiciones limitantes. Este algoritmo utiliza métodos vistos en el trazado de una ecuación en el plano cartesiano. Sin embargo, en el trazado, sólo dibujábamos líneas que pertenecían a la línea. En el caso del fractal de Mandelbrot, debemos comprobar cada píxel.

En el algoritmo anterior, hemos tenido en cuenta la orientación del eje-Y de la pantalla (en píxeles). Esto lo hemos realizado con la siguiente fórmula:

xu = xui + xp * dxup,
yu = yui - yp * dyup

Fijémonos en el signo positivo para el valor de x_u, y el signo negativo para y_u. El signo positivo para x indica una orientación idéntica, mientras que el negativo de y indica una orientación contraria al sistema de coordenadas. Esto suele ser lo habitual en sistemas gráficos, pero si esto no es el caso, con simplemente cambiar los signos podemos elegir la orientación que nos sirva.

Otra observación es la complejidad del tiempo de ejecución del algoritmo. Con el algoritmo descrito anteriormente, observaremos una ralentización en su ejecución. Esto se debe a que el algoritmo sigue comprobando si cada valor permanece dentro de las restricciones dadas, hasta completar todas las iteraciones. Sin embargo, podríamos aplicar ciertos criterios según la "naturaleza" de la función base. Realizando comprobaciones de periocidad y dirección, podemos optimizar el proceso. El inconveniente se basa en que cada comprobación depende de la función en sí. Otro inconveniente está en que no todos los lectores saben manipular números complejos para implementar tales comprobaciones en sus programas.

Explicación Detallada

Fractales como los de Mandelbrot, Julia, y muchos más no son utilizables por la mayoría de las personas, que no tengan una buena base de matemáticas. Las imágenes basadas en tales fractales son estéticamente agradables. Otros usos se basan en la propiedad de autosemejanza. Hoy en día existen varios métodos de compresión de datos basados en fractales - esta cualidad de autosemejanza.Se puede alcanzar compresiones de hasta 5.000 á 1. Por supuesto, todo depende de la variedad de los datos al igual a poder encontrar la fórmula matemática para describir tales conjuntos de datos.

Ejercicios

Enlace al paquete de este capítulo.

1. Escriba un programa que represente el fractal de Mandelbrot, con estas características:
   x = [-1, 1], e y = [-1, 1]
   

   Valor máximo de iteraciones: 3.000
   Radio: 4
   Resolución: 300 x 300

2. Podemos usar otras funciones para crear otros tipos de fractales. Realice un programa que genere un fractal basado en cada una de las siguientes fórmulas, reemplazando el algoritmo Ecuación() en el apartado Algoritmo.

   Nota: Se aconseja usar alguna biblioteca para manipular números complejos, especialmente si no se sabe hacer usando matemáticas. En un programa de C++, se puede usar la plantilla complex<T> declarada en <complex>. Se sugiere usar la clase complex<double> para crear cada variable compleja y usar los operadores sobrecargados para llevar a cabo las operaciones necesarias: *, +, -, /, sin(), cos(), exp(), etc.

   1. Z_n+1 = (conj(Z_n))² + C

      Nota: conj() se refiere al conjugado; esto es:
      z = x + iy  o  z = (x,y),
      su conjugado es:
      z' = x - iy  o  z = (x,-y),

      

   2. Z_n+1 = sen(Z_n / C)

      

   3. Z_n+1 = C*exp(Z_n)

      

   4. Z_n+1 = Z_n³ + C

      

   5. Z_n+1 = C*Z_n²

      

   6. Z_n+1 = C*senh(Z_n)

      

   7. Z_n+1 = C*sen(Z_n)

      

   8. Z_n+1 = C*exp(conj(Z_n)) * C*exp(Z_n) = C²*exp(2x)

      

   Nota: x indica la parte real de Z_n

   9. Z_n+1 = sen(Z_n) + Z_n² + C

      

   10. Z_n+1 = cosh(Z_n) + Z_n² + C

       

   11. Z_n+1 = exp(Z_n²) + C

       

   12. Z_n+1 = ln(Z_n) + Z² + C

       Nota: ln hace alusión al logaritmo neperiano o natural.

       

   Observación: Podemos crear cualquier función, especialmente tomando como modelo:
   Z_n+1 = f(z) * Z_n, donde f(z) es cualquier función trigonométrica compleja; por ejemplo,
   f(z) = cos(z),
   f(z) = tan(z),
   f(z) = 2*sen(z)*cos(z),
   etc.

   Advertencia: Es posible que, en algunas bibliotecas estándares, las implementaciones de algunas funciones no den buenos resultados. Por lo tanto, use las siguientes definiciones:

3. Se aconseja crear un puntero a una función, para luego poder cambiar de función fácilmente, sin tener que reprogramar el algoritmo. Por ejemplo, el código parcial en C++, puede ser el siguiente:

   typedef Punto (*f_z)( Punto, Punto );
   
   Punto mandelbrot( Punto Z, Punto C );
   
   void fractal( f_z f, Punto Z_0, Punto C, unsigned long num_iteraciones, double r )
   {
     ...
     for( k=2; k<=num_iteraciones && !bEsMandelbrot; k++ )
       if( (d=dist(Z_sig)) < r )
       {
         Z = Z_sig;
         Z_sig = f( Z, C ); /* Invocamos la función general */
       }
       else bEsMandelbrot = true;
    ...
   }
   
   void Dibujar(void)
   {
     ...
     fractal( mandelbrot, Z_0, C, num_iteraciones, r );
   }
   

   Podemos ver que sólo tenemos que pasar el puntero de la función que queramos mostrar. El algoritmo implementado en fractal() aplicará cualquier función dada.

4. Las imágenes interesantes de los fractales se encuentran en la "costa" o borde del fractal. Aquí es donde se encuentran muchas bahías, ríos, afluentes, y deltas. Cree un programa para facilitar el engrandecimiento (o zoom) de cualquier área de un fractal. Esto se puede lograr, calculando las dimensiones originales de la imagen, un factor de engrandecimiento, y un punto central a tal área engrandecida.

   Por ejemplo,

   Si comenzamos con unas dimensiones de:

   x = [-1, +3] e y = [0, +2],
   

   entonces podemos hacer un zoom al área como punto central (0,5, -0,5) y con un factor de zoom de 3,0. Es decir, nuestro área nueva será 3 veces menor que la original, con un punto central de (0,5, -0,5). Esto se haría de la siguiente forma:

   1. Mudamos una de las esquinas de nuestro área rectangular al origen: (0, 0). Esto se puede calcular fácilmente:

      Elegimos la esquina inferior izquierda: (-1, 0). Ahora desplazamos las dimensiones, para que esta esquina se sitúe en el origen, (0, 0):

      x = [-1-(-1), +3-(-1)]
      y = [0-0, +2-0]
      

      Obtenemos,

      x = [0, +4]
      y = [0, +2]

   2. Ahora cambiamos las dimensiones según el factor de zoom: 3,0. Como se trata de un zoom hacia dentro, estamos reduciendo el tamaño original por 3,0, que es lo mismo que dividir las longitudes entre 3,0. Esto sería:

      x = [0/3,0, 4/3,0]
      y = [0/3,0, 2/3,0]
      

      Resultando en,

      x = [0,0, 1,3333]
      y = [0,0, 0,6666]

   3. Ya que las dimensiones han sido reducidas, ahora podemos desplazar las dimensiones de nuestro área según el punto central dado: (0,5, -0,5). Esto no es más que una suma:

      x = [0,0+0,5, 1,3333+0,5], e
      y = [0,0-0,5, 0,6666-0,5],
      

      obtenemos que,

      x = [+0,5, +1,8333]
      y = [-0,5, +0,1666]
      

      Recalculando el fractal con estas nuevas dimensiones, obtendremos una imagen de un área reducida 3 veces de la original y centrada en el punto (0,5, -0,5). Como el área es más pequeña que la original, los valores de dx_up y dy_up se ven reducidos. Esto implica que nuestra imagen permitirá mostrar más información al someter estas nuevas dimensiones a la misma resolución gráfica.

5. Si el lector tiene experiencia en programar aplicaciones interactivas, entonces podemos crear un programa que permita al usuario elegir el área a investigar mediante la creación de un rectángulo pequeño en la imagen. Por ejemplo, al pinchar el botón izquierdo del ratón en la imagen, podría comenzar a crear un rectángulo arrastrándolo. Dicho rectángulo puede resultar al soltar tal botón izquierdo.

   Este rectángulo ya contiene las nuevas dimensiones de la imagen, para realizar el zoom. Lo único que tendríamos que hacer es convertir los valores de los píxeles a su representación en coordenadas (matemáticas) del plano complejo.

6. Aún no hemos visto la forma de manipular colores; esto se trata en el siguiente capítulo 4. De todas formas, es una parte importante de la estética de la imagen.Un método popular se basa en dar un color a un píxel el cual representa un número complejo (coordenada) que no pertenece al conjunto del fractal. El criterio de dar un color u otro se basa en la distancia de tal coordenada desde su posición anterior (dentro del conjunto del fractal) a su posición actual (fuera del conjunto del fractal). Restringiendo tal distancia a un valor entre el intervalo: [0,00, 1,00], podemos usar un mapa de colores. Con este mapa podemos asignar o calcular un color, de acuerdo a nuestra gama de colores, según un valor entre el intervalo anterior. El tema de mapa de colores es tratado en el siguiente capítulo 4.

   Podemos hacer el siguiente cálculo para obtener un valor, a modo de parámetro para nuestro mapa de colores, en el intervalo [0,00, 1,00]:

   mapa( r / d ), donde d ≥ r

   d es la distancia entre las dos últimas coordenadas, y

   r es una constante que indica el radio del fractal.

   Por ejemplo,

   

   Si el lector no tiene suficientes conocimientos para usar colores, entonces es recomendable pasar al siguiente capítulo 4, y luego volver a este ejercicio, cuando sepa la forma de manipular colores.