stringtranslate.com

Relleno de inundación

Relleno de inundación recursivo con 4 direcciones

El relleno de inundación , también llamado relleno de semilla , es un algoritmo de inundación que determina y altera el área conectada a un nodo dado en una matriz multidimensional con algún atributo coincidente. Se utiliza en la herramienta de relleno de "cubeta" de los programas de pintura para rellenar áreas conectadas de colores similares con un color diferente, y en juegos como Go y Buscaminas para determinar qué piezas se despejan. Una variante llamada relleno de límites utiliza los mismos algoritmos pero se define como el área conectada a un nodo dado que no tiene un atributo particular. [1]

Tenga en cuenta que el relleno por inundación no es adecuado para dibujar polígonos rellenos, ya que omitirá algunos píxeles en las esquinas más agudas. [2] En su lugar, consulte Regla par-impar y Regla distinta de cero .

Los parámetros del algoritmo

Relleno de inundación recursivo con 8 direcciones

El algoritmo tradicional de relleno por inundación toma tres parámetros: un nodo de inicio, un color de destino y un color de reemplazo. El algoritmo busca todos los nodos de la matriz que estén conectados al nodo de inicio por una ruta del color de destino y los cambia al color de reemplazo. Para un relleno de límites, en lugar del color de destino, se proporcionaría un color de borde.

Para generalizar el algoritmo de la forma habitual, las siguientes descripciones tendrán en cambio dos rutinas disponibles. [3] Una llamada Insideque devuelve verdadero para los puntos no rellenos que, por su color, estarían dentro del área rellena, y otra llamada Setque rellena un píxel/nodo. Cualquier nodo que Setla haya llamado ya no debe ser Inside.

Dependiendo de si consideramos conectados o no los nodos que se tocan en las esquinas, tenemos dos variantes: de ocho y de cuatro vías respectivamente.

Implementación recursiva basada en pila (de cuatro vías)

La implementación de relleno de inundación de cuatro vías recursiva basada en pila implícita más antigua conocida es la siguiente: [4] [5] [6] [7]

Relleno de inundación (nodo): 1. Si el nodo no está dentro, retorna. 2. Establezca el nodo 3. Realice el relleno por inundación un paso al sur del nodo . 4. Realice el relleno por inundación un paso al norte del nodo . 5. Realice el relleno por inundación un paso al oeste del nodo . 6. Realice el relleno por inundación un paso al este del nodo. 7. Devolución.

Aunque es fácil de entender, la implementación del algoritmo utilizado anteriormente no es práctica en lenguajes y entornos donde el espacio de pila está severamente limitado (por ejemplo, microcontroladores ).

Trasladar la recursión a una estructura de datos

Al mover la recursión a una estructura de datos (ya sea una pila o una cola ), se evita un desbordamiento de pila . Es similar a la solución recursiva simple, excepto que en lugar de realizar llamadas recursivas, empuja los nodos a una pila o cola para su consumo, y la elección de la estructura de datos afecta el patrón de proliferación:

Relleno de inundación (nodo): 1. Establezca Q en la cola o pila vacía. 2. Añade un nodo al final de Q. 3. Mientras Q no esté vacío: 4. Establezca n igual al primer elemento de Q.5. Retire el primer elemento de Q. 6. Si n está dentro : Establezca n y agregue el nodo al oeste de n al final de Q. Añade el nodo al este de n al final de Q. Añade el nodo al norte de n al final de Q. Añade el nodo al sur de n al final de Q. 7. Continúa haciendo bucle hasta que se agote Q. 8. Devolución.

Otras optimizaciones potenciales

Ventajas

Desventajas

Relleno de tramos

Relleno de línea de escaneo utilizando una pila para almacenamiento

Es posible optimizar aún más las cosas trabajando principalmente con intervalos, una fila con una constante y. El primer ejemplo completo publicado funciona según el siguiente principio básico. [1]

  1. A partir de un punto inicial, rellene los puntos izquierdo y derecho. Lleve un registro del punto de relleno más a la izquierda lxy del punto de relleno más a la derecha rx. Esto define el intervalo.
  2. Escanee desde lxarriba rxy abajo del punto semilla, buscando nuevos puntos semilla para continuar.

Como optimización, el algoritmo de escaneo no necesita reiniciarse desde cada punto inicial, sino solo desde aquellos que se encuentran al comienzo del siguiente tramo. El uso de una pila explora primero la profundidad de los tramos, mientras que una cola explora primero la amplitud de los tramos.

