漫水填充及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)