Algorithmes de remplissage d'inondation

Question

C'est le week-end à nouveau, et cela signifie que je peux jouer avec mon hobby project.

Je suis devenu fatigué de créer des niveaux d'essai à la main, donc je pensais que je prendrais une pause de développement du moteur et de travailler sur un éditeur de niveau:

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

J'aimerais mettre en œuvre un algorithme de remplissage d'inondation dans l'éditeur, qui fonctionnerait comme dans un programme de peinture. Est-ce que quelqu'un a des indications sur quelle technique serait bon pour moi ici? Le niveau est juste un tableau 2d, donc il pourrait être considéré comme un bitmap vraiment.

Merci!

Answer 1

general reference

optimized algorithm in C#

Answer 2

Wikpedia fournit quelques exemples de pseudocode de différentes techniques de remplissage des crues sur leur article Flood fill. La technique que vous choisissez dépend de l'application. Rappelez-vous que le remplissage d'inondation peut facilement être fileté (similaire à la rapidité de la transmission).

Answer 3

En toute justice, cela devrait être assez simple. Puisque vous avez la structure de carreau de base de toute façon l'algorithme serait assez simple:

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

Avertissement: Ce qui précède est une description très basique. Il y a beaucoup de références sur le web qui l'expliquent beaucoup mieux que je peux.

Answer 4

Nous avons dû programmer que pour l'école:

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 

Selon que nous ne 8 voisin ou 4 voisin, nous vérifions les 8 pixels voisins, ou seuls les pixels gauche/droite ou au-dessus/en dessous d'un certain pixel. Voici le code (en utilisant ImageJ, j'ai enlevé du code non pertinent). J'espère que c'est logique, c'est Java. Il suffit de demander des questions:

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

L'article Wikipédia est plutôt bon. Tant que vos grilles sont petites, à peu près tout va fonctionner.

Plus tôt cet automne, j'ai fait un certain remplissage d'inondation sur des images numérisées de 10 mégapixels. (Le problème consistait à supprimer les bords noirs des pages de livres qui avaient été scannées sur un photocopieur.) Dans ce cas, il n'y a que deux couleurs, donc j'ai essentiellement traité le problème comme une recherche dans un graphe non orienté. les quatre directions de la boussole. J'ai maintenu un bitmap séparé pour garder la trace des pixels qui avaient été visités.

Les principales conclusions ont été

• Ne pas essayer profondeur d'abord récursive recherche. Vous voulez vraiment une structure de données explicite. Une file d'attente auxiliaire utilise beaucoup moins d'espace qu'une pile.Environ quarante fois moins d'espace. En d'autres termes, préférez la recherche en largeur à la recherche en profondeur en premier.

Encore une fois, ces résultats portent uniquement sur des grilles avec plusieurs mégapixels. Sur une belle petite grille comme celle montrée dans votre question, tout algorithme simple devrait fonctionner.