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.

[IMAGEN]: Figura 3 - Koch n=0
Figura 3 - Koch n=0

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.

[IMAGEN]: Figura 4 - Koch n=1
Figura 4 - Koch n=1

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.

[IMAGEN]: Figura 5 - Koch n=2
Figura 5 - Koch n=2

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

A0 → Avanzar

An+1 → AnIAnDDAnIAn

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 A0. 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 )
  1. Declarar: Cursor como un punto y un ángulo
  2. Inicializar Cursor:
  3. Cursor.punto ← Punto_Inicial
  4. Cursor.ángulo ← 0
  5. Dibujar_Koch( Cursor, Longitud, Número_Iteraciones )
  6. 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 )
  1. Si N = 0 entonces, // A(vanzar)
  2. Cursor.punto ← Avanzar( Cursor, Dist )
  3. Terminar
  4. Si no, entonces, // Recursividad: A→AIADDAIA
  5. Dibujar_Koch( Cursor, Dist/3, N-1 ) // A
  6. Cursor.ángulo ← Cursor.ángulo + π/3 // I
  7. Dibujar_Koch( Cursor, Dist/3, N-1 ) // A
  8. Cursor.ángulo ← Cursor.ángulo - π*2/3 // DD
  9. Dibujar_Koch( Cursor, Dist/3, N-1 ) // A
  10. Cursor.ángulo ← Cursor.ángulo + π/3 // I
  11. Dibujar_Koch( Cursor, Dist/3, N-1 ) // A
  12. 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 )
  1. Declarar P como un punto: (x,y)
  2. P.x ← Cursor.punto.x + D*cos( Cursor.ángulo )
  3. P.y ← Cursor.punto.y + D*sen( Cursor.ángulo )
  4. Dibujar_Línea( Cursor.punto.x, Cursor.punto.y, P.x, P.y )
  5. 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 Nn sea el número de tramos, según la iteración n, y Ln, 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, dcap, 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 dcap es el exponente para Ln que equivale a Nn.

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 → IAnDDAnDDAn, con un ángulo de 60° (=π/3 radianes) para formar el triángulo equilátero a partir de la "base".
    A0 → Avanzar,
    An+1 → AnIAnDDAnIAn,

    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.

    [IMAGEN]: Copo de Nieve - N=5
    Copo de Nieve - N=5

    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. An+1 para que la punta de la curva de Koch se oriente hacia la derecha. Es decir,
      An+1 → AnDAnIIAnDAn, 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 → IAnIIAnIIAn, a partir del "pico" del triángulo invertido.

    [IMAGEN]: Anti-Copo de Nieve - N=5
    Anti-Copo de Nieve - N=5

    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 → AnDAnDAnDAnDAnDAn, describe un hexágono regular,
      A0 → Avanzar,
      An+1 → AnIAnDAn,
      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 A4.

      [IMAGEN]: Isla de Gosper - N = 4
      Isla de Gosper - N = 4
    2. Fractal de Cesàro,
      B → AnIAnIAnIAn, con un ángulo de 90° (=π/2 radianes), describe un cuadrado,
      A0 → Avanzar,
      An+1 → AnIAnDDAnIAn,
      Los giros de An 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 A4.

      [IMAGEN]: Fractal de Cesàro - N=4
      Fractal de Cesàro - N=4
  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,
      A0 → Avanzar,
      An+1 → An[IAn]An[DAn]An,
      Á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 A6.

      [IMAGEN]: Árbol - N=6
      Árbol - N=6
    2. Fractal de Hielo, basado en un triángulo,
      B → IAnDDAnDDAn, con un ángulo de 60° para formar el triángulo equilátero,
      A0 → Avanzar,
      An+1 → AnAnAnIIAnDDDAnIIAnDDDAnIIAnAnAn,
      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 A4.

      [IMAGEN]: Fractal de Hielo - N=4
      Fractal de Hielo - N=4
    3. Fractal de Hielo, basado en un triángulo,
      B → AnIIAnIIAn, 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.

      [IMAGEN]: Fractal de Hielo - N=4
      Fractal de Hielo - N=4
    4. Fractal de Hielo, basado en un cuadrado,
      B → AnIAnIAnIAn, con un ángulo de 90° (=π/2 radianes), describe un cuadrado regular,
      A0 → Avanzar,
      An+1 → AnAnIAnDDAnIAnAn,
      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 A4.

      [IMAGEN]: Fractal de Hielo - N=4
      Fractal de Hielo - N=4
    5. Fractal de Hielo, basado en un cuadrado,
      B → AnDAnDAnDAn, 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.

      [IMAGEN]: Fractal de Hielo - N=4
      Fractal de Hielo - N=4
    6. Árbol con ramas y hojas,
      A0 → Avanzar,
      An+1 → AnAn[IAn][DAn],
      Á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 A7.

      [IMAGEN]: Árbol - N=7
      Árbol - N=7
  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:
    A0 → Avanzar,
    E0 → Avanzar,
    An+1 → IEnAnDAnDEnIAn, con un ángulo de giro de 90° (= π/2 radianes), y
    En+1 → AnDEnIAnIAnEnD

    Como pueden observar, En+1 invierte el orden de la regla de An+1 y luego cambia todos los giros I y D a D e I, respectivamente.

    Para A1, la regla es simplemente: IE0A0DA0DE0IA0, como E0 es igual a A0, entonces la regla es equivalente a: IA0A0DA0DA0IA0
    Para A2, la regla se convierte en: IE1A1DA1DE1IA1
    Esta regla se expandirá a: I A0DE0IA0IA0E0D IE0A0DA0DE0IA0 D A0DE0IA0IA0E0D D IE0A0DA0DE0IA0 I A0DE0IA0IA0E0D
  7. Cree un programa para que trace cada uno de los siguientes fractales:
    1. Curva basada en Peano,
      A0 → Avanzar, y
      An+1 → IEnAnDAnDEnIAn, 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 A5.

      [IMAGEN]: Curva basada en Peano - N=5
      Curva basada en Peano - N=5
    2. Curva de Peano-Gosper,
      A0 → Avanzar,
      An+1 → AnIEnIIEnDAnDDAnAnDEnI,
      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 A5.

      [IMAGEN]: Curva de Peano-Gosper - N=5
      Curva de Peano-Gosper - N=5
    3. Curva de Peano-Sierpinski,
      A0 → Avanzar/,
      An+1 → IEnDAnDEnI,
      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 A8.

      [IMAGEN]: Curva de Peano-Sierpinski - N=8
      Curva de Peano-Sierpinski - N=8