Recursividad - Triángulo de Sierpinski

Triángulo de Sierpinski 

La recursividad está presente en todo, incluso en el mundo real y tangible donde vivimos. Por ejemplo los átomos, los átomos de un mismo elemento son idénticos, y estos a su vez, están presentes miles de millones de veces para formar algún material, podemos decir entonces que son estructuras que se repiten muchas veces para formar una estructura mas grande. 

Otros ejemplos son por ejemplo las hojas de los árboles o los copos de nieve, son estructuras que se repiten varias veces a distintas escalas. A estos patrones se les conoce como fractales.

Existe un fractal muy curioso llamado triángulo de Sierpinski, el cual presenta una característica muy interesante, es una figura que a medida que más se repiten los patrones, su área tiende a 0.

Otro punto importante de éste fractal, y que como programadores nos concierne un poco más que su área, es que su construcción puede llevarse a cabo mediante un proceso recursivo. 

Antes de entrar al aspecto programático, haciendo un pequeño análisis de este fractal, podemos darnos cuenta que su construcción es bastante sencilla; partiendo del triangulo  equilátero inicial, basta con unir con una linea los 3 puntos medios de cada lado del triangulo, de esa manera el triangulo queda dividido en 4 triángulos mas pequeños de los cuales 3, son similares al triangulo inicial. Si aplicamos el mismo procedimiento a cada uno de los 3 triángulos que obtuvimos en el paso anterior,  tendremos ahora 13 triángulos de los cuales 9 son similares al triangulo inicial, y así sucesivamente.

Aquí es donde entramos nosotros como programadores a elaborar un algoritmo recursivo que nos permita construir este fractal.

Como se mencionaba, basta con tomar el triángulo equilátero inicial, determinar sus puntos medios, y en base a ellos dibujar los 3 triángulos mas pequeños, el proceso se repite en cada uno de los triángulos obtenidos las veces que se desee.

A partir de esa definición podemos construir el algoritmo y posteriormente el código en C# tomando como información de entrada las coordenadas de los vértices y una variable para determinar cuántas veces ha de repetirse el proceso. vert_1 es el vértice izquierdo, vert_2 el de arriba y vert_3 el derecho. p_medio1 es el punto medio de la izquierda, p_medio2 es el punto medio de abajo y p_medio3 el de la derecha.

Algoritmo:

fractal( vert_1, vert_2, vert_3, repe)                    

    Si( repe == 0 )                                       

       dibujar triangulo con las coordenadas              

    Sino                                                  

       calcular p_medio1                                  

       calcular p_medio2                                  

       calcular p_medio3                                  

       fractal(vert_1, p_medio1, p_medio2, repe - 1)      

       fractal(p_medio1, vert_2, p_medio3, repe - 1)      

       fractal(p_medio2, p_medio3, vert_3, repe - 1)      

En esas sencillas lineas se puede resumir la construcción de este particular fractal. Únicamente cabe destacar como se mencionaba en una entrada anterior, que la recursividad funciona en base a una pila de llamadas, y las llamadas empiezan a retornar valores hasta que se llega al caso base, es decir, aquel en el que no es necesario que el método vuelva a llamarse a si mismo. En este caso, dado un triángulo inicial, el método continuaría llamándose a si mismo las veces que sea necesario hasta llegar al caso en que repe es igual a 0, entonces es cuando empezaría a dibujar los triángulos, lógicamente los que corresponden a las últimas llamadas del método, es decir, los triángulos mas pequeños.

En palabras menos complicadas, el método lo único que hace es tomar un triángulo inicial, y dividirlo n veces, hasta el momento que lo tiene dividido las veces necesarias, es cuando comienza a dibujar. 

Ahora bien, pasemos a analizar el código en C#

 private void Triangulo(int x1, int y1, int x2, int y2, int x3, int y3, Graphics g,  int n)

 {

    if (n == 0)

    {

    SolidBrush b = new SolidBrush(Color.Teal);

    Point[] puntos = new Point[3];

    puntos[0] = new Point(x1, y1);

    puntos[1] = new Point(x2, y2);

    puntos[2] = new Point(x3, y3);

    g.FillPolygon(b, puntos);

    }

    else

    {

    int pm1x = (x1 + x2) / 2;

    int pm1y = (y1 + y2) / 2;

    int pm2x = (x1 + x3) / 2;

    int pm2y = (y1 + y3) / 2;

    int pm3x = (x2 + x3) / 2;

    int pm3y = (y2 + y3) / 2;

    Triangulo(x1, y1, pm1x, pm1y, pm2x, pm2y,g,n - 1);

    Triangulo(pm1x, pm1y, x2, y2, pm3x, pm3y, g, n - 1);

    Triangulo(pm2x, pm2y, pm3x, pm3y, x3, y3, g ,n - 1);

    }

 }     

Adjunto el proyecto Sierpinski en Visual C# 2010 
Descargar