¿Cómo funciona la operación de llenado en aplicaciones de pintura?

Question

Todos los programas de pintura, independientemente de cuán simples o complejos sean, vienen con una herramienta de relleno. Esto básicamente reemplaza el color de una región cerrada con otro color. Sé que hay diferentes API para hacer esto, pero estoy interesado en el algoritmo. ¿Cuál sería un algoritmo eficiente para implementar esta herramienta?

Un par de cosas que se me ocurren rápidamente son:

1. imagen convertir en un mapa binario, donde los píxeles del color a ser reemplazados son 1 y todos los demás colores son 0.
2. Encuentra una región cerrada alrededor del punto que desea cambiar de tal manera que todos los píxeles en el interior son 1 y todos los píxeles vecinos son 0.

Sample Image

Answer 1

Muchas implementaciones se realizan como una conquista y recursiva dividir algoritmo. Si haces un rápido Google para "algoritmo de inundación", encontrarás muchos recursos, incluida la excelente página de wikipedia en the topic.

Answer 2

Si quieres un algoritmo eficiente de tiempo que no le importa muy acerca de la eficiencia de memoria, puede hacerlo a través de:

1) mantener una memoria booleano de la cual las células que ya ha visitado: Vis[]

2) mantener una lista de puntos que ya ha visitado, pero todavía no han marcado los vecinos para: Busy[]

3) comienzan ambas cosas lo más vacío

4) añadir el punto de inicio de Busy

5)

while you have a point P in Busy: 
{ 
    for each neighbour N of the point P for which Vis[N] is still false 
    { 
     if appropriate (not crossing the boundary of the fill region) 
     { 
      set Vis[N] to true 
      update the colour of N in the bitmap 
      add N to the end of Busy[] 
     } 
     remove P from Busy[] 
    } 
} 

Answer 3

El algoritmo de relleno por inundación es lo que se usa más comúnmente. La siguiente es una versión ingenua de ella hacia fuera de mi viejo libro de texto universitario, "Computer Graphics con OpenGL" por Hearn panadero, 3ª ed:

void floodFill4 (int x, int y, int fillColor, int interiorColor) 
{ 
    int color; 

    /* Set current color to fillColor, then perform the following operations */ 
    getPixel(x, y, color); 
    if (color == interiorColor) 
    { 
    setPixel(x,y); // Set color of pixel to fillColor. 
    floodFill4(x + 1, y, fillColor, interiorColor); 
    floodFill4(x - 1, y, fillColor, interiorColor); 
    floodFill4(x, y + 1, fillColor, interiorColor); 
    floodFill4(x, y - 1, fillColor, interiorColor); 
    } 
} 

Para grandes imágenes, sin embargo, lo anterior probablemente le dará una pila -el error de desbordamiento debido a la recurrencia de cada píxel. A menudo, este algoritmo se modifica para que utilice la iteración cuando se llena una fila de píxeles, y luego rellena de manera recursiva las filas arriba y abajo. Como dijo @kasperjj, wikipedia tiene un buen artículo sobre esto.

Answer 4

Este tipo de algoritmos se discuten en detalle en Computer Graphics: Principles and Practice. Recomiendo encarecidamente este libro si está interesado en entender cómo rastrillar líneas, rellenar polígonos, escribir códigos en 3D sin el beneficio de utilizar las API de DirectX o OpenGL. Por supuesto, para las aplicaciones del mundo real, es probable que desee utilizar las bibliotecas existentes, pero si tiene curiosidad sobre cómo funcionan estas bibliotecas, esta es una lectura impresionante.

Answer 5

Lea también sobre etiquetado de componentes conectados. Esta es una forma eficiente de encontrar píxeles conectados, mientras que solo visita cada píxel dos veces.

Wikipedia article.

La ventaja de esto es que los valores de píxel no tienen que ser necesariamente la misma o la función que describe píxeles como conectado podría ser algo distinto de valor en bruto - gradiente tal vez.

Answer 6

La idea general se describe como Flood Fill Algorithm y presenta varias modificaciones. Uno común es el relleno de scanline. Ver la pregunta relacionada How Scanline based 2d rendering engines works?