fn rellenar ( x , y ): Si no está dentro de ( x , y ), entonces regresa sea ​​s = nueva pila o cola vacía Agregue ( x , y ) a s mientras s no esté vacío: Eliminar un ( x , y ) de s sea lx = x mientras Dentro de ( lx - 1, y ): Establecer ( lx - 1, y ) lx = lx - 1 mientras Dentro de ( x , y ): Conjunto ( x , y ) x = x + 1 scan ( lx , x - 1, y + 1, s ) scan ( lx , x - 1, y - 1, s )función de escaneo ( lx , rx , y , s ): sea ​​span_added = falso para x en lx .. rx : si no Dentro ( x , y ): span_added = false de lo contrario si no span_added : Agregar ( x , y ) a s  span_added = true

Con el tiempo se realizaron las siguientes optimizaciones:

El relleno final, que combina escaneo y relleno, se publicó en 1990. En formato de pseudocódigo: [8]

fn rellenar ( x , y ): Si no está dentro de ( x , y ), entonces regresa sea ​​s = nueva cola o pila vacía Suma ( x , x , y , 1) a s Suma ( x , x , y - 1, -1) a s mientras s no esté vacío: Eliminar un ( x1 , x2 , y , dy ) de s sea x = x1 si Dentro de ( x , y ): mientras Dentro ( x - 1, y ): Establecer ( x - 1, y ) x = x - 1 si x < x1 : Sumar ( x , x1 - 1, y - dy , - dy ) a s mientras x1 <= x2 : mientras Dentro de ( x1 , y ): Establecer ( x1 , y ) x1 = x1 + 1 si x1 > x : Sumar ( x , x1 - 1, y + dy , dy ) a s si x1 - 1 > x2 : Sumar ( x2 + 1, x1 - 1, y - dy , - dy ) a s  x1 = x1 + 1 mientras x1 < x2 y no Dentro ( x1 , y ): x1 = x1 + 1 x = x1

Ventajas

Desventajas

Añadiendo compatibilidad con relleno de patrones

Dos formas comunes de hacer que los algoritmos basados ​​en píxeles y en intervalos admitan el relleno de patrones son usar un color único como relleno simple y luego reemplazarlo con un patrón o hacer un seguimiento (en una matriz booleana 2D o como regiones) de los píxeles que se han visitado, utilizándolo para indicar que los píxeles ya no se pueden rellenar. Inside debe devolver falso para dichos píxeles visitados. [3]

Relleno de teoría de grafos

Algunos teóricos aplicaron la teoría de grafos explícita al problema, tratando los intervalos de píxeles, o agregados de los mismos, como nodos y estudiando su conectividad. El primer algoritmo de teoría de grafos publicado funcionaba de manera similar al llenado de intervalos, mencionado anteriormente, pero tenía una forma de detectar cuándo duplicaría el llenado de intervalos. [9] Desafortunadamente, tenía errores que impedían que completara algunos rellenos. [10] Más tarde se publicó un algoritmo corregido con una base similar en la teoría de grafos; sin embargo, altera la imagen a medida que avanza, para bloquear temporalmente los bucles potenciales, lo que complica la interfaz programática. [10] Un algoritmo publicado más tarde dependía de que el límite fuera distinto de todo lo demás en la imagen y, por lo tanto, no es adecuado para la mayoría de los usos; [11] [3] también requiere un bit adicional por píxel para la contabilidad. [3]

Ventajas

Desventajas

Relleno basado en caminatas (método de memoria fija)

Existe un método que básicamente no utiliza memoria para las cuatro regiones conectadas, ya que simula ser un pintor que intenta pintar la región sin acorralarse. Este también es un método para resolver laberintos . Se examinan los cuatro píxeles que forman el límite principal para ver qué acción se debe tomar. El pintor podría encontrarse en una de varias situaciones:

  1. Se rellenan los cuatro píxeles del límite.
  2. Se rellenan tres de los píxeles del límite.
  3. Se rellenan dos de los píxeles del límite.
  4. Se rellena un píxel de límite.
  5. Los píxeles de límite cero se rellenan.

Cuando se debe seguir un camino o un límite, se utiliza la regla de la mano derecha. El pintor sigue la zona colocando su mano derecha en la pared (el límite de la zona) y avanzando por el borde de la zona sin retirar la mano.

En el caso n.° 1, el pintor pinta (rellena) el píxel sobre el que se encuentra y detiene el algoritmo.

