Implementación de algoritmos/Miscelánea/Alfombra de Sierpinski
Apariencia
Definición del algoritmo
[editar]La construcción de la alfombra de Sierpinski se define de forma recursiva:
- Comenzamos con un cuadrado.
- El cuadrado se corta en 9 cuadrados congruentes, y eliminamos el cuadrado central.
- 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
[editar]/**
* 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
[editar]/*
* 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.
}