Para esta primera tarea elegí explicar el algoritmo de Relleno, en inglés Floodfill, este algoritmo sirve para rellenar áreas, nosotros mismos hemos utilizado este algoritmo en programas como Paint que vendría siendo la función que hace el "bote de pintura", o en el buscaminas, entre muchos otros juegos.
Hay varias maneras de llevar acabo la función de rellenar, es decir hay soluciones distintas para un mismo problema, pero como ya bien sabemos no todas son óptimas.
Para esta tarea elegí explicar el algoritmo Recursivo que ofrece la solución pero no es el mejor para resolver el problema, ya que falla cuando se tiene un arreglo de datos demasiado grande ocurre lo que se llama "Desbordamiento" así se dice cuando el puntero de la pila aumenta mas que el límite máximo del área a cubrir.
Para empezar a cubirir el área se requieren 3 parámetros que debe de recibir la función: el color con el que se rellenará, el color anterior, y el punto de partida.
Aparte de la manera óptima para el algoritmo y la que no lo es hay algunas variantes, en este caso en la forma recursiva explicaré como es que se puede hacer diferentes tipos de relleno dependiendo de la funcion que queremos que realice.
Y como dicen que una imagen vale mas que mil palabras aqui les muestro dos animaciones que obtuve de "Wikipedia".
Este es algoritmo recursivo de 4 direcciones:
Pseudocódigo
y este otro de 8 direcciones:
Pseudocódigo
La otra forma que dije anteriormente es la óptima, esta se trata de tener una cola vacía a la que se le van agregando coordenadas de pixeles, empezando por algún pixel random o que el usuario elija. No se usa recursión es un método más elaborado pero con el se llega a soluciones más rapidas sin tantas llamadas alguna función además que no presenta el problema de "desbordamiento", como el de recursión.
Esta es la animación que nos muestra su manera de funcionar:
Espero pronto poder agregarle esta funcionalidad a mi código de Paint, esperaría que para la próxima semana estarles mostrando mi código en javascript listo para probarse(tratare de hacerlo de las dos formas recursivo o sin recursión).
Referencias:
