第4章(2)多边形填充算法

第4章基本光栅图形生成算法4.3多边形的填充4.3.1多边形的表示方法多边形的分类:凸多边形凹多边形含内环的多边形表示方法：顶点表示和点阵表示4.3.1多边形的表示方法顶点表示是用多边形的顶点的序列来描述多边形该表示几何意义强、占内存少但它不能直观地说明哪些像素在多边形内点阵表示是用位于多边形内的像素的集合来刻划多边形该方法虽然没有多边形的几何信息是面着色所需要的图像表示形式

多边形填充就是把多边形的顶点表示转换为点阵表示即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。

多边形的填充方法：扫描线方法边缘填充方法边界标志方法栅栏填充方法4.3.2多边形填充的扫描线算法算法特点：基本概念：充分利用了相邻象素之间的连续性，避免对象素的逐点判断和反复求交运算，减少了计算量，提高了算法速度，是效率较高的多边形填充算法，处理对象为非自交多边形。区域的连续性扫描线的连续性边的连续性关于一般多边形的填充过程,对于一条扫描线,可分为四步:求交排序交点配对区间填色奇点的处理区域的连续性

设多边形P的顶点各顶点Pi的纵坐标yi的递减数列p0p1p7p2p3p4p5p6p8p1,p7,p3,p6,p2,p5,p0,p4,p8(1)梯形的两底边分别在y=和y=两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。

它们具有下列性质(设为整数)：(2)梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。

(3)两类梯形在长方形区域{，}内相间的排列。

位于y=和y=两条扫描线之间的长方形区域被多边形P的边分割成若干梯形p0p1p7p2p3p4p5p6p8由区域的相关性知当知道一个区域内一点与多边形的位置关系，即可确定该区域内所有点与多边形之间的内外关系扫描线的连续性扫描线的连续性是区域连续性在扫描线上的体现012345678设e为一整数≥e≥若扫描线y=e与多边形P的边Pi-1Pi相交，则记其交点的横坐标为y=e该扫描线与P的边界各交点横坐标的递增序列此交点序列具有以下性质：

(1)l是偶数(2)扫描线被分成好多区段,一部分在多边形内,一部分在多边形外(3)两类线段间隔排列由区域的连贯性和扫描线的连续性知:若已知某一点与多边形的位置关系,就可知该点所在线段与多边形的位置关系边的连续性若d为一整数，d=e–1，且yi0≥y≥yin；设位于扫描线y=d上的交点序列为012345678y=ey=d则两交点序列之间有以下关系:

1两序列元素的个数相等2点()与()位于多边形P的同一边上，即以上性质称为边的连续性奇点定义

如果，则称顶点Pi为极值点；否则称Pi为非极值点。奇点的处理当扫描线与多边形P的边界的交点是P的顶点时，则称该交点为奇点p0p1p7p2p3p4p5p6p8要把奇点作为几个交点来处理呢??多边形P的顶点可分为两类：极值点和非极值点如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数。若将每一奇点都简单地计为两个交点，同样会导致反常的结果

为了使交点个数保持为偶数,规定当奇点是P的极值点时，该点按两个交点计算；否则按一个交点计算。

预处理:若Pi是非极值点，则将两边中位于扫描线y=yi上方的那条边在Pi点处截去一单位长扫描线算法的数据结构和实现步骤扫描线算法的数据结构多边形P0P1P2P3P4P5P6P0数据结构边的分类表ET和边的活化链表AELET和AEL中的多边形的边由四个域组成：

ymax

边的上端点的y坐标在ET中为边的下端点的x坐标x在AEL中是边与扫描线交点的x坐标Δx边的斜率的倒数next指向下一条边的指针[P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]多边形P0P1P2P3P4P5P6P0[P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]对奇点采用了预处理的边y筒分类表ET是按边下端点的纵坐标y对边进行分类的指针数组同一类中，各边按x值递增的顺序排列成行下端点的纵坐标y等于i的边归入第i类，水平边除外[P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]多边形P0P1P2P3P4P5P6P0对奇点采用了预处理的边y筒边的活化链表AEL由与当前扫描线相交的所有多边形的边组成