En el caso n.° 2, existe un camino que sale del área. Pinta el píxel sobre el que se encuentra el pintor y muévete en la dirección del camino abierto.

En el caso n.° 3, los dos píxeles de contorno definen un camino que, si pintamos el píxel actual, puede impedirnos volver al otro lado del camino. Necesitamos una "marca" que defina dónde estamos y en qué dirección nos dirigimos para ver si alguna vez volvemos exactamente al mismo píxel. Si ya creamos una "marca" de este tipo, conservamos nuestra marca anterior y pasamos al siguiente píxel siguiendo la regla de la mano derecha.

Se utiliza una marca para el primer límite de 2 píxeles que se encuentra para recordar dónde comenzó el pasaje y en qué dirección se movía el pintor. Si se encuentra la marca nuevamente y el pintor se mueve en la misma dirección, entonces el pintor sabe que es seguro pintar el cuadrado con la marca y continuar en la misma dirección. Esto se debe a que (a través de algún camino desconocido) se pueden alcanzar los píxeles del otro lado de la marca y pintarlos en el futuro. La marca se elimina para su uso futuro.

Si el pintor encuentra la marca pero va en una dirección diferente, entonces se ha producido algún tipo de bucle, que ha hecho que el pintor vuelva a la marca. Este bucle debe eliminarse. Se recoge la marca y el pintor procede entonces en la dirección indicada previamente por la marca utilizando una regla de la mano izquierda para el límite (similar a la regla de la mano derecha pero utilizando la mano izquierda del pintor). Esto continúa hasta que se encuentra una intersección (con tres o más píxeles de límite abiertos). Siguiendo utilizando la regla de la mano izquierda, el pintor busca ahora un pasaje simple (formado por dos píxeles de límite). Al encontrar este camino de límite de dos píxeles, se pinta ese píxel. Esto rompe el bucle y permite que el algoritmo continúe.

En el caso n.° 4, debemos verificar si las esquinas opuestas conectadas por 8 están llenas o no. Si una o ambas están llenas, se crea una intersección de múltiples caminos y no se puede llenar. Si ambas están vacías, se puede pintar el píxel actual y el pintor puede moverse siguiendo la regla de la mano derecha.

El algoritmo sacrifica tiempo por memoria. Para formas simples es muy eficiente. Sin embargo, si la forma es compleja y tiene muchas características, el algoritmo pasa una gran cantidad de tiempo trazando los bordes de la región para intentar asegurarse de que todo se pueda pintar.

En 1994 se publicó un algoritmo de caminata. [12]

Pseudocódigo

Esta es una implementación en pseudocódigo de un algoritmo óptimo de relleno de memoria fija escrito en inglés estructurado:

Las variables
El algoritmo
NOTA: Todas las direcciones (delante, atrás, izquierda, derecha) son relativas acur-dir
Establezca cur en el píxel inicialEstablezca cur-dir en la dirección predeterminadaBorrar mark y mark2 (establecer valores en nulos)Establezca backtrack y findloop en falsomientras el píxel frontal esté vacío seguir adelanteterminar mientrasSaltar al INICIOBUCLE PRINCIPAL: seguir adelante Si el píxel derecho está dentro , entonces  si backtrack es verdadero y findloop es falso y el píxel frontal o el píxel izquierdo están dentro , entonces Establezca findloop en verdadero terminar si Gire a la derechaPINTAR: seguir adelante terminar siCOMENZAR: Establezca  el recuento en el número de píxeles adyacentes no diagonales llenos (frontal/posterior/izquierdo/derecho SOLAMENTE) si  el recuento  no es 4 , entonces  haga Gire a la derecha mientras el píxel frontal está dentro Gire a la izquierda mientras que el píxel frontal no está dentro del extremo si  el conteo de interruptores  caso 1 Si el retroceso es verdadero entonces Establezca findloop en verdadero De lo contrario, si findloop es verdadero , entonces  si mark es nulo , entonces marca de restauración fin si  de lo contrario si el píxel frontal izquierdo y el píxel posterior izquierdo están ambos dentro entonces marca clara establecer cur Saltar a PINTAR terminar si caso final caso 2 Si el píxel posterior no está dentro , entonces  si el píxel frontal izquierdo está dentro , entonces marca clara establecer cur Saltar a PINTAR fin si  de lo contrario si la marca no está establecida entonces establecer marca para cur Establezca mark-dir en cur-dir Marca clara 2 Establezca findloop y backtrack en falso de lo contrario,  si mark2 no está configurado , entonces  si cur está en mark , entonces  si cur-dir es el mismo que mark-dir, entonces marca clara Giro de vuelta establecer cur Saltar a PINTAR demás Establecer retroceso como verdadero Establezca findloop en falso Establezca cur-dir en mark-dir fin si  de lo contrario si findloop es verdadero entonces Establezca mark2 en cur Establezca mark2-dir en cur-dir fin si  de lo contrario  si cur está en mark entonces Establezca cur en mark2 Establezca cur-dir en mark2-dir marca clara y marca2 Establecer retroceso en falso Giro de vuelta establecer cur Saltar a PINTAR De lo contrario, si cur está en mark2 , entonces establecer marca para cur Establezca cur-dir y mark-dir en mark2-dir Marca clara 2 fin si  fin si  fin si caso final caso 3 marca clara establecer cur Saltar a PINTAR caso final caso 4 establecer cur hecho caso final interruptor finalFin del BUCLE PRINCIPAL

