Algoritmos de relleno de inundación

Question

Es el fin de semana de nuevo, y eso significa que puedo jugar con mi hobby project.

he cansado de crear niveles de prueba a mano, así que pensé en tomar un descanso de desarrollo de motores y trabajar en un editor de niveles:

Level Editor http://gfilter.net/junk/Editor.JPG

me gustaría poner en práctica un algoritmo de relleno de inundación en el editor, que funcionaría como en un programa de pintura. ¿Alguien tiene alguna sugerencia sobre qué técnica funcionaría bien aquí?

El nivel es solo una matriz de 2d, por lo que podría considerarse lo mismo que un mapa de bits realmente.

Gracias!

Answer 1

general reference

optimized algorithm in C#

Answer 2

Wikpedia proporciona algunos ejemplos de pseudocódigo de las diferentes técnicas de relleno en su artículo Flood fill. La técnica que elija depende de la aplicación.

Recuerde que el relleno de inundación se puede enhebrar fácilmente (similar a cómo puede ser el quicksort).

Answer 3

Con toda justicia, debería ser bastante simple. Puesto que usted tiene la estructura básica del azulejo de todos modos el algoritmo sería bastante simple:

Select Tile To Fill:  
Fill Till  
Check neighbouring Tiles - If Empty Then Fill  
Repeat, for all filled tiles. 

exención de responsabilidad: La anterior es una descripción muy básica. Hay muchas referencias en la web que lo explican mucho mejor que yo.

Answer 4

Tuvimos que programar que para la escuela:

1: stuff the start pixel into a queue, note its color. note it as added. 
2: begin picking a pixel off the queue. If it's similar to the start pixel: 
    2: put all its neighbours into the queue 
     for each added pixel, note it's added. if already noted for a pixel, don't 
     add it anymore. 
    3: color it with the destination color. 
3: nonempty => jump back to 2 
4: empty => we are finished 

Dependiendo de si hacemos 8-vecino o 4-vecino, comprobamos los 8 píxeles vecinos, o sólo los píxeles izquierda/derecha o arriba/abajo una cierto pixel Aquí está el código (usando ImageJ. He eliminado algún código no relevante). Espero que tenga sentido, es Java. Solo pregunte por preguntas:

public class Uebung1_2 implements PlugInFilter, MouseListener { 
    private ImageProcessor ip; 
    boolean[] state; 
    int[] pixels; 
    Queue<Integer> nextPixels; 
    int threshould; 

    /** 
    * adds one pixel to the next-pixel queue only if it's not 
    * already added. 
    */ 
    void addNextPixel(int p) { 
     if(!state[p]) { 
      nextPixels.add(p); 
      state[p] = true; 
     } 
    } 

    boolean pixelsSimilar(int color1, int color2) { 
     int dr = Math.abs(((color1 >> 16) & 0xff) - 
          ((color2 >> 16) & 0xff)); 
     int dg = Math.abs(((color1 >> 8) & 0xff) - 
          ((color2 >> 8) & 0xff)); 
     int db = Math.abs(((color1 >> 0) & 0xff) - 
          ((color2 >> 0) & 0xff)); 
     return ((double)(dr + dg + db)/3.0) <= threshould; 
    } 

    /** 
    * actually does the hard work :) 
    * @param x the x position from which to start filling 
    * @param y the y position from which to start filling 
    */ 
    private void doFill(int x, int y, boolean connect8) { 
     // first, add the start pixel 
     int width = ip.getWidth(), 
      height = ip.getHeight(); 
     /* for 8bit, we just gonna take the median of rgb */ 
     Color colorC = ij.gui.Toolbar.getForegroundColor(); 
     int color = colorC.getRGB(); 
     int firstPixel = ip.get(x, y); 

     // go on with the mainloop 
     addNextPixel(y * width + x); 
     while(!nextPixels.isEmpty()) { 
      int nextPixel = nextPixels.remove(); 
      int pixel = pixels[nextPixel]; 
      if(pixelsSimilar(pixel, firstPixel)) { 
       // yay it matches. put the neighbours. 
       int xN = nextPixel % width, 
        yN = nextPixel/width; 
       /* the three pixels above */ 
       if(yN - 1 >= 0) { 
        if(connect8) { 
         if(xN + 1 < width) { 
          addNextPixel(nextPixel - width + 1); 
         } 
         if(xN - 1 >= 0) { 
          addNextPixel(nextPixel - width - 1); 
         } 
        } 
        addNextPixel(nextPixel - width); 
       } 

       /* pixels left and right from the current one */ 
       if(xN > 0) { 
        addNextPixel(nextPixel - 1); 
       } 
       if(xN + 1 < width) { 
        addNextPixel(nextPixel + 1); 
       } 

       /* three pixels below */ 
       if(yN + 1 < height) { 
        if(connect8) { 
         if(xN + 1 < width) { 
          addNextPixel(nextPixel + width + 1); 
         } 
         if(xN - 1 >= 0) { 
          addNextPixel(nextPixel + width - 1); 
         } 
        } 
        addNextPixel(nextPixel + width); 
       } 

       /* color it finally */ 
       pixels[nextPixel] = color; 
      } 
     } 
    } 

    @Override 
    public void run(ImageProcessor ip) { 
     ij.WindowManager.getCurrentImage().getCanvas().addMouseListener(this); 
     this.ip = ip; 
     this.pixels = (int[])ip.getPixels(); 
     this.state = new boolean[ip.getPixelCount()]; 
     this.nextPixels = new LinkedList<Integer>(); 
    } 

    @Override 
    public int setup(String arg0, ImagePlus arg1) { 
     return DOES_RGB; 
    } 

    @Override 
    public void mouseClicked(MouseEvent e) { 
     ij.WindowManager.getCurrentWindow().getCanvas().removeMouseListener(this); 
     ij.gui.GenericDialog g = new GenericDialog("Please enter parameters"); 
     g.addChoice("connection", new String[]{"4-connect", "8-connect"}, "8-connect"); 
     g.addNumericField("Threshould (0..255)", 0.0, 3); 
     g.showDialog(); 

     boolean connect8 = g.getNextChoice().equals("8-connect"); 
     threshould = (int) g.getNextNumber(); 
     doFill(e.getX(), e.getY(), connect8); 
     ij.WindowManager.getCurrentImage().draw(); 
    } 
} 

Answer 5

El artículo de Wikipedia es bastante bueno. Mientras sus cuadrículas sean pequeñas, cualquier cosa funcionará.

A principios de este otoño rellené algunas imágenes escaneadas de 10 megapíxeles. (El problema era eliminar los bordes negros de las páginas de los libros que se habían escaneado en una fotocopiadora). En ese caso, solo hay dos colores, así que básicamente traté el problema como una búsqueda en un gráfico no dirigido, con cada píxel conectado a sus vecinos a lo largo las cuatro direcciones de la brújula Mantuve un mapa de bits separado para realizar un seguimiento de los píxeles que se han visitado.

Las principales conclusiones fueron

• No trate recursiva búsqueda en profundidad. Realmente quieres una estructura de datos explícita.

• Una cola auxiliar utiliza mucho menos espacio que una pila.Aproximadamente cuarenta veces menos espacio. En otras palabras, prefiera la búsqueda de amplitud a la de profundidad de búsqueda.

Una vez más, estos hallazgos se aplican sólo a las redes con múltiples megapíxeles. En una cuadrícula pequeña y agradable como la que se muestra en su pregunta, cualquier algoritmo simple debería funcionar.