Algoritmo de relleno por difusión

Este artículo es una traducción del equivalente en inglés, y aún no está completo.

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

Algoritmo recursivo de 8 direcciones.

El algoritmo de relleno en programas de dibujo 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

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

The algorithm can be sped up by filling lines. Instead of pushing each potential future pixel coordinate into the stack, it inspects the neighbour lines (previous and next) to find adjacent segments that may be filled in a future pass; the coordinates (either the start or the end) of the line segment are pushed on the stack. In most of cases this scanline algorithm is at least an order of magnitude faster than the per-pixel one.

Vector implementations

The current development version of Inkscape (which will become version 0.46) includes a bucket fill tool, giving output similar to ordinary bitmap operations and indeed using one: the canvas is rendered, a flood fill operation is performed on the selected area and the result is then traced back to a path.

Véase también

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

Enlaces externos

• Source code for implementing the flood fill algorithm in Java, C, and OCaml.
• Sample implementations for recursive and non-recursive, classic and scanline flood fill, by Lode Vandevenn.
• C implementation of Flood/Seed Fill Algorithm from Graphics Gems; BSD(ish) license, by Paul Heckbert.