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

引言

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

常用填充算法

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

1 逐点判断算法:该算法对绘图窗口内每一像素点进行射线环绕探测来实现内点判定,孤立地考虑像素点与区域间的关系,计算量较大,一般不采用。

2 种子填充算法:该算法事先给定一像素点作为种子点,再以该种子点为起点朝四连通或八连通方向递归填充,如下图所示,左边为四连通填充效果,右边为八连通填充效果。但这种算法它仍基于像素,且区域内每一像素点均需入栈,易堆栈溢出,所以一般也不采用。

seedfill3 活性边表算法:该算法充分挖掘了边的连贯性和顶点间的约束关系,通过扫描线自下而上扫描图形,并利用相交边的斜率关系快速定位下次扫描的边界点,进而实现快速填充,如下图所示。该算法在速度上比其它算法都快,但弊端是需要事先将图形近似化成多边形,并存储关键点的坐标数据,且不能由用户指定填充内点,自由度很低。故绘图软件中往往也不采用

activeedge

扫描线种子填充算法

先大致说下这个算法的主要思想,好有一个直观的感受:该算法需事先指定一个种子点,然后分别水平向右和向左地探测得到图形边界点,填充两端点之间的线段(边界为[xl,xr]),并让该线段之上和之下的不超过xr的最右侧内点入栈,继而栈顶像素点出栈作为新的种子点,重复上述操作至栈空。

现在,假设我们要在下面的绘图空间内,填充边界颜色为X的区域,红色是用户点击的填充起点,阴影是填充后的颜色。那么按照上面所述思路,第一个种子点分别向左、向右找到边界,然后填充该区段后的效果就应该如下图所示。不仅填充了该区段,还把与自己向上紧邻的1像素、向下紧邻的1像素所在区段不超过xr的最右侧内点坐标压入了栈中。

stack1

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

stake3

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

stack

这里想提几点注意事项:

1 像素点入栈次序:应该是先向上探索,还是先向下探索,新种子点入栈有没有先后顺序要求,答案是没有,随意。

2 搜索时遇到内部边界:在向上、向下探索时,很容易遇到内部边界,比如上图中的像素点1在向下探索时,生成了像素点2和3,而他俩中间其实是隔了3个颜色为X的边界像素点的,这个时候直接跳过它们即可。

3 搜索时遇到内部孔洞:有人这时可能要质疑了,上面那种情况太特殊了,是满满的边界颜色,要是遇到“空心”的情况怎么办呢?比如2下面那一行?其实仔细想想,这种情况根本不存在,因为任何一个孔洞,它必然会有一个临界,这个临界就是扫描线在初遇到它的时候,本身完整的一个区段会被划分为左右区段(比如上图红色起点所在行的一整条扫描线,在向下探索时被划分成了2、3所在的两个区段),或左中右区段,甚至更多子区段的那个边界点,或边界线,上面那种情况就是边界线。而一旦被划分成多个区段后,[xl,xr]自然都会缩小,而算法对新种子点又有<=xr的限制,因此根本不用去考虑。

4 填充起点不同:经过测试,只要按照算法的限定和要求来执行,用户指定的填充起点不同对算法正确性毫无影响,只是扫描的次序会有不同。

不难看出,扫描线填充算法中种子点入栈次数与扫描线条数相同,较种子填充算法大大减少了堆栈操作,时空开销均有降低,效率都较高。所以该算法是绘图软件中常常采用的,非常高效。

算法描述

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

Step1  初始化: 堆栈置空。将种子点(x, y) 入栈;

Step2  出栈: 若栈空则结束。否则取栈顶元素(x, y) , 以y 作为当前扫描线;

Step3  填充并确定种子点所在区段: 从种子点(x, y) 出发, 沿当前扫描线向左、右两个方向填充, 直到边界。分别标记区段的左、右端点坐标为xl和xr;

Step4  确定新的种子点: 在区间[xl,xr]中检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素, 则把每一区间的最右像素作为种子点压入堆栈, 返回Step2

填充效果

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

 result result2

结语

本文只给出了该算法文字描述,但真正编程实现起来还是有很多细节需要注意,您可以去我的GitHub上下载FillAlgorithms,里面有上面所提到的算法实现。注意:因为当时需求所限,均是基于Android平台实现的,但核心是用Java写的,只需要把Android SDK中的画布、着色、画线等相关方法转换成JDK中的对应方法即可。

另外,本章最开头提到的“活性边表算法”也是非常神奇的一个算法,这个算法稍微复杂一些,所以本章也就不作详述了,如果您感兴趣,可以在我的GitHub上找到“一种强鲁棒性自适应活性边表算法”这篇论文,上面不仅有基本算法的实现思路,还有对该算法的改进实现,代码包含在上面那个填充算法集合里面。

“Android绘图软件开发”这个系列就这么多内容啦,主要对绘图软件的开发思路、技术框架、核心功能、难点功能进行了着重阐述,因为篇幅有限,对于界面、交互以及额外功能等就不做阐述啦。本人水平有限,如果有哪里写得不对恳请各路大神批评指正,又如果您看过该文之后有所启发,那就欢迎您继续关注我的博客哦~

Leave a Comment.