Implementación de algoritmos/Miscelánea/Alfombra de Sierpinski

Definición del algoritmo

La construcción de la alfombra de Sierpinski se define de forma recursiva:

1. Comenzamos con un cuadrado.
2. El cuadrado se corta en 9 cuadrados congruentes, y eliminamos el cuadrado central.
3. El paso anterior vuelve a aplicarse recursivamente a cada uno de los 8 cuadrados restantes.

La alfombra de Sierpinski es el límite de este proceso tras un número infinito de iteraciones.

Construcción de la alfombra de Sierpinski:
Paso 1	Paso 2	Paso 3	Paso 4	Paso 5

Implementación en C, C + + y Java

/**
* Decides if a point at a specific location is filled or not.
* @param x is the x coordinate of the point being checked
* @param y is the y coordinate of the point being checked
* @param width is the width of the Sierpinski Carpet being checked
* @param height is the height of the Sierpinski Carpet being checked
* @return 1 if it is to be filled or 0 if it is not
*/
int isSierpinskiCarpetPixelFilled(int x, int y, int width, int height)
{
	// base case 1 of 2
	if ((x <= 0)||(y <= 0)||(x>=width)||(y>=height)) //top row or left column or out of bounds should be full
	{
		return 1;
	}
	{
		/*
		If the grid was split in 9 parts, what part(x2,y2) would x,y fit into?
		*/
		int x2 = x * 3 / width; // an integer from 0..2 inclusive
		int y2 = y * 3 / height; // an integer from 0..2 inclusive

		// base case 2 of 2
		if (x2 == 1 && y2 == 1) // if in the center square, it should be empty
			return 0;

		// general case

		/* offset x and y so it becomes bounded by 0..width/3 and 0..height/3
		and prepares for recursive call
		some offset is added to make sure the parts have all the correct size when
		width and height isn't divisible by 3
		*/
		x -= (x2 * width+2) / 3; 
		y -= (y2 * height+2) / 3;
		width = (width +2-x2)/3;
		height = (height+2-y2)/3;
	}

	return isSierpinskiCarpetPixelFilled(x, y, width, height);
}

Versión simplificada

/*
* Verificar si un punto en un lugar específico está lleno o no. Esto funciona mediante iteración, primero verificando si
* el píxel está vacío en cuadrados sucesivamente más grandes o no puede estar en el centro de ningún cuadrado más grande.
* x es la coordenada x del punto que esta siendo verificado con cero siendo el primer píxel e 
* y es la coordenada y del punto que esta siendo verificado con cero siendo el primer píxel
* 1 es en caso de estar lleno o 0 al estar vacío.
*/
int isSierpinskiCarpetPixelFilled(int x, int y)
{
    while (x > 0 || y > 0) // cuando cualquiera de estos llega a cero, se determina que el píxel está en el borde 
                               // en ese nivel cuadrado y debe llenarse
    {
        if (x % 3 == 1 && y % 3 == 1) //verifica si el píxel está en el centro para el nivel cuadrado actual
            return 0;
        x /= 3; // x e y se decrementan para verificar el siguiente nivel cuadrado más grande
        y /= 3;
    }
    return 1; // si todos los niveles cuadrados posibles están marcados y el píxel no está determinado
                   // como uno vacío, entonces debe estar lleno.
}