王伟兵
完美前传
【摘 要】首先分析了经典的区域填充算法的两个问题.在此基础上,借鉴种子填充算法的一些思想,提出了一种针对任意复杂多边形区域的搜索算法,该算法克服了传统算法的一些缺陷,可以满足实际编程需要.【期刊名称】《自动化与信息工程》
【年(卷),期】2005(026)004
【总页数】3页(P18-19,45)
2015年新年寄语>晶炼
【关键词】区域填充;区域边界搜索;种子填充算法
【作 者】王伟兵
【作者单位】广东警官学院,计算机系
【正文语种】中 文
【中图分类】TP3
区域填充是基本图形算法研究的重要内容。经典的区域填充算法包括扫描线算法、边填充算法和种子填充算法等等。不论扫描线算法还是边填充算法，都要求预先知道区域的边界，即一般情况下要求在填充前将多边形区域的顶点坐标保存在数组中。但是在很多应用中，一个需要填充的复杂区域的边界事先并不知道。种子填充算法虽然不要求事先知道待填充区域的边界，但是不管是普通的种子填充算法还是扫描线种子填充算法，都要求使用堆栈，这就降低了算法的效率，在特殊应用中填充速度就满足不了要求。鉴于以上的问题，本文吸取了种子填充算法的某些思想，提出一种多边形区域的搜索算法，在应用扫描线填充算法或边填充算法之前，用于搜索待填充区域的边界。在笔者实际编程实现后，发现填充速度很快，能满足实际应用的需求。
算法总体分三步，流程图如图1 所示。
2.1 搜索包围“种子点”的最小闭合区域R
所谓“种子点”是指复杂非规则图形区域内部像素值已知的一点，实际编程中一般取鼠标点击点。本步骤逻辑上又分为两个子步骤：
（1）从“种子点”出发，沿任意固定方向扫描，寻一个位于区域R边界上的点作为“起始点”。
因为区域R边界预先未知，怎样判断扫描点到达区域 R边界上呢？简单地，可以判断各个扫描点的RGB值，只要扫描点的RGB值不等于“种子点”的RGB值，就可认为该扫描点位于区域R的边界之上。如图2（a）所示，但是倘若“种子”点到区域R的边界之间存在“黑洞”（位于闭合区域R内部但不包含“种子点”的小闭合区域），如图2（b）所示，就不能简单的判断，必须对每个RGB值和“种子点”RGB值不同的“准起始点”进行真伪鉴别，判断其是否真正是“起始点”（位于区域R边界之上）。真伪鉴别很容易：先从“准起始点”出发，应用子步骤（2）的搜索算法，搜索出一闭合区域r，判断r是否包围“种子点”（通过系统函数很容易实现），如果不包围，则该“准起始点”不是合法的“起始点”（不位于区域R之上），否则，就是合法的“起始点”。
（2）沿“起始点”出发，搜索R上的其他点，直到回到“起始点”，完成区域R的搜索。要到robust
下一点，必须先知道“当前点”和“当前方向”。因为一个像素点周围有八个相邻像素点，如图3所示。
须按一定的顺序依次对这八个点的RGB值进行判断，只要某个相邻点的RGB值和当前点不同，就认为该相邻点是所要的下一点，为了保证搜索正确以及尽可能减少比较次数，依次判断八个相邻点的顺序的就非常关键，为此，先定义八个方向（top/上,lefttop/左上,left/左, bottomleft/下左,bottom/下,rightbottom /右下,right/右,topright/上右），对应八个整数（0，1，2，3，4，5，6，7），八个方向对应的点就构成了一个圆，圆心就是“当前点”，假设“当前方向”D1=d1,则先对位于“当前点”D2=（D1+1）%8方向的相邻点进行判断，如该相邻点的RGB值与“当前点”的RGB值相同，则该点就是所要的“下一点”，否则方向加1，判断下一个相邻点，依次循环，直至到合适的“下一点”，认为该“下一点”就是区域R边界上的一点，将其存入数组，并取该“下一点”为“当前点”，当前方向取目前“当前点”相对于前一个“当前点”的方向，重新开始搜索新的“下一点”，依次循环，直至搜索到的“下一点”等于“起始点”，就完成了区域R的搜索。流程如图4所示。
2.2 搜索区域R中的“黑洞”
所谓区域R中的“黑洞”就是被区域R完全包围，但本身又不包围“种子”点的闭合区域。填充区域R时，不应当对R中的“黑洞”进行填充，这就要求搜索出已知区域R中所有“黑洞”。
搜索“黑洞”最直观的方法就是：根据已搜索到的区域R的边界点集合，求出包围区域R的最小矩形M，如图5。依次将M的所有内点（如存在点P的一个邻域，该领域上的所有点均属于区域M，则称点P是区域M的内点）作为“种子点”，按步骤1提供的算法搜索包围该“种子点”的闭合区域R＇,如R＇≠R，则R＇就是“黑洞”，否则不是“黑洞”。
这个直观方法简单清晰，易于实现，但执行起来速度较慢，原因是将一些无用的点作为“种子点”进行搜索操作：①M的内点，但不是R的内点，如图5中的A点，这些点位于区域R之外，完全没必要以它们为“种子点”进行搜索。②已搜索出的“黑洞”内部的点，如图5的B点，这些点位于某“黑洞”内部，以该点作“种子点”搜索而得闭合区域还是该“黑洞”。
为此需对该方法进行优化，以减少不必要的操作和冗余的操作。该步骤完整的流程图如图6所示。碱式碳酸锌
2.3 进行区域运算，对运算结果进行填充
李福兆
经步骤1和步骤2，已知道包围“种子点”的最小闭合区域R和R中若干“黑洞”。这就可调用系统提供的区域运算函数从R中减去所有R中的“黑洞”,得出一个新的区域 r，这就是带填充区域的边界。可采用扫描线算法或边填充算法对该区域进行填充。
该算法从实际编程的角度，提出了一种新的思想，有效克服了传统填充算法的一些问题，经实际编程检验，填充速度很快，对于一个极其复杂的多边形区域，边界搜索连同区域填充瞬间即可完成，完全可以满足实际需要。当然本算法还有一些缺点，比如略显复杂，编程时对编程技巧要求比较高，所以还有待于进一步的简化完善。
【相关文献】
[1] 何薇. 计算机图形技术与CAD[M]. 北京: 清华大学出版社, 2001.9
[2] 袁枫. Windows图形编程[M]. 北京: 机械工业出版社, 2002.4
[3] 唐荣锡,等. 计算机图形学教程[M]. 北京: 科学出版社,1994
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议