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

De Wikilibros, la colección de libros de texto de contenido libre.
Ir a la navegación Ir a la búsqueda

Definición del algoritmo[editar]

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:
Menger 0.PNG Menger 1.PNG Menger 2.PNG Menger 3.PNG Menger 4.PNG
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);
}