四、边界标志填充算法
在光栅显示平面上,多边形是封闭的,它是用某一边界色围成的一个闭合区域,填充是逐行进行的,即用扫描线逐行对多边形求交,在交点对之间填充。边界标志填充算法就是在逐行处理时,利用边界或边界颜色作为标志来进行填充的。准确地说,边界标志填充算法不是指某种具体的填充算法,而是一类利用扫描线连贯性思想的填充算法的总称。这类算法有很多种,本篇就介绍几种。
首先介绍一种以边为中心的边缘填充算法,这种边界标志算法的基本思想是:对于每一条扫描线和每一条多边形边的交点(xi,yi),将该扫描线上交点右方的所有象素取补,依次对多边形的每条边作此处理,直到最终完成填充。这里要介绍一下取补的定义,假设某点的颜色是M,则对该点的颜色取补得到M’ = A – M,A是一个很大的数字,至少要比所有合法的颜色值大。根据取补的定义,如果对光栅位图某区域已经标记为M的颜色值做偶数次取补运算,该区域颜色不变;而做奇数次取补运算,则该区域颜色变为值为M’的颜色。算法可以简单描述为两个步骤:
1、将绘图窗口的背景色置为M’颜色;
2、对多边形的每一条非水平边,从该边上的每个象素开始向右求余;
算法的处理过程如图(12)所示,左边是多边形的形状,右边分别是对每条边处理完成后填充区域的颜况,初始背景颜色是M’,经过处理后,需要填充的区域是奇数次取补,最终的颜色是要填充的正确值M,非填充区域经过偶数次取补,仍然是背景色M’:
图(12)边缘填充算法的处理过程
算法的实现非常简单,对于光栅位图的展示,我们仍然采用前文所用的方法,用数字矩阵表示一块光栅位图区域,矩阵的每个位置表示一个像素点,用0-9表示颜色值。本算法示例用9表示最大值A,0表示无效的区域,合法的颜色值就是1-8。
87void EdgeCenterMarkFill(const Polygon& py, int color)
88{
89 std::vector<EDGE3> et;
90
91 InitScanLineEdgesTable(et, py);//初始化边表
92
93 FillBackground(A - color); //对整个填充区域背景颜色取补
94 for_each(et.begin(), et.end(), EdgeScanMarkColor);//依次处理每一条边
95}
|
76void EdgeScanMarkColor(EDGE3& e)
77{
78 for(int y = e.ymax; y >= e.ymin; y--)
79 {
80 int x = ROUND_INT(e.xi);
81 ComplementScanLineColor(x, MAX_X_CORD, y);
82
83 e.xi -= e.dx;
84 }
85}
|
这个算法非常简单,所有的函数实现也很简单,InitScanLineEdgesTable()函数前面已经介绍过,FillBackground()函数将填充背景初始化为要填充颜色的取补颜色,EdgeScanMarkColor()函数负责对每条非水平边进行处理,逐条扫描线进行颜色取补,ComplementScanLineColor()函数负责对y扫描线上[x1, x2]区间的点的颜色值取补。
以上以边为中心的填充算法的优点是简单,缺点是对于复杂多边形,每一象素可能被访问多次(多次取补),效率不高。考虑对此算法改进,人们提出了栅栏填充算法。栅栏填充算法的基本思想是:经过多边形的某个顶点,在多边形内部建立一个与扫描线垂直的“栅栏”,当扫描线与多边形边有交点,就将交点与栅栏之间的象素取补。若交点位于栅栏左边,则将交点之右,栅栏之左的所有象素取补;若交点位于栅栏右边,则将栅栏之右,交点之左的象素取补。
仍以图(12)所示的多边形为例,假设经过P4点建立一条栅栏,则改进的栅栏填充算法处理过程就如图(13)所示:
图(13)栅栏填充算法的处理过程
栅栏填充算法的实现和以边为中心的边缘填充算法类似,只是对每条边的扫描线取补处理的范围控制有区别,算法需要指定一个“栅栏”:
115void EdgeFenceMarkFill(const Polygon& py, int fence, int color)
116{
117 std::vector<EDGE3> et;
118
119 InitScanLineEdgesTable(et, py);//初始化边表
120
121 FillBackground(A - color); //对整个填充区域背景颜色取补
122 for_each(et.begin(), et.end(),
123 std::bind2nd(std::ptr_fun(FenceScanMarkColor), fence));//依次处理每一条边
124}
|
97void FenceScanMarkColor(EDGE3 e, int fence)
98{
99 for(int y = e.ymax; y >= e.ymin; y--)
100 {
101 int x = ROUND_INT(e.xi);
102 if(x > fence)
103 {
104 ComplementScanLineColor(fence, x, y);
105 }
106 else
107 {
108 ComplementScanLineColor(x, fence - 1, y);
109 }
110
111 e.xi -= e.dx;
112 }
113}
|
注意FenceScanMarkColor()函数和EdgeScanMarkColor()函数的区别,就是这点区别使得栅栏填充算法主动减少了很多像素被访问的次数,而多边形之外的像素也不会被多余处理,效率提高了不少。
栅栏填充算法只是减少了被重复访问的象素的数目,但仍有一些象素会被重复访问。从图(13)中很容易看出这一点。下面介绍的边标志算法利用扫描线的连贯性,对每个像素只访问一次即可完成多边形区域的填充。边标志算法的思想是设置一个标志,沿着扫描线从左到右访问多边形所在区域的像素的时候,用这个标志标识是否扫描到了多边形的边界。如果碰到边界(边界用特殊的颜色标识),则改变标识状态,接下来根据标识状态决定扫描到的像素点是否要填充成指定颜色。
在实施边标志填充算法通常先求出多边形所在图像区域的最小包围盒,以便缩小扫描范围,加快填充速度。完整的填充算法如下:
5void EdgeMarkFill(int xmin, int xmax, int ymin, int ymax,
6 int boundarycolor, int color)
7{
8 int flag = -1;
9 for(int y = ymin; y <= ymax; y++)
10 {
11 flag = -1;
12 for(int x = xmin; x <= xmax; x++)
13 {
14 if(GetPixelColor(x, y) == boundarycolor)
15 {
16 flag = -flag;
17 }
18 if(flag == 1)
19 {
20 SetPixelColor(x, y, color);
21 }
22 }
23 }
24}
|
可以看到该算法思想简单,实现容易。算法既不需要初始化边表、求交点、交点排序等额外操作,也不需要使用链表、堆栈等数据结构。不过,边标志算法虽然简单,但是使用时对边界的处理要格外小心,否则很容易出错。比如上下顶点之类的局部极值点,会造成标志的奇偶计数不匹配,填充时会出现“抽丝”现象,也就是扫描线上不该填充的区段被填上色,而应该填充的区段却没有填上色。再比如边界像素点重复的问题,多边形的边界是利用直线的生成算法依次画出的,当扫描线遇到斜率小于1的边时,容易产生重复的边界点,如图(14)所示,引起标志的无序改变,从而造成填充错误。
图(14)斜率小于1的边的光栅扫描转换问题
至此,本文完整介绍了8中常见的多边形区域填充算法,拖拖沓沓写了一个多月,总算完成了,居然有将近30页,总计13000多字(24000多可见字符),毕业以后就没写过这么长的文档了,感慨一下。本文给出的示例代码都是为了演示,基于可读性而设计的,大家在实际的图形处理软件中看到的算法实现可能和本文的示例算法“大相径庭”,但是基本原理都是一样的。
参考资料:
【1】计算几何:算法设计与分析 周培德 清华大学出版社 2005年
【2】计算几何:算法与应用 德贝尔赫(邓俊辉译) 清华大学出版社 2005年
【3】计算机图形学 孙家广、杨常贵 清华大学出版社 1995年
分享到:
相关推荐
多边形区域填充算法,
(系统会自己调高积分,我重新改成5分啦!)大学计算机图形学课程作业代码,完美实现多边形有效边表填充算法,自用,具体代码完整。打包下载,可直接运行。c/c++语言MFC实现。支持vs。
区域填充算法,很强大的算法,通过鼠标画多边形,在选择颜色并填充
1. 通过实验,进一步理解和掌握几种常用多边形填充算法的基本原理 2. 掌握多边形区域填充算法的基本过程 3. 掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。 实验设备及实验环境 计算机(每人一台) ...
使用MFC编写的多边形有效边表填充算法,是完整的算法 大家有需要的借鉴借鉴
使用VS 2017实现多边形填充中的种子填充算法,此资源包括完整的项目文件,可以直接使用。此代码仅供学习交流使用。
多边形扫描填充算法,填充图案为自己的学号
这是用java实现的多边形填充算法,是扫描线算法,按照课本上编写的,调试过,绝对没问题。
对一个用鼠标左击形成的多边形,画一个最小的矩形,在这个矩形内用有效边表填充算法对多边形填充。 建议 请用VS2008运行。
实现用扫描线算法 和种子算法对多边形进行填充 还可以画线和多边形
C++ 多边形边缘填充算法主要于图像填充的开发,代码调理清晰,有助于图像处理方面开发。
用VS2013,OPENGL环境实现多边形的扫描转换和区域填充,附上OPENGL配置文件。多边形的扫描转换:有效边表算法,多边形的区域填充:边界填充算法。
vs2008下 opengl实现,多边形扫描线填充算法。 用到glut库 鼠标左右键实现选点和填充
1)用边缘填充算法填充示例多边形; 2)实现调用系统调色板选择多边形填充颜色; 3)多边形外接矩形为整个屏幕客户区。
python实现扫描线填充算法,使用matplotlib模块将绘制的图形保存并画出来,可以画凹多边形
题目:用种子填充算法(或扫描线填充算法)填充任一多边形域 基本要求: (1)数据输入项为:多边形的顶点数、各顶点x,y坐标。 对于种子填充算法要输入种子象素的x,y坐标。 对于扫描线填充算法要输入扫描线间距。 ...
实验三计算机图形学多边形填充算法
为提高区域填充效率,对三种常见的区域填充算法进行了介绍和分析,并对其中优势较为明显的活性边表区域填充算法进行了进一步改进。改进算法针对原始算法的不足,充分利用多边形顶点信息,建立了活性边动态发现机制,...
使用java编程 多边形画法:先选择画图中的多边形,然后在面板里单击鼠标左键,画点...扫描线种子填充的算法适合于任意图形,不会出现部分区域填补上的现象。 程序没有任何问题~ 有不明白的可以联系我~ qq:815366795~