-5/357AELe7e54212AEL在y=2扫描线上的当前状态它记录了多边形沿扫描线的交点序列,并根据递推关系,不断地更新交点序列它是一个动态列表，新边插入，旧边删除[P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)][P0P1P2P3P4P5

P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]-5/35AELe7e54214AEL在y=3扫描线上的当前状态-5/35AELe7e54216AEL在y=4扫描线上的当前状态E4边做了预处理(也可以不做预处理，但要清楚的知道此点要在AEL中计几次)扫描线算法实现步骤步骤1:(AEL初始化)将边的活化链表AEL设置为空。步骤2:(y初始化)取扫描线纵坐标y的初始值为ET中非空元素的最小序号步骤3：按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行下列步骤，直到边的分类表ET和边的活化链表AEL都变成空为止。(1)如边分类表ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入边的活化链表AEL中，AEL中的各边按照x值(当x的值相等时，按Δx值)递增方向排序。(2)若相对于当前扫描线，边的活化链表AEL非空，则将AEL中的边两两依次配对，即第1，2边为一对，第3，4边为一对，依此类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点(象素)按多边形属性着色。(3)将边的活化链表AEL中满足y=ymax的边删去。

(4)将边的活化链表AEL剩下的每一条边的x域累加Δx，即x=x+Δx。

(5)将当前的扫描线的纵坐标值y累加，即y=y+1扫描线算法实现步骤伪代码Polygonfill(polydef,color)Intcolor多边形定义polydef{for(各条扫描线I){初始化新边表表头指针ET[I];把ymin=I的边放进边表ET[I];}y=最低扫描线号;初始化活化边表AEL为空;for(各条扫描线I){把新边表ET[I]中的边结点用插入排序法插入AEL表,使之按x递增顺序排列;遍历AET表,把配对交点之间的区间上的各像素(x,y)用待填颜色改写遍历AET表,把ymax=I的结点从AEL中删除,并把ymax>I的结点的x递增dx;若允许多边形的边自交,则用冒泡排序法对AEL表重新排序;}}扫描线算法特点数据结构较复杂但充分利用了扫描线、多边形边的连续性,避免了反复求交点的运算,是一种较快的填充方法对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现优点：对每个像素只访问一次与设备无关缺点：数据结构复杂只适合软件实现yx0123456789101112345678P6P4P1P5P2P3例习题1：用扫描线算法来扫描转换一个多边形边的Y筒ET5432125-3353720811075-3/2852yx0123456789101112345678P6P4P1P5P2P3边的活化链表Y=125-3353(5,1)(5,1)Y=222-3383(2,2)(8,2)yx0123456789101112345678P6P4P1P5P2P3yx0123456789101112345678P6P4P1P5P2P3例习题1：习题

