洪水填充遞歸算法

我試圖做一個算法，可以在c＃中填充int數組。基本上，作爲MS Paint中的填充工具，我有一個顏色，如果我選擇數組中的（x，y）座標，它將用新顏色替換具有相同初始顏色的所有鄰居。洪水填充遞歸算法

例：

[0,0,0] 
[0,1,0] 
[1,1,0]

如果我在（0,0）放3，排列成爲

[3,3,3] 
[3,1,3] 
[1,1,3]

所以我想它在遞歸和它的工作，但不是所有的時間。實際上，我有時會出現「堆棧溢出」錯誤（似乎是合適的）。這裏是我的代碼，這將是巨大的，如果你能告訴我什麼是錯的:)

public int[,] fill(int[,] array, int x, int y, int initialInt, int newInt) 
{ 
    if (array[x, y] == initialInt) 
    { 
     array[x, y] = newInt; 

     if (x < array.GetLength(0) - 1) 
      array = fill(array, (x + 1), y, initialInt, newInt); 
     if (x > 0) 
      array = fill(array, (x - 1), y, initialInt, newInt); 

     if (y < array.GetLength(1) - 1) 
      array = fill(array, x, (y + 1), initialInt, newInt); 
     if (y > 0) 
      array = fill(array, x, (y - 1), initialInt, newInt); 
    } 

    return array; 
}

謝謝！

來源

2014-01-26 Pimeko

是啊......那是一大堆遞歸調用。可能最好以程序化的方式在C＃這樣的語言中完成此操作，但不保證尾部調用優化（不是說您的當前代碼會從中受益） –

不錯 - >「堆棧溢出」 – Justas

如何使用堆棧/隊列來管理剩餘的工作？

public void Fill(int[,] array, int x, int y, int newInt) 
{ 
    int initial = array[x,y]; 

    Queue<Tuple<int,int>> queue = new Queue<Tuple<int,int>>(); 
    queue.Push(new Tuple<int, int>(x, y)); 

    while (queue.Any()) 
    { 
     Tuple<int, int> point = queue.Dequeue(); 

     if (array[point.Value1, point.Value2] != initial) 
      continue; 

     array[point.Value1, point.Value2] = newInt; 

     EnqueueIfMatches(array, queue, point.Value1 - 1, point.Value2, initial); 
     EnqueueIfMatches(array, queue, point.Value1 + 1, point.Value2, initial); 
     EnqueueIfMatches(array, queue, point.Value1, point.Value2 - 1, initial); 
     EnqueueIfMatches(array, queue, point.Value1, point.Value2 + 1, initial);   
    } 
} 

private void EnqueueIfMatches(int[,] array, Queue<Tuple<int, int>> queue, int x, int y, int initial) 
{ 
    if (x < 0 || x >= array.GetLength(0) || y < 0 || y >= array.GetLength(1)) 
     return; 

    if (array[x, y] == initial) 
     queue.Enqueue(new Tuple<int, int>(x, y)); 
}

來源

2014-01-26 02:01:37

感謝這個算法和快速回答但這不起作用。事實上，我有一個「內存不足」的例外。任何想法？ – Pimeko

其實它工作！非常感謝:) – Pimeko

這是爲什麼使用遞歸併不總是合適的教科書示例。遞歸對於通過固有遞歸的數據結構（例如樹）是很好的，但是你的像素數據陣列不是。

我建議在代碼中添加一個計數器來打印fill()函數被調用的頻率。在每次函數調用時，您的機器都必須在內存中創建一個新的幀（所以它知道函數結束後必須返回哪個內存位置）。遞歸圖像填充算法調用fill()函數的次數很多，因此堆棧將快速增長。它的尺寸有限，所以它會溢出來放大照片。

解決方案是實現迭代填充算法，使用循環而不是遞歸遍歷像素。

請參閱維基百科上的recursion和stack overflows或Foley等人的「Computer Graphics，Principles and Practice」有關基本計算機圖形算法的更詳細介紹。

來源

2014-01-26 01:59:29

正如已經提出的那樣，問題在於遞歸調用的數量。在一個32位的機器上，你有4個字節的指針，所以如果你有一個512 * 512的圖像並且你想填充整個東西，那麼函數指針本身就會在你的堆棧上佔用512 * 512 * 4bytes = 1MB的內存。 And that is the default size of the stack。無論函數指針如何，您都有另外5個引用（array,x,y,initialInt,newInt），它們在每次調用時都被複製爲臨時對象，並且在函數調用終止之前處於堆棧中。在相同大小的圖像上，這些是另外的512 * 512 * 5 * 4字節= 5MB的內存。

要解決您的問題，您可以modify（與上面相同的鏈接）堆棧的大小。

此外，爲了節省一些堆棧空間，你可能會考慮包裝的單個對象內的參數，在這種情況下，你將有每個呼叫臨時存儲的只有4位，而不是20

不過，因爲它是並指出，最好的解決方案是迭代地重寫你的算法。

來源

2014-01-26 02:44:19

請注意，儘管增加堆棧大小可能是針對特定情況的解決方法，但當提供較大的圖像時，問題將再次出現。這仍然是一個非常低效的算法，真正的解決方案是修復算法。 –

@LeonWeber你是對的，我已經添加了編輯。 –

洪水填充遞歸算法

回答

相關問題