漫水填充及Photoshop中魔術棒選擇工具的實作

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

<a href="http://images.cnblogs.com/cnblogs_com/xiaotie/WindowsLiveWriter/Photoshop_58F0/image_2.png"></a>

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

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

對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 &lt; 0 || location.X &gt;= width || location.Y &lt; 0 || location.Y &gt;= height) return;     if (backColor == fillColor) return;      if (img[location.Y, location.X] != backColor) return;     Stack&lt;Point&gt; points = new Stack&lt;Point&gt;();      points.Push(location);     int ww = width -1;      int hh = height -1;     while (points.Count &gt; 0)      {          Point p = points.Pop();          img[p.Y, p.X] = fillColor;          if (p.X &gt; 0 &amp;&amp; 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 &lt; ww &amp;&amp; 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 &gt; 0 &amp;&amp; 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 &lt; hh &amp;&amp; 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）是查找和種子點聯通的顔色相同的點，魔術棒選擇工具則是查找和種子點聯通的顔色相近的點，将和初始種子點顔色相近的點壓進棧作為新種子。

本文轉自xiaotie部落格園部落格，原文連結http://www.cnblogs.com/xiaotie/archive/2010/09/08/1821100.html如需轉載請自行聯系原作者

xiaotie 集異璧實驗室(GEBLAB)