洪水填充算法

Question

再次來到這個週末，這意味着我可以玩我的hobby project。

我已經得到了累了手工創建測試水平的，所以我想我會採取從發動機的研製工作在一個關卡編輯器突破：

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

我想實現編輯器中的洪水填充算法，可以像在繪畫程序中一樣工作。有沒有人有任何關於什麼技術對我有用的指點？

該級別只是一個2D數組，因此它可以被認爲與位圖相同。

謝謝！

Answer 1

general reference

optimized algorithm in C#

Answer 2

Wikpedia提供他們Flood fill文章的不同顏色填充技術的一些僞代碼例子。您選擇哪種技術取決於應用程序。

請記住，洪水填充可以很容易地進行線程化（類似於quicksort可以如何）。

Answer 3

平心而論，它應該很簡單。既然你有基本的瓷磚結構反正算法將是相當簡單：

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

免責聲明：以上是一個非常基本的描述。網上有很多參考文獻可以比我更好地解釋它。

Answer 4

我們不得不進行編程，對學校：

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 

取決於我們是否做8近鄰或4鄰國，我們檢查所有8個鄰居像素，或左/右或高於/低於僅像素某個像素。這裏是代碼（使用ImageJ，我刪除了一些不相關的代碼）。我希望它是有道理的，它是Java。只需提出問題：

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

維基百科的文章很不錯。只要你的網格很小，幾乎任何東西都可以工作。

今年秋天早些時候，我在1000萬像素的掃描圖像上做了一些洪水填充。 （問題是去除了在複印機上掃描過的書頁上的黑色邊緣）。在那種情況下，只有兩種顏色，所以我基本上將問題看作是在無向圖中進行搜索，每個像素都連接到它的鄰居四個羅盤方向。我保留了一個單獨的位圖來跟蹤哪些像素已被訪問。

主要結果

• 不要嘗試遞歸深度優先搜索。你真的想要一個明確的數據結構。

• 輔助隊列比堆棧使用的空間少得多。關於的空間減少了四分之一。換句話說，更喜歡廣度優先搜索到深度優先搜索。

同樣，這些研究結果只適用於電網與多個百萬像素。在你的問題中顯示的一個很好的小網格上，任何簡單的算法都可以工作。