今天寫程序中有一個地方用到了漫水填充（FloodFill）。所謂漫水填充，簡單來說，如下圖中左圖，白布上有一塊紅色的斑點，在這個紅色的斑點上點一下，就自動選中了和該點相連的紅色的區域，接著將該區域替換成指定的顏色，如下圖中右圖所示。

GDI中有一個函數 ExtFloodFill ，可以用于漫水填充。函數原型是：

BOOL ExtFloodFill(HDC hdc,int nXStart,int nYStart,COLORREF crColor,UINT fuFillType)

在C#中使用這個函數并不好用，這里有一個例子 http://www.codeproject.com/Feature/WickedCode.aspx?msg=2364985 。照貓畫虎的寫了一遍，結果返回的結果是false——填充失敗。

對win32這些東西看著就煩，也沒心思去看到底哪里出錯了，干脆自己寫一個 FloodFill 算法得了。

算法很簡單：

（1）將最初的點作為種子點壓入棧中；

（2）彈出一個種子點，把它涂成目標顏色；

（3）對于種子點來說，和它相鄰的有4個像素，判斷這4個像素中的顏色是否是背景色，如果是，則作為新的種子點入棧；

（4）循環至棧空。

實現起來也很簡單，一共只需要22行代碼，比用DllImport去調用ExtFloodFill代碼量還少：

void FloodFill(ImageRgb24 img, Point location, Rgb24 backColor, Rgb24 fillColor)
{
??? int width = img.Width;
??? int height = img.Height;
??? if (location.X < 0 || location.X >= width || location.Y < 0 || location.Y >= height) return;

??? if (backColor == fillColor) return;
??? if (img[location.Y, location.X] != backColor) return;

??? Stack<Point> points = new Stack<Point>();
??? points.Push(location);

??? int ww = width -1;
??? int hh = height -1;

??? while (points.Count > 0)
??? {
??????? Point p = points.Pop();
??????? img[p.Y, p.X] = fillColor;
??????? if (p.X > 0 && img[p.Y, p.X - 1] == backColor)
??????? {
??????????? img[p.Y, p.X - 1] = fillColor;
??????????? points.Push(new Point(p.X - 1, p.Y));
??????? }

??????? if (p.X < ww && img[p.Y, p.X + 1] == backColor)
??????? {
??????????? img[p.Y, p.X + 1] = fillColor;
??????????? points.Push(new Point(p.X + 1, p.Y));
??????? }

??????? if (p.Y > 0 && img[p.Y - 1, p.X] == backColor)
??????? {
??????????? img[p.Y - 1, p.X] = fillColor;
??????????? points.Push(new Point(p.X, p.Y - 1));
??????? }

??????? if (p.Y < hh && img[p.Y + 1, p.X] == backColor)
??????? {
??????????? img[p.Y + 1, p.X] = fillColor;
??????????? points.Push(new Point(p.X, p.Y + 1));
??????? }
??? }
}

有這個算法為基礎，類似photoshop的魔術棒選擇工具就很容易實現了。漫水填充（FloodFill）是查找和種子點聯通的顏色相同的點，魔術棒選擇工具則是查找和種子點聯通的顏色相近的點，將和初始種子點顏色相近的點壓進棧作為新種子。

在photoshop cs5中新引進了快速選擇工具，這個工具看起來很神奇，它背后的算法也研究了有些年了，就是摳圖技術，有興趣的可以去研究，這里有一篇很好的綜述文章：《Image and Video Matting: A Survey》。

?

總結

以上是生活随笔為你收集整理的漫水填充及Photoshop中魔术棒选择工具的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。