Ventajas

Desventajas

Implementaciones de vectores

La versión 0.46 de Inkscape incluye una herramienta de relleno con cubeta, que ofrece un resultado similar al de las operaciones de mapa de bits habituales y que, de hecho, utiliza una: se renderiza el lienzo, se realiza una operación de relleno con inundación en el área seleccionada y, a continuación, el resultado se traza hasta una ruta. Utiliza el concepto de condición de contorno .

Véase también

Enlaces externos

Referencias

  1. ^ abc Smith, Alvy Ray (1979). Tint Fill . SIGGRAPH '79: Actas de la sexta conferencia anual sobre gráficos por computadora y técnicas interactivas. págs. 276–283. doi :10.1145/800249.807456.
  2. ^ ab Ackland, Bryan D; Weste, Neil H (1981). El algoritmo de bandera de borde: un método de relleno para pantallas de escaneo rasterizado . IEEE Transactions on Computers (volumen: C-30, número: 1). págs. 41–48. doi :10.1109/TC.1981.6312155.
  3. ^ abcdefghij Fishkin, Kenneth P; Barsky, Brian A (1985). Un análisis y algoritmo para la propagación del relleno . Imágenes generadas por computadora: el estado del arte. Actas de la interfaz gráfica '85. págs. 56–76. doi :10.1007/978-4-431-68033-8_6.
  4. ^ Newman, William M; Sproull, Robert Fletcher (1979). Principios de gráficos informáticos interactivos (2.ª ed.). McGraw-Hill. pág. 253. ISBN 978-0-07-046338-7.
  5. ^ Pavlidis, Theo (1982). Algoritmos para procesamiento de gráficos y imágenes . Springer-Verlag. pag. 181.ISBN​ 978-3-642-93210-6.
  6. ^ abcdefghi Levoy, Marc (1982). Algoritmos de inundación de área . Notas del curso de animación por computadora bidimensional de SIGGRAPH 1981.
  7. ^ Foley, JD; van Dam, A; Feiner, SK; Hughes, SK (1990). Gráficos por computadora: principios y práctica (2.ª ed.). Addison–Wesley. págs. 979–982. ISBN 978-0-201-84840-3.
  8. ^ Heckbert, Paul S (1990). "IV.10: Un algoritmo de llenado de semillas". En Glassner, Andrew S (ed.). Graphics Gems . Academic Press. págs. 275–277. ISBN 0122861663.
  9. ^ ab Lieberman, Henry (1978). Cómo colorear en un libro para colorear . SIGGRAPH '78: Actas de la quinta conferencia anual sobre gráficos por computadora y técnicas interactivas. págs. 111–116. doi :10.1145/800248.807380.
  10. ^ abc Shani, Uri (1980). Relleno de regiones en imágenes raster binarias: un enfoque de teoría de grafos . SIGGRAPH '80: Actas de la 7.ª conferencia anual sobre gráficos por ordenador y técnicas interactivas. págs. 321–327. doi :10.1145/800250.807511.
  11. ^ ab Pavlidis, Theo (1981). Relleno de contornos en gráficos rasterizados . SIGGRAPH '81: Actas de la octava conferencia anual sobre gráficos por computadora y técnicas interactivas. págs. 29–36. doi :10.1145/800224.806786.
  12. ^ Henrich, Dominik (1994). Relleno de regiones con uso eficiente del espacio en gráficos rasterizados . The Visual Computer. págs. 205–215. doi :10.1007/BF01901287.