设现在要用扫描线算法来扫描转换一个多边形，该多边形的顶点分别为，如图所示。先写出边y桶，然后试给出边的活化链表AEL,完成扫描转换4.3.3边缘填充算法采用对图像进行逐位求反的方法，免去对边排序的工作量算法特点:预备知识：对图像M作偶数次求反运算，其结果还是M;而对M作奇数次求反运算的结果是反的在光栅图形中，如某区域已着上值为M的某种颜色，则上述求反运算得到的结果是：对区域作偶数次求反运算后，该区域的颜色不变；作奇数次求反运算后，该区域的颜色则变成值为的颜色。边缘填充算法的实现对多边形P的每一非水平边（i=0,1,…,n）上的各像素做向右求反运算即可01234122334340边缘填充算法分析优点：最适合于有帧缓存的显示器可按任意顺序处理多边形的边仅访问与该边有交点的扫描线上右方的像素，算法简单缺点：对复杂图形，每一像素可能被访问多次，输入/输出量大图形输出不能与扫描同步进行，只有全部画完才能打印4.3.4栅栏填充算法此算法是为了减少边缘算法访问像素的次数而提出的栅栏:是一条与扫描线垂直的直线,栅栏的位置通常取过多边形顶点,能把多边形分为左右两半栅栏填充的基本思想:对于每个扫描线与多边形边的交点,就将交点与栅栏之间的像素取补.若交点位于栅栏左边,则将交点之右,栅栏之左的所有像素取补若交点位于栅栏右边,则将交点之左,栅栏之右的所有像素取补栅栏填充的具体实现:01234栅栏线12栅栏线34栅栏线23栅栏线4栅栏线0边界标志法:先画边界后填色，使对帧缓冲器中的每个元素的赋值次数不超过2次。基本思想是：先用一种特殊的颜色在帧缓冲器中将多边形的边界(水平边的部分边界除外)勾画出来。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需的颜色

