洪水填充實現

這是我的基於堆棧的洪水填充算法（我基於維基百科定義）的C＃實現。在編碼之前，我只想看看它的工作原理。它確實如此。然後，我想知道實際上填充的像素數。所以在我的代碼中，我將返回類型更改爲int並返回了變量「012」。但是然後ctr竟然約爲實際填充像素數的兩倍（我做了一個單獨的功能，唯一的目的是計算這些像素 - 只是爲了確定）。洪水填充實現

任何人都可以啓發如何以及爲什麼變量「ctr」增加兩倍，因爲它應該有？

* 像素類僅用作位圖像素的x，y和顏色值的容器。

public Bitmap floodfill(Bitmap image, int x, int y, Color newColor) 
{ 
    Bitmap result = new Bitmap(image.Width, image.Height); 
    Stack<Pixel> pixels = new Stack<Pixel>(); 
    Color oldColor = image.GetPixel(x, y); 
    int ctr = 0; 

    pixels.Push(new Pixel(x, y, oldColor)); 

    while (pixels.Count > 0) 
    { 
     Pixel popped = pixels.Pop(); 

     if (popped.color == oldColor) 
     { 
      ctr++; 
      result.SetPixel(popped.x, popped.y, newColor); 

      pixels.Push(new Pixel(popped.x - 1, popped.y, image.GetPixel(x - 1, y)); 
      pixels.Push(new Pixel(popped.x + 1, popped.y, image.GetPixel(x + 1, y)); 
      pixels.Push(new Pixel(popped.x, popped.y - 1, image.GetPixel(x, y - 1)); 
      pixels.Push(new Pixel(popped.x, popped.y + 1, image.GetPixel(x, y + 1)); 
     } 
    } 

    return result; 
}

來源

2013-01-31 libzz

如果'ctr'的意思是'counter'，那麼稱它爲'counter'沒什麼問題。 –

您做檢查這裏的像素的顏色：

if (popped.color == oldColor)

但popped.color可能（和apperently是在50％的案件）已經過時了。因爲在將像素插入堆棧時不檢查重複項，所以會有重複項。一旦彈出這些重複項，顏色屬性將很久以前保存。

也許它得到一個更清晰的圖畫：

graphical explanation

作爲一個例子，我花了位圖與9個像素。在第一個窗格中您有像素的編號，右側是您的堆棧。

您從第5號像素開始，然後將像素2,4,6和8推入堆棧。然後關閉像素2並按下1和3.在下一步中，您彈出1並再次按下2和4（再次！）。然後，你可以拿2，並意識到它已推出時已經得到了新的顏色。（稍遲，但比從不遲到）然而：像素號碼。 4有兩次，並且記得舊顏色兩次。所以你採用第4號像素併爲它着色。

一些步驟後來你有圖像填充，仍然在你的堆棧上的一些項目。由於舊顏色值仍然存儲在這些項目中，因此會再次計數。

雖然我在堆棧中可能有錯誤的排序，但該點仍然有效。

解決問題的方法：快速和骯髒的（因爲它仍然低效）

if (image.GetPixel(popped.x, popped.y) == oldColor)

它計算僅在當前的顏色是錯誤的，不記得彩色像素。

建議：檢查您的像素是否需要着色，然後再推入堆疊。

來源

2013-01-31 20:05:12

我明白你的觀點。但是彈出的像素（具有oldColor）不應該再次被推動（在下一次迭代中），因爲它的顏色屬性是通過SetPixel函數改變的。 – libzz

我確實延伸了我的答案，並希望繪圖能夠說清楚。對你的評論：如果你還沒有實現一些黑暗的魔法（或擴展方法），Bitmap.SetPixel（）肯定不會改變存儲在你的Pixel對象中的顏色值。它甚至不知道你的Pixel類存在！ –

謝謝！我看到我現在忽視的地方。我會嘗試你的建議！非常感謝您爲繪圖做出的努力！^_^ – libzz

如果所有Pixel都保留傳遞給其構造函數的顏色，則在填充像素後它不會更新顏色，因此可以每像素多次增加ctr。

如果更改像素採取一個指向它的構造函數圖像，你可以重新讀取顏色（即使顏色得到屬性，讀取當前的顏色），或跟蹤已經填寫的座標和不再次推動這些。

[編輯]

如果這一點不明確，從公認的答案和GetPixel返回一個顏色 - 值類型。把它想象成一個int，它編碼當時像素的RGB值。

如果您想快速執行填充，請查找Graphics.FloodFill示例。

如果您的目標是學習，我建議您將圖像數據複製到數組進行處理，然後再返回 - 大多數經典的圖像算法使用GetPixel（）並不是很有趣。

來源

2013-01-31 20:08:51

但是，當我推動像素時，它基於圖像本身而不是來自Pixel類。所以我假設他們不會再輸入if語句。因此，（據說）不增加ctr。 – libzz

是的，我們的教師教我們使用Bitmapdata處理字節指針。我已經轉換了我的代碼，它的運行速度非常快（在我修改它以便不插入已插入的像素後，速度更快）。感謝您的建議，但。 – libzz

洪水填充實現

回答

相關問題