某人最近在使用C#写一个类似Windows的画图工具，在填色的部分卡住了。劳资要他使用种子填充算法着色（不要调用Windows提供的API，否则还锻炼个毛线），现在我把这个功能实现了，程序的效率很高。现在在这里大概写一下实现方法。
程序是用VB.NET写的，C#写法类似（而且还不需要使用Marshal类访问非托管资源，更加方便）。程序的运行结果如下：
种子填充算法说白了就是宽度优先搜索算法（BFS），如果你不知道这是什么东西，那说明你数据结构根本就没有学，请自行补充相应的知识。
第一步：实现“铅笔”工具
我们定义如下的全局变量（窗体类的私有成员），作用是啥一看名字就知道：
Private Enum DrawStyle
Drawing = 0
Fill = 1
DrawDragging = 2
End Enum
Private _fillColor() As Color = {Color.Blue, Color.Green, Color.Red, Color.LightGray, Color.LightPink, Color.LightSkyBlue, _
Color.GreenYellow, Color.Gold, Color.LightSeaGreen}
Private _drawStyle As DrawStyle = DrawStyle.Drawing
Private _imgMain As Bitmap
Private _g As Graphics
Private _lastPosition As Point
Private _drawingPen As Pen
</div>
这个程序中填充的颜色是随机决定的（都懒得做一个选颜色的功能了），可以填充的颜色在_fillColor数组中。_drawStyle定义当前的绘图模式（Drawing表示使用铅笔工具，但未按下，Fill表示准备填充，DrawDragging表示鼠标正按下并拖拽）。
_imgMain是绘制的图片，_g是创建在这个Bitmap上的Graphics对象。
需要注意的是，Drawing和Drawing2D类不提供画点的方法，我们需要通过画直线或画矩形来模拟。至于_lastPosition的作用，由于鼠标拖拽过程中，如果速度过快，那么MouseMove事件中的坐标点（每次MouseMove事件被触发）并不是连续的，所以我们需要在当前点和上一次的鼠标位置之间画一条直线，否则画出来的线是间断的。
MouseDown、MouseMove和MouseUp实现铅笔工具的基本功能，代码如下：
Private Sub PictureBox1_MouseDown(sender As Object, e As MouseEventArgs) Handles PictureBox1.MouseDown
If CheckBox1.Checked Then _drawStyle = DrawStyle.Fill Else _drawStyle = DrawStyle.Drawing
If _drawStyle = DrawStyle.Fill Then
Call FillRegion(e.Location, _fillColor(New Random().Next(_fillColor.Count)))
Else
_drawStyle = DrawStyle.DrawDragging
_lastPosition = e.Location
End If
End Sub
Private Sub PictureBox1_MouseMove(sender As Object, e As MouseEventArgs) Handles PictureBox1.MouseMove
If _drawStyle = DrawStyle.DrawDragging Then
_g.DrawLine(_drawingPen, _lastPosition, e.Location)
_lastPosition = e.Location
PictureBox1.Image = _imgMain
End If
End Sub
Private Sub PictureBox1_MouseUp(sender As Object, e As MouseEventArgs) Handles PictureBox1.MouseUp
_drawStyle = DrawStyle.Drawing
End Sub
</div>
二、正题——种子填充算法的实现
上面说了一堆废话，现在终于可以开始实现填充的算法了。
当用户点击图片中某一个点后，需要填充与这个点相邻的、颜色相同的其他点。为什么要叫“种子填充”呢？大概是这样：你在点中的那个点中播下一颗种子，它开花结果（颜色变成目标颜色），然后它又播种出新的种子（与它上下左右相邻且颜色等于原来颜色的点）；新种子再开花结果（变颜色），播种新种子…… 如此往复，直到没有地方播种了为止，算法结束。
按照BFS通常的实现方式，可以使用循环队列作为数据结构。对于BFS算法来说，需要的存储空间较大，具体需要多少还真不好估算。这里给大家一个参考，我的这个程序图片框大小是832*450，大概是37万像素，循环队列的容量设置为1600可以满足需求（全部着色）。如果你的图片框比较大，可以先取一个较大的数值（比如8000），再逐渐缩小，反复尝试。
实现这个循环队列直接定义成一个一维数组就可以了，没有必要使用ConcurrentQueue类，否则性能会下降，也没有这个必要。
首先，由于要向四个方向填充，为了避免类似的代码反复写导致程序丑陋无比，我们可以定义一个fill_direction数组：
Dim fill_direction() As Point = {New Point(-1, 0), New Point(1, 0), New Point(0, -1), New Point(0, 1)}
</div>
这样，使用一个For循环就可以完成四个方向的操作了。
按照首先说的思路，程序的实现就很简单了：首先将点击的那个点入队，记录这个点的颜色。然后使用一个循环，取出队首元素，并向四个方向撒种子（颜色相同，且没有越出图片框边界），将每一个种子的颜色改变成目标颜色并入队。如此往复直到队列为空为止。代码如下：
Private Sub FillRegion2(sourcePoint As Point, destinationColor As Color)
Dim new_bitmap As Bitmap = DirectCast(PictureBox1.Image, Bitmap)
Dim source_color As Color = new_bitmap.GetPixel(sourcePoint.X, sourcePoint.Y)
Dim MIN_X As Integer = 0, MIN_Y As Integer = 0
Dim MAX_X As Integer = PictureBox1.Width - 1, MAX_Y As Integer = PictureBox1.Height - 1
Dim fill_queue(MAX_FILL_QUEUE) As P