Algoritmo de relleno

Esta historia parte de un pequeño proyecto de antaño en el que intenté implementar la herramienta de relleno de Paint o Photoshop.

Estamos hablando de un algoritmo de relleno por difusión: el objetivo es pasar por todos los puntos no coloreados partiendo de uno arbitrario y la solución se antojaba sencilla: un algoritmo de backtracking. 

Estuve cerca de lograrlo pero cuando la superficie a rellenar era medianamente grande, el programa se colgaba por desbordamiento de pila.

El problema es que, al tratarse de una función recursiva, con cada paso que daba había que guardar en la pila el punto anterior, y si el espacio es grande podemos estar hablando de miles o millones de pasos. Esta información se guarda en la pila de llamadas, una zona de memoria especialmente rápida... y pequeña.

La solución es muy fácil: convertir la función recursiva en iterativa, y guardar cada punto a explorar dentro de un contenedor de pila (QStack en la biblioteca Qt), cuyos datos se almacenan en el heap, mucho más grande que la pila de llamadas.

Vista del programa.
Tenemos aquí el algoritmo implementado con un programa basado en Qt para verlo funcionando, incluye el código fuente y el ejecutable para Windows x64.

Comentarios

Publicar un comentario

Entradas populares de este blog

Cifrado de Vernam

Imagen
El cifrado de Vernam es un algoritmo de encriptación en flujo , es decir, consiste en combinar cada uno de los bits del mensaje con otro bit que actúa como clave de cifrado. Numerosos protocolos criptográficos, como el sistema WEP que utilizan nuestros routers o el A5/1 que se usa en las redes de teléfonos móviles, están basados en el cifrado de Vernam. Este procedimiento requiere, a diferencia de los sistemas de encriptación por bloques, una clave que sea tan larga como el mensaje . Entonces necesitamos alguna forma de obtener una clave pseudoaleatoria que pueda tener una longitud muy larga, y variable. Una forma de conseguir una clave fiable con facilidad, es utilizar un LFSR (Linear Feedback Shift Register), o Registro de Desplazamiento con Retroalimentación lineal. No nos asustemos por ese nombre, es lo más fácil del mundo: Fuente: Wikipedia . Un registro de desplazamiento es un conjunto de bits que tienen la capacidad de moverse a través de las celdas en las que
Leer más

Problema de las N reinas

Imagen
El problema de las ocho reinas es un juego que consiste en colocar ocho reinas en un ajedrez sin que se amenacen entre sí. La solución a este problema se encuentra con un algoritmo de backtracking , que consiste en asignar una fila a cada reina, y progresivamente colocar cada reina en una posición diferente. Si una reina es amenazada en cualquier casilla de su fila, la retiramos y colocamos la reina anterior en otra posición. El programa termina cuando se ha conseguido colocar a todas las reinas en posiciones seguras. Aquí dejo una propuesta dinámica para N reinas, en lenguaje C: >>  Descargar reinas.c  << Mejorando el algoritmo Tiempo después de publicar originalmente este post, estudié que éste es realmente un problema de satisfacción de restricciones . Resolver un problema NP completo puede costarnos mucho tiempo, ya que el espacio de búsqueda crece enormemente respecto al tamaño del problema. La aproximación por backtracking  "a pelo&quo
Leer más