Android绘图软件开发(4)-扫描线种子填充算法

引言

填充，是绘图软件极为重要的一个功能。用户通过点击某空白区域内任一点，即可为该区域着色，系统能自动识别边界线，最后停止填充。本章我们就讲解下填充算法的实现思路。

常用填充算法

填充算法有很多种，他们适合不同的场景，效率也有所不同，有逐点判断算法、种子填充算法、扫描线种子填充算法和活性边表算法，其中扫描线种子填充算法是绘图软件常采用的，也是本文要介绍的。下面先简要介绍下其它3种算法：

• 逐点判断算法：该算法对绘图窗口内每一像素点进行射线环绕探测来实现内点判定，孤立地考虑像素点与区域间的关系，计算量较大，一般不采用。
• 种子填充算法：该算法事先给定一像素点作为种子点，再以该种子点为起点朝四连通或八连通方向递归填充，如下图所示，左边为四连通填充效果，右边为八连通填充效果。但这种算法它仍基于像素，且区域内每一像素点均需入栈，易堆栈溢出，所以一般也不采用。
  
• 活性边表算法：该算法充分挖掘了边的连贯性和顶点间的约束关系，通过扫描线自下而上扫描图形，并利用相交边的斜率关系快速定位下次扫描的边界点，进而实现快速填充，如下图所示。该算法在速度上比其它算法都快，但弊端是需要事先将图形近似化成多边形，并存储关键点的坐标数据，且不能由用户指定填充内点，自由度很低。故绘图软件中往往也不采用。
  

扫描线种子填充算法

先大致说下这个算法的主要思想，好有一个直观的感受：该算法需事先指定一个种子点，然后分别水平向右和向左地探测得到图形边界点，填充两端点之间的线段（边界为[xl,xr]），并让该线段之上和之下的不超过xr的最右侧内点入栈，继而栈顶像素点出栈作为新的种子点，重复上述操作至栈空。
现在，假设我们要在下面的绘图空间内，填充边界颜色为X的区域，红色是用户点击的填充起点，阴影是填充后的颜色。那么按照上面所述思路，第一个种子点分别向左、向右找到边界，然后填充该区段后的效果就应该如下图所示。不仅填充了该区段，还把与自己向上紧邻的1像素、向下紧邻的1像素所在区段不超过xr的最右侧内点坐标压入了栈中。

继续，下一步就应该是像素点3出栈，搜索边界[xl,xr]，填充区段，向上，向下，其中向上的时候发现整行都被填充过了，所以该行没有新种子点入栈，而向下的时候发现4正好属于内点、在最右侧、不超过xr，因此4入栈。下一步又是4出栈，同3的情况一样，最后进行到下图所示情况。

此时像素点5出栈，也和上面一样，执行完成后像素点6入栈。而6的这次就稍微有些不同了，因为6所在区段[xl,xr]比较长，往往上下就会有多于1个像素点入栈），可以看到这次有7、8、9入栈。

这里想提几点注意事项：

• 像素点入栈次序：应该是先向上探索，还是先向下探索，新种子点入栈有没有先后顺序要求，答案是没有，随意。
• 搜索时遇到内部边界：在向上、向下探索时，很容易遇到内部边界，比如上图中的像素点1在向下探索时，生成了像素点2和3，而他俩中间其实是隔了3个颜色为X的边界像素点的，这个时候直接跳过它们即可。
• 搜索时遇到内部孔洞：有人这时可能要质疑了，上面那种情况太特殊了，是满满的边界颜色，要是遇到“空心”的情况怎么办呢？比如2下面那一行？其实仔细想想，这种情况根本不存在，因为任何一个孔洞，它必然会有一个临界，这个临界就是扫描线在初遇到它的时候，本身完整的一个区段会被划分为左右区段（比如上图红色起点所在行的一整条扫描线，在向下探索时被划分成了2、3所在的两个区段），或左中右区段，甚至更多子区段的那个边界点，或边界线，上面那种情况就是边界线。而一旦被划分成多个区段后，[xl,xr]自然都会缩小，而算法对新种子点又有<=xr的限制，因此根本不用去考虑。
• 填充起点不同：经过测试，只要按照算法的限定和要求来执行，用户指定的填充起点不同对算法正确性毫无影响，只是扫描的次序会有不同。
  不难看出，扫描线填充算法中种子点入栈次数与扫描线条数相同，较种子填充算法大大减少了堆栈操作，时空开销均有降低，效率都较高。所以该算法是绘图软件中常常采用的，非常高效。

算法描述

为了实现，我们进一步整理一下，把扫描线填充算法归纳为以下4个步骤实现:

1. 初始化: 堆栈置空。将种子点(x, y) 入栈；
2. 出栈: 若栈空则结束。否则取栈顶元素(x, y) , 以y 作为当前扫描线；
3. 填充并确定种子点所在区段: 从种子点(x, y) 出发, 沿当前扫描线向左、右两个方向填充, 直到边界。分别标记区段的左、右端点坐标为xl和xr；
4. 确定新的种子点: 在区间[xl,xr]中检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素, 则把每一区间的最右像素作为种子点压入堆栈, 返回2。

填充效果

我们导入了一些较为复杂的图形进行填充测试，得到如下的效果。第一幅图的时间只用了1秒左右，事实证明该算法不仅正确，而且非常高效，给用户的自由度也很高。

结语

本文只给出了该算法文字描述，但真正编程实现起来还是有很多细节需要注意，您可以去我的GitHub上下载FillAlgorithms，里面有上面所提到的算法实现。注意：因为当时需求所限，均是基于Android平台实现的，但核心是用Java写的，只需要把Android SDK中的画布、着色、画线等相关方法转换成JDK中的对应方法即可。
另外，本章最开头提到的“活性边表算法”也是非常神奇的一个算法，这个算法稍微复杂一些，所以本章也就不作详述了，如果您感兴趣，可以在我的GitHub上找到“一种强鲁棒性自适应活性边表算法”这篇论文，上面不仅有基本算法的实现思路，还有对该算法的改进实现，代码包含在上面那个填充算法集合里面。
“Android绘图软件开发”这个系列就这么多内容啦，主要对绘图软件的开发思路、技术框架、核心功能、难点功能进行了着重阐述，因为篇幅有限，对于界面、交互以及额外功能等就不做阐述啦。本人水平有限，如果有哪里写得不对恳请各路大神批评指正，又如果您看过该文之后有所启发，那就欢迎您继续关注我的博客哦~