图边界标志算法的运行过程4.3.5边界标志算法边界标志法具体实现图边界标志算法的运行过程步骤1：以值为boundary-color的特殊颜色勾画多边形P的边界。设多边形顶点为Pi=(xi,yi),0≤i≤n，xi,yi均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。步骤2：设interior_point是一布尔变量。对每一条扫描线从左到右进行搜索，如果当前是像素位于多边形P内，则interior_point=true，需要填上值为polygon_color的颜色；否则该像素在多边形P外，需要填上值为background_color的颜色边界标志算法实例XXXXXXXXXXXXP2(8,5)Y=2Y=3XXXXXXY=1P0(1,4)P1(1,10)P3(14,8)P4(14,2)P5(11,0)P6(6,0)XXXXХXXХY=4Y=5Y=6Y=7Y=8Y=9Y=10算法实现inti=0;doublex,y;doubledy,dx;intymin,ymax;for(i=0;i<=n;i++){dy=y[i+1]-y[i];if(dy!=0){dx=(x[i+1]-x[i])/dy;if(dy>0) x=x[i];elsex=x[i+1];if(y[i]>=y[i+1]){//获得多边形边的端点 ymin=y[i+1]; ymax=y[i];}else{ ymin=y[i]; ymax=y[i+1];}for(y=ymin;y<=ymax-1;y++){ x=x+dx; COLORREFk=RGB(0,0,255),n; n=dc->GetPixel(x,y); if(k==n) dc->SetPixel(x+1,y,RGB(0,0,255));//标志边界并处理奇点 elsedc->SetPixel(x,y,RGB(0,0,255));}}}//maxx、maxy、minx、miny是获得的多边形最小矩形包围盒边界值doublex1,y1;for(y1=miny-1;y1<=maxy-1;y1++){in_flag=0;//多边形内部标志变量for(x1=minx-1;x1<=maxx-1;x1++){COLORREFl,m;

l=dc->GetPixel(x1,y1);m=RGB(0,0,255);//多边形边界颜色if(l==m) {if(in_flag==0) in_flag=1;else in_flag=0;}if(in_flag)dc->SetPixel(x1,y1,RGB(0,0,255));//在多边形内部填充色蓝色elsedc->SetPixel(x1,y1,RGB(255,255,255));//在多边形外部填充色白色 }}算法特点分析：1本算法避免了对帧缓存的大量元素的赋值2但需逐条扫描线并对帧缓存中的元素进行搜索和比较3当算法生成的边界不封闭时，在一条扫描线上必须有偶数个具有边界颜色的点第4章基本光栅图形生成算法4.4区域填充4.4.1区域的基本概念是指已经表示成点阵形式的像素集合。区域区域的表示方式在光栅图形中，有内点表示法和边界表示法内点表示法：把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。边界表示法：把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。是指先将区域内的一点(常称种子点)赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。区域填充一个封闭区域确定以后,填充要解决的问题是如何确定填充的像素以及如何高效地填充。4连通的区域:取区域内任意两点，在该区域内若从其中一点出发通过上、下、左、右四种运动可到达另一点。四个方向的运动8连通区域:

取区域内任意两点，若从其中任一点出发，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点。8个方向的运动区域的连通性4连通区域可理解为8连通区域，但他们的边界不尽相同。四连通区域的边界是八连通的八连通区域的边界是四连通的4.4.2简单的种子填充算法

基本思想：1给定区域G一种子点（x,y）2判断该点是否是区域内的一点如果是，则将该点填充为新的颜色3然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理4通过这种扩散完成对整个区域的填充

简单的种子填充算法

（4连通）种子像素入栈当栈非空时，重复以下步骤：栈顶像素出栈将出栈象素置成填充色

按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799按右、上、左、下的顺序进栈区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果算法分析：1有些象素会入栈多次，降低算法效率；栈结构占空间。2递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。种子算法充分利用了递归调用的机理，在前一种子点确定并变为新颜色后，按照自身调用的八(四）向顺序依次查找新的种子点，找到即变为新颜色，继续下一种子的查找。未查的方向被压栈保存，等退栈时继续查找，最终完成蔓延至整个区域所有点都变为新颜色。

改进算法，减少递归次数，提高效率。方法之一使用扫描线填充算法；4.4.3扫描线种子填充算法从给定的种子点开始，填充当前扫描线上种子点所在的区间基本思想：然后确定与这一区间相邻的上下两条扫描线上需要填充的区间从这些区间上各取一个种子点并把他们保存起来，作为下次填充的种子点反复这个过程，直到所保存的各区间都填充完毕算法步骤：步骤1：将算法设置的堆栈置为空。将给定的种子点（x,y）压入堆栈步骤2：如果堆栈为空，算法结束；否则取栈顶元素（x,y）作为种子点步骤3：从种子点（x,y）开始，沿纵坐标为y的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充，直到边界为止。设区间两边界的横坐标分别为xleft和xright。步骤4：在与当前扫描线相邻的上下两条扫描线上，以区间[xleft,xright]为搜索范围，求出需要填充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到步骤2。

具体实现过程图3.32扫描线种子填充算法的执行过程1212123对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率。

12种子点位置不同3whilestack–not–emptydo

{pop(x,y)；*从堆栈中取一种子象素*savex:=x:*保存横坐标x的值*whilegetpixel(FB,x,y),<>B–colordo{setpixel(FB,x,y,N–color);x:=x+1}xright:=x–1*保存线段的右端点*x:=savex–1;{*向种子的左边填充*}whilegetpixel(FB,x,y)<>B–colordo{setpixel(FB,x,y,N–color);x:=x–1}xleft:=x+1*保存线段的左端点*x:=xleft;y:=y+1;whilex<=xrightdo

{span–need–fill:=false;算法程序：whilegetpixel(FB,x,y)<>N–colorandgetpixel(FB,x,y),<>B–colordo

{span–need–fill:=true;x:=x+1;}ifspan–need–fillthen

{push(x–1,y);右端点进栈span-need–fill:=false;}while(getpixel(FB,x,y)=B-colororgetpixel(FB,x,y)=N-color)andx<xrightdo{x:=x+1}

};*在上一条扫描上检查完*y:=y–2;*在扫描线y–1上从左向右地检查位于区间[xletft,xright]上的象素，其方法与在扫描线y+1上检查的情况完全一样，故略去详情*}*出栈完*算法程序：123扫描线种子点填充算法的具体应用。红色圆点代表种子点，扫描填充过程中，在要进栈的像素点的网格上依次标出他们的序号(进栈次序)；或是建立坐标系，写出每一步栈中所有像素的坐标值(有次序)。1234567891011121314151610987654321×××××××××××××××××●××××××××××××××××××××××