Algoritmo de relleno por difusión

Algoritmo recursivo de 4 direcciones.

El algoritmo de relleno por difusión, también llamado algoritmo de relleno, o -directamente del inglés- floodfill determina el área formada por elementos contiguos en una matriz multidimensional. Se usa en la herramienta Bote de pintura de programas de dibujo para determinar qué partes de un mapa de bits se van a rellenar de un color (o una textura), y en juegos como el Buscaminas, Puyo Puyo, Lumines y Magical Drop para determinar qué piezas pueden retirarse o seleccionarse.

El algoritmo

[editar]
Algoritmo recursivo de 8 direcciones.

El algoritmo de relleno en programas de dibujo, creado por S. Fazzini, requiere tres parámetros: un nodo inicial, un color para sustituir, y otro de relleno. El algoritmo rastrea todos los nodos que sean del color seleccionado, y a la vez contiguos entre sí y con el inicial, y los sustituye por el color de relleno.

Hay muchas maneras en las que el algoritmo de relleno por difusión puede ser estructurado, pero todas ellas hacen uso de tipos de datos tales como la cola o la pila, explícita o implícitamente. Una implementación del algoritmo de relleno por difusión basada en pilas se define de la siguiente manera (para un arreglo bidimensional):

Flood-fill (node, target-color, replacement-color):
1. Si el color de un node es distinto del que se pretende sustituir, se termina el algoritmo.
2. Asigna el color de node a replacement-color.
3. Se ejecuta de nuevo el algoritmo, usando el nodo situado a la izquierda del presente, y los mismos parámetros de color.
Se ejecuta de nuevo el algoritmo, usando el nodo situado a la derecha del presente, y los mismos parámetros de color.
Se ejecuta de nuevo el algoritmo, usando el nodo situado inmediatamente superior al presente, y los mismos parámetros de color.
Se ejecuta de nuevo el algoritmo, usando el nodo situado inmediatamente inferior al presente, y los mismos parámetros de color.
4. Fin del algoritmo.

Implementaciones alternativas

[editar]

Pese a su facilidad para entender, la implementación del algoritmo mostrada arriba no es práctica en lenguajes y entornos donde el espacio en la pila está severamente limitado (ej. applets Java).

Una implementación explícitamente basada en colas sería como sigue:

Flood-fill (node, target-color, replacement-color):
1. Asignar Q a una cola vacía.
2. Si el color de node no es target-color, retornar.
3. Agregar node al final de Q.
4. Para cada elemento n de Q:
5. Si el color de n es igual a target-color:
6. Asigna el color de n a replacement-color.
7. Si el color del nodo a la derecha de n es target-color, agregar ese nodo al final de Q.
Si el color del nodo a la izquierda de n es target-color, agregar ese nodo al final de Q.
Si el color del nodo arriba de n es target-color, agregar ese nodo al final de Q.
Si el color del nodo debajo de n es target-color, agregar ese nodo al final de Q.
8. Continuar el bucle hasta que Q quede vacía.
9. Retornar.

Implementaciones más prácticas usan un bucle para las direcciones derecha e izquierda como una optimización para evitar el desbordamiento de la pila o de la cola:

Flood-fill (node, target-color, replacement-color):
1. Asignar Q a una cola vacía.
2. Si el color de node no es target-color, retornar.
3. Agregar node a Q.
4. Para cada elemento n de Q:
5. Si el color de n es target-color:
6. Asignar w y e iguales a n.
7. Mover w a la izquierda hasta que el color del nodo a la izquierda de w ya no coincida con target-color.
8. Mover e a la derecha hasta que el color del nodo a la derecha de e ya no coincida con target-color.
9. Asignar el color de los nodos entre w y e a replacement-color.
10. Para cada nodo n entre w y e:
11. Si el color del nodo arriba de n es target-color, agregar ese nodo a Q.
Si el color del nodo debajo de n es target-color, agregar ese nodo a Q.
12. Continuar el bucle hasta que Q quede vacía.
13. Retornar.

Adaptando el algoritmo para que use un arreglo adicional para almacenar la forma de la región permite la generalización para cubrir un relleno "difuso", donde un elemento puede diferenciarse hasta dentro de un umbral específico del símbolo de origen. Al utilizar este arreglo adicional como un canal alfa se permite que los bordes de la región rellena se mezclen con cierta suavidad con la región no rellena.

Scanline Fill

[editar]

El algoritmo puede acelerarse rellenando líneas. En lugar de introducir en la pila la coordenada de cada píxel potencial, se inspeccionan las líneas vecinas (anterior y siguiente) para encontrar segmentos adyacentes que puedan ser rellenados en un pase futuro. Se introducen en la pila las coordenadas de los segmentos de línea (ya sea su inicio o su final). En la mayoría de los casos este algoritmo es por lo menos más rápido en un orden de magnitud que el basado en cada pixel.

Implementaciones vectoriales

[editar]

La versión actualmente en desarrollo del software Inkscape incluye una herramienta de llenado que permite lograr un resultado similar al de las operaciones con mapa de bits. De hecho utiliza uno de los métodos: se renderiza el lienzo, se realiza una operación floodfill en el área seleccionada para luego realizar el camino inverso y así trazar un recorrido.

Véase también

[editar]
  • Boundary fill is an algorithm used for the similar purposes as Flood fill

Enlaces externos

[editar]