El algoritmo de relleno por inundación (floodfill) es un método recursivo utilizado para rellenar áreas en una representación de píxeles con un color específico. Tradicionalmente, este proceso requiere una pila de datos para gestionar las coordenadas de los píxeles de origen, lo que implica un consumo de memoria adicional. Sin embargo, existe una variante optimizada que elimina la necesidad de estructuras de datos dinámicas como la pila, utilizando en su lugar un automata finito.
Esta técnica, descrita por Nils M. Holm en 2023, permite codificar los estados del proceso directamente en los valores de color de la imagen. Al reservar 16 colores específicos, se pueden representar las direcciones de navegación y el estado actual de cada píxel. El algoritmo funciona iterando por los píxeles adyacentes, marcando cada uno con un estado que indica su dirección de origen y la siguiente dirección a explorar. Cuando no quedan opciones disponibles, el píxel se rellena con el color final y se retrocede hasta el punto de inicio.
La complejidad temporal de este método es lineal, O(n), donde n es el número de píxeles a rellenar, manteniendo la eficiencia del enfoque recursivo estándar. La implementación se puede extender a rejillas hexagonales o espacios de voxels, aunque esto requiere un mayor número de colores disponibles. Esta variante es particularmente útil en entornos con recursos limitados, como sistemas BASIC antiguos con poca memoria de programa y niveles de anidación de subrutinas restringidos, donde la eliminación de la pila permite una ejecución más eficiente y predecible.
