CG-4-2 区域填充

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4.4,区域填充,4.4.1,有序边表填充算法,本节讨论如何用一种颜色或图案来填充一个二维区域。填充的区域可以是多边形的，也可以是圆或椭圆的，还可以是带孔的。区域填充可以分两步进行，第一步先确定需要填充哪些像素。第二步确定用什么颜色值或图案来填充。,多边形区域填充的一种常用方法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。,A B C D,P,1,P,2,P,3,P,4,P,5,P,6,2 4 6 8 10,2,4,6,8,O,y,x,如图所示，扫描线,3,与多边形的边界线交于四点,A,、,B,、,C,、,D,。,交点,(,x,坐标,),序列为：,3,、,4.5,、,6,、,8.3,把交点从小到大逐对取出，构成区间：,3, 4.5,6, 8.3,。这,两个区间落在多边形内，该区间内的像素应该填充，其他区间不填充。,图,多边形与扫描线,在多边形顶点处的交点需要专门处理。,例如图所示，扫描线,2,与多边形相交于,P,6,，若交点算一个，则求得交点,(,x,坐标,),序列,3, 6.5, 7.5,。这将导致,3, 6.5,区间内的像素被填充，而这个区间的像素是属于多边形外部，不需要填充。,A B C D,P,1,P,2,P,3,P,4,P,5,P,6,2 4 6 8 10,2,4,6,8,O,y,x,为了正确地进行交点取舍，必须对上述两种情况区别对待。,具体实现时，只需检查顶点的两条边的另外两个端点的,y,值。按这两个,y,值中大于交点,y,值的个数是,0,，,1,，,2,来决定是取零个、一个、还是两个。,A B C D,P,1,P,2,P,3,P,4,P,5,P,6,2 4 6 8 10,2,4,6,8,O,y,x,例如，扫描线,2,交顶点,P,6,，由于共享该顶点的两条边的另外二个顶点均高于扫描线，故交点,P,6,取两次，,则交点序列为,：,3,、,3,、,6.5,、,7.5,。即,3, 3 6.5, 7.5,二个区间内的像素被填充,。,而,扫描线,7,与多边形相交于,P,1,，该交点算一个，则交点序列为：,2, 10,，即,2, 10,区间内的像素被填充,。,A B C D,P,1,P,2,P,3,P,4,P,5,P,6,2 4 6 8 10,2,4,6,8,O,y,x,由于边的连贯性，即当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交，为此，计算下一条扫描线与同一条边的交点,x,值时，只需把当前交点,x,值加上一个边的反斜率即可：,x,k,+1,=,x,k,+ 1 /,m,(,m,为边的斜率,),A B C D,P,1,P,2,P,3,P,4,P,5,P,6,2 4 6 8 10,2,4,6,8,O,y,x,归纳上述讨论，我们可写出多边形区域填充的步骤为：,输入欲填充多边形的顶点数及其顶点坐标。这里，顶点数为实际顶点数加,1,，最后一个顶点坐标与第一个顶点坐标相同。,计算所有多边形顶点坐标中,y,的最大值和最小值，以此作为扫描线的处理范围。,对处理范围内的每条扫描线建立有序边表。,对处理范围内的每条扫描线，重复下列步骤：,A,用有序边表建立当前扫描线的活化边表；,B,从活化边表中依次取出一对交点，对该两个交点内的像素进行填充；,C,为下一条扫描线更新活化边表，即增加交点的,x,值和删除不再相交的边；,D,重排活化边表。,有序边表填充算法的,C,语言描述（略）,4.4.2,边填充算法,边填充算法的基本思想是：求每一条扫描线和多边形各边的交点,(x,1, y,1,),，,将该扫描线上交点右方的所有像素取补。,对多边形的每条边作此处理，多边形的顺序随意。如图所示，为应用最简单的边填充算法填充一个多边形的示意图。,P,5,P,4,P,3,P,1,P,2,P,2,P,3,P,3,P,4,P,4,P,5,P,5,P,1,图,边填充算法示意图,本算法的优点是简单，缺点是对于复杂图形，每一像素可能被访问多次，输入,/,输出的量比有序边表算法大得多。,为了减少边填充算法访问像素的次数，可引入栅栏。所谓栅栏指的是一条与扫描线垂直的直线，栅栏位置通常取过多边形顶点、且把多边形分为左右两半。,栅栏填充法的基本思想是：对于每个扫描线与多边形的交点，就将交点与栅栏之间的像素取补。若交点位于栅栏左侧，则将交点之右至栅栏之左的所有像素取补；若交点位于栅栏右边，则将栅栏之右至交点之左的像素取补。图,3.10,为栅栏填充法示意图。,P,5,P,4,P,3,P,1,P,2,P,2,P,3,P,4,P,5,P,3,P,4,P,5,P,1,图,栅栏填充算法示意图,4.4.3,种子填充算法,种子填充算法则采用不同的原理：填充方法是从多边形区域内部的一点开始，由此出发找到区域内的所有像素。这种填充算法在交互式绘图中很常用。,种子填充算法采用的边界定义是区域边界上所有像素均具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色，而边界外的像素则可具有与边界相同的颜色值。,程序从,(,x,，,y,),开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否是边界色和填充色，若不是，就填充该相邻点。这个过程延续到已经检测完区域边界范围内的所有像素为止。,从当前点检测相邻像素有两种方法：四向连通和八向连通。四向连通方法指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；,4,连通,从区域内任意一点出发，可通过上、下、左、右四个方向到达区域内的任意象素；,8,连通,从区域内任意一点出发，可通过上、下、左、右、左上、左下、右上、右下八个方向到达区域内的任意象素。,4,连通区域和,8,连通区域,四连通区域 八连通区域,区域的表示方法,内点表示,枚举出区域内部的所有像素,内部的所有像素着同一个颜色,边界表示,枚举出边界上所有的像素,边界上的所有像素着同一颜色,内部像素着与边界像素不同的颜色,八向连通方法指的是区域内每一个像素，可以通过左、右、上、下、左上、右上、左下、右下这八个方向的移动的组合来到达。,种子填充算法中允许从四个方向寻找下一像素者，称为四向算法；允许从八个方向搜索下一像素者，称为八向算法。八向算法可以填充八向连通区域，也可以填充四向连通区域。但四向算法只能填充四向连通区域，而不能填充八向填充区域。以下我们只讨论四向算法。只要把搜索方向从四个改变八个，即可得到八向算法。,下面程序给出了四向连通填充的递归算法。,void boundaryfill4 (,int,seedx,int,seedy,int,fcolor,int,bcolor,),int,current =,getpixel,(,seedx, seedy);,if (current !=,bcolor,) & (current !=,fcolor,),putpixel,(,seedx, seedy,fcolor,);,boundaryfill4 (,seedx,+1, seedy,fcolor,bcolor,);,boundaryfill4 (,seedx,1, seedy,fcolor,bcolor,);,boundaryfill4 (,seedx, seedy +1,fcolor,bcolor,);,boundaryfill4 (,seedx, seedy 1,fcolor,bcolor,);,void,SeedFill,(,int,cnt, POINT *pts,int,seedx,int,seedy,int,fcolor,int,bcolor,),POINT v1,v2;,int,i;,for (i=0; i ,cnt,1; i +), v1 = pts i ; v2 = pts i +1;,BoundaryMark,(v1.x, v1.y, v2.x, v2.y,bcolor,);,boundaryfill4 (,seedx, seedy,fcolor,bcolor,);,这种算法的优点是算法简单，易于实现，也可以填充带有内孔的平面区域。但是这种算法需要很大的存储空间以实现栈结构，同一个像素多次入栈和出栈，所花费的时间也很多。因此后来提出了许多改进的算法，如书上的扫描线种子填充算法，链队列种子填充算法。,链队列种子填充算法的算法基本思路是：从链队列中获得一个像素点，判断其四连通像素点，若没有填充，则填充它，并将它入队列，如此循环，直到队列空为止。,4.4.4,圆和椭圆的填充,上面所讨论的多边形区域的填充原理也可以推广到圆域的填充。由于圆和椭圆的特殊属性，即可依据任何欲填充的像素点与圆心的距离是否大于或小于半径来判断是否在圆外或圆内，或者依据欲填充的像素点与椭圆两焦点的距离之和是否大于或小于椭圆的半径常数来判断是否在椭圆外或椭圆内，因此圆和椭圆的填充采用种子填充算法最为简单，并且它不需要先对圆或椭圆边界进行扫描转换。,以下是圆的四向连通填充算法的,C,语言描述。,void CircleFill4 (,int,xc,int,yc,int,r,int,seedx,int,seedy,int,color),int,fill =,getpixel,(,seedx, seedy);,if (,seedx,xc,) * (,seedx,xc,) + (seedy ,yc,) *,(seedy ,yc,) next;,while ( p1 ), p2 = p1 next;,for ( i = p1 x; i x; i +),if (pattern i % 8 scan % 8 ),putpixel,( i, scan, color );,p1 = p2 next;,上述程序的一个运行结果如图,3.12,所示。,图,3.12,图案填充的一个实例,4.4.6,线宽与线型的处理,1,、,直线线宽的处理,在实际应用中，除了使用单像素宽的线条，还经常使用指定线宽和线型的直线与弧线。欲产生具有宽度的线，可以顺着扫描所生成的单像素线条轨迹,移动一把具有一定宽度的“刷子”来获得。“刷子”的形状可以是一条线段或一个正方形。也可以采用区域填充的办法间接地产生有宽度的线。,线刷子的原理最简单。假设直线斜率在,1, 1,之间，这时可以把刷子置成垂直方向，刷子的中点对准直线一端点，然后让刷子中心往直线的另一端移动，即可“刷出”具有一定宽度的线。,当直线斜率不在,1,，,1,之间时，把刷子置成水平方向。具体实现线刷子时，只要对直线扫描转换算法的内循环稍作修改。例如，当直线斜率在,1, 1,之间时，把每步迭代所得的点的上下方半线宽之内的像素全部置成直线颜色,若线宽为,5,个像素，则把原来的,putpixel(,x, y,，,color),语句扩展为下列循环语句：,for(i=-2;i=2;i+),putpixel,(,x,，,y+,i,，,color);,图,3.22,所示为线宽是,5,个像素的情形。算法简单、效率高是线刷子的优点。但是，线的始末端总是水平或垂直的。因此，当线宽较大时，看起来很不自然。当比较接近水平的线与比较接近垂直的线汇合时，汇合处外均将有缺口。如图,3.23,所示。,图,3.22 5,个像素宽的线刷子,图,3.23,线刷子的缺口,线刷子还会使斜线与水平（或垂直）线不一样粗。对于水平线或垂直线，刷子与线条垂直，因而最粗。其粗细与指定线宽相等。而对于,45,斜线，刷子与线条成,45,角，粗细仅为指定线宽的,0.7,倍。,为了生成有宽度的线，还可以用方形的刷子。把边宽为指定线宽的正方形的中心沿直线作平行移动，即可获得具有线宽的线条，如图,3.24,所示为用正方形刷子绘制的具有宽度的线条。比较图,3.24,与图,3.22,可知，用方形刷子所得的线条比用线刷子所绘制的线条要粗一些。,线宽为,5,个像素的方刷子,与线刷子类似，用方刷子绘制的线条始未端也是水平或垂直的，且线宽与线条方向有关。与线刷子的情形相反，对于水平线与垂直线，线宽最小，而对于斜率为,1,的线条，线宽最大，为垂直（水平）线宽度的,1.41,倍。,实现正方形刷子最简单的办法是，把方形中心对准单像素宽的线条上各个像素，并把方形内的像素全部置成线条颜色。若线宽为,5,，则可把原来的,putpixel,(,x,，,y,，,color),语句改为下列语句组：,for (i = 2; i=2; i+),for (j = 2; j =2; j+),putpixel,(x+i, y+j, color);,这种简单方法将会重复地写像素。这是因为对应于相邻两像素的方形一般会重叠。为了避免重复写像素，可以采用与活化边表类似的技术。为每条扫描线建一个表，存放该扫描线与线条的相交区间左右端点位置。在每个像素使用方形刷子时，用该方形与各扫描线的相交区间端点坐标去更新原表内端点数据。,生成具有宽度的线条还可以采用区域填充的算法。先算出线条各角点，再用直线段把相邻角点连接起来，最后调用多边形填充算法把所得的四边形进行填色，即得到具有宽度的线条。用这种方法还可以生成两端粗细不一样的线条。,2,、 圆弧线宽的处理,为了生成具有宽度的圆弧，可采用与直线情形类似的方法，当采用线刷子时，在经过曲线斜率为,1,的点时，必须把线刷子在水平与垂直方向之间切换。由于线刷子总是置成水平或垂直的，所以在曲线接近水平与垂直的地方，线条更粗一些，而在斜率接近,1,的点附近，线条更细一些，如图,(a),所示。,当采用正方形刷子时，无需改变刷子方向。只需顺着单像素宽的轨迹，把正方形中心对准轨迹上的像素，把方形内的像素全部用线条颜色填充。,(a),用线刷子绘制的圆弧,图,圆弧的线宽,用正方形刷子绘制的曲线条，在接近水平与垂直的部分最细，而在斜率为全,1,的点附近最粗，这恰与线刷子情形相反，如图,(b),所示。,(b),用方刷子绘制的圆弧,3,、 线型的处理,绘制具有宽度的圆弧线条也可以采用填充的办法，先绘制圆弧线条的内边界和外边界，然后在内外边界之间对其填色。可以让内外边界都与单像素弧线轨迹距离半线宽，或把内外边界之一对准单像素弧线轨迹。另一边界线离开此线一个线宽距离。,在绘图应用中常用到不同线型的线条，以便区分各种不同的意义。如采用实线表示立体线框图中可见的轮廓线。用虚线表示不可见的轮廓线，用点划线表示中心线等等。,线型可以用一个布尔值的序列来存放。例如，用一个,32,位整数可以存放,32,个布尔值。用这样的整数存放线型定义时，线型必须以,32,个像素为周期进行重复。,可以把扫描转换算法中的无条件写像素语句改为,if (,位串,i,32),putpixel,(x,，,y,，,color),；,其中,i,为循环变量，在扫描转换算法的内循环中，每处理一个像素递增,1,，然后除以,32,取余。,用这种简单办法实现的线型有个毛病。因为每位对应于算法的一个送代步骤而不是线条上一个长度单位，因此线型中的笔划长度与直线长度有关，斜线上的笔划长度比横向或竖向上的笔划更长。对于工程图，这种变化是不能接受的。这时，每个笔划应该作为与角度无关的线段进行计算并扫描转换。粗线的线型计算为实的或透明的方形，其顶点位置根据线型要求进行准确计算。然后对方形进行扫描转换，对于垂直或水平的粗线线型，可以用写方块的简单办法进行。,