第2章基本图形生成

第2章基本图形生成现在的计算机能够生成非常复杂的图形,但图形无论多么复杂,它都是由基本图形组合而成的。因此,学习基本图形的生成算法是掌握计算机图形学的基础。本章主要讨论一些基本图形的生成原理,如直线、圆、椭圆的生成问题,二维封闭图形（多边形、圆、椭圆）的填充问题（包括颜色填充、影线填充和图案填充）以及线型和线宽的处理。VisualC++的CDC图形程序库已提供了画线、画圆和椭圆、填充等基本图形的绘制函数,它们实质上是按计算机图形标准并以C++的语法约定提供给用户使用的标准图形生成算法。因此,从实用的角度出发,用户只需完全按照C++的语法约定使用这些图形程序库,就没有必要学习基本图形的生成原理及算法。但是,基于下面的二个理由,我们认为学习本章介绍的基本图形生成原理及算法是非常有必要的。第二,VisualC++虽然提供了许多绘图函数,但总有满足不了用户特殊绘图要求的时候。如果仅仅学会使用VisualC++的绘图函数,不掌握基本图形生成原理及算法,那么你就永远无法超越VisualC++的限制。第一,基本图形生成原理及算法是计算机图形学的基本原理,如果不学习这些基本原理,那么以后还要涉及的其他计算机图形学原理就无从谈起；众所周知,目前我们使用的主要图形输出设备显示器和打印机本质上是一种画点设备,是由一定数量的网格状细小光点,使其某些像素亮,某些像素不亮来显示图形或文字的。所谓的基本图形生成原理是指在点阵输出设备的情况下,如何对一条斜的直线或弯曲的曲线尽可能快地输出其最接近理想的直线或曲线。图3-1用一系列的象素点来逼近直线

本章我们主要以光栅图形显示器为例讨论基本图形的生成原理及算法。我们假定,编程语言（以C语言为例）提供了一个最底层的像素操作函数：putpixel(x,y,

color)；

2.1直线的生成在计算机上画线一般都是给定两个坐标点(x1,y1)和(x2,y2),要求画出它们的直线。当要在屏幕上显示一条直线时,只能在显示器所给定的有限个像素矩阵中,确定最佳逼近于该直线的一组像素,对这些像素进行写操作。这就是通常所说的在显示器上绘制直线,或直线的扫描转换。直线的斜率截距方程为：

y=k·x+b(3–1)其中,k表示斜率,b是y轴截距。为此,只需让x从起点到终点每次增加(或减少)1,用(3–1)式计算对应的y值,再用putpixel(x,

(int)(y+0.5),color)函数输出该像素的颜色值即可。

xi+1=xi+1

yi+1=kxi+1+b给定线段的两个端点(x1,y1)和(x2,y2),可以计算出斜率k和截距b：

k=△y／△x=(y2–y1)/(x2–x1)

b=y1–k·x1

但是,用这种方法画线效率太低,这是因为每步都需要一个浮点乘法运算和一个四舍五入运算。为此我们要寻找更快的画线方法。2.1.1数值微分法

对直线上任何给定的x的增量△x和y的增量△y,有下列计算公式：△y=

k·△x(3–2)或△x=△y/k(3–3)

当斜率绝对值|k|<1时：△x>△y

可以让x从起点到终点变化,每步递增(或递减)1,即令△x=±1,则△y=±k。若前一次的直线上像素点坐标为(xi,yi),这一次的直线上像素点坐标为(xi+1,yi+1),则xi+1=xi±1,yi+1=yi±k。随后用putpixel函数输出该像素的颜色值即可。见图2.1。(xi,yi)(xi,(int)(yi+0.5))(xi+1,yi)(xi+1,(int)(yi+0.5))图2.1数值微分法示意图

当|k|>1时,

△x<△y可以让y从起点到终点变化,每步递增(或递减)1,即△y=±1,用(3–3)式计算对应的x增量,即△x=±1/k。若前一次的直线上像素点坐标为(xi,

yi),这一次的直线上像素点坐标为(xi+1,yi+1),则yi+1=yi±1,xi+1=xi±1/k。随后用putpixel函数输出该像素的颜色值即可。

上述采用的增量计算方法称为数值微分算法(DigitalDifferentialAnalyzer简称DDA)。以下是用数值微分算法(DDA)生成直线(斜率在0～l)的C语言描述。voidDDALine(intx1,inty1,intx2,inty2,intcolor){intx;floatk,dx,dy,y=y1;dx=x2-x1;dy=y2-y1;k=dy/dx;for(x=x1;x<=x2;x++){putpixel(x,(int)(y+0.5),color);y=y+k;}}2.1.2中点画线法

这里先讨论直线斜率在0～l之间。如图2.2所示,若直线在x方向上增加一个单位,则在y方向上的增量只能在0～1之间。假设直线上当前已确定的一个像素点坐标为(xp,yp),用实心小圆表示。P=(xp,yp)P2P1MQ图2.2中点画线法示意图

那么,下一个与直线最近的像素只能是正右方的P1(xp+1、yp)或右上方的P2(xp+1、yp+1)两者之一,用空心小圆表示。为了确定出下一个像素是P1还是P2设M为P1与P2的中点,即M=(xp+1,yp+0.5)Q是理想直线与垂直线x=xp+l的交点。显然,若M在Q的上方,则P1离直线近,应取为下一个像素；否则应取P2。这种以中点M作为判别标志的方法就是中点画线算法。下面来讨论中点画线法的具体实现。直线方程为：F(x,y)=ax+by+c＝0假设直线的起点和终点分别为(x1,y1)和(x2,y2),则上述参数：a=y1-y2,b=x2-x1,c=

x1y2-x2y1。P=(xp,yp)P2P1MQ对于直线上的点,F(x,y)=0；对于直线上方的点:F(x,y)>0；对于直线下方的点,F(x,y)<0。因此,欲判断前述Q在M的上方还是下方,只要把

M代入

F(x,y),并判断它的符号。

构造判别式

d＝F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当

d>0时,M在直线上方（即在Q的上方）,故应取右方的P1作为下一个像素。而当d<0,则应取右上方的P2。当d=0时,约定取右方P1。

对每一个像素计算判别式d,根据它的符号确定下一像素。由于d是xp和yp的线性函数,可采用增量计算,以便提高运算效率。在d≥0的情况下,取正右方像素P1(xp+1,yp)欲判断再下一个像素应取那个,应计算

d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c

=(a(xp+1)+b(yp+0.5)+c)+a=d+a故d的增量为a。在d<0时,取右上方像素P2(xp+1,yp+1)。要判断再下一个像素,应计算

d2=F(xp+2,yp+l.5)=a(xp+2)+b(yp+1.5)+c

=(a(xp+1)+b(yp+0.5)+c)+a+b=d+a+b再看d的初始值。直线的第一个像素为左端点(x1,y1),所以相应的判别式值为

d0=F(x1+1,y1+0.5)=a(x1+1)+b(y1+0.5)+c=(ax1+by1+c)+a+0.5b=F(x1,y1)+a+0.5b由于(x1,y1)在直线上,故F(x1,y1)

=0。因此,d的初始值为d0=a＋0.5b。由于我们使用的只是d的符号,而且d的增量都是整数,只是其初始值包含小数。因此,我们可以用2d代替d,就可以写出仅包含整数运算的中点画线算法(斜率在0～l)：

故d的增量为a＋b。

voidMidpointLine(intx1,inty1,intx2,inty2,intcolor){intx,y,a,b,d1,d2,d;a=y1-y2;b=x2-x1;d=2*a+b;d1=2*a;d2=2*(a+b);x=x1;y=y1;putpixel(x,y,color);while(x<x2){x=x+1;if(d<0){y=y+1;d+=d2;}else{d+=d1;}putpixel(x,y,color);}}中点法绘制直线实例例2.1：已知直线段的起点为（0,0）,终点为（5,2）,用中点算法求出线段各像素坐标值。

解：直线段的起点x=0,y=0,dx=5,dy=2,d0=5-2*2=1d0=1>0,x=1y=0,直线段的第二个像素点坐标为（1,0）；d1=d0-4=-3<0,x=2,y=1,直线段第三个像素点坐标为（2,1）d2=d1+10-4=3>0,x=3,y=1,直线段第四个像素点坐标为（3,1）d3=d2-4=-1<0,x=4,y=2,直线段第五个像素点坐标为（4,2）d4=d3+10-4=5<0,x=5,y=2,直线段第六个像素点坐标为（5,2）d0=a＋0.5b=2a+bd1=d+ad2=d+a+b2.1.3Bresenham画线算法

1965年,Bresenham提出了一种更好的直线生成算法,称为Bresenham算法。此算法的一个主要思想是借助于一个决策变量dk,来确定下一个该点亮的像素点。

对于直线斜率k在0～1之间的情况,如图2.3所示,从给定线段的左端点(x1,y1)开始,逐步处理每个后续列(x位置),并在扫描线y值最接近线段的像素上绘出一点。假设当前直线上的像素已确定,其坐标为(xk,yk)。那么下一步需要在列xk+1上确定扫描线y的值。y值要么不变,要么递增1。

在列位置xk+1,用d1和d2来标识两个候选像素的y值与线段上理想y值的差值,则：

d1=y–yk=(k(xk+1)+b)–yk

d2=(yk+1)–y=yk+1–(k(xk+1)+b)那么

d1–d2=2k(xk+1)–2yk+2b–1xkykyk+1yxk+1d1d2图2.3

两个候选像素的y值与线段上理想y值的差值d1和d2设△y=y2–y1和△x=x2–x1,则k=△y/△x,代入上式,得：△x(d1–d2)=2△y·xk–2△x·yk+c(3–4)当dk>0时,直线上理想位置与右上方像素(xk+1,yk+l)更接近,所以应取右上方像素；而当dk<0时,右方像素(xi+l,y)与直线上理想位置更接近,应取右方像素；当dk=0时,两个候选像素与直线上理想位置一样接近,约定取(xk+l,yk+1)。

若令dk=△x(d1–d2),并称dk为画线中第k步的决策参数,则dk的计算仅包含整数运算,它的符号与d1–d2的符号相同。c为常量,在计算中将被消除。

在k+1步,决策参数可从方程(3–4)算出：

dk+1=2△y·xk+1–2△x·yk+1+c从上述方程中减去方程（3–4）,可得：

dk+1–dk=2△y(xk+1–xk)–2△x(yk+1–yk)已知xk+1=xk+1,因而得到：

dk+1=dk

+2△y–2△x(yk+1–yk)若取右上方像素,yk+1–yk=1,则：

dk+1=dk

+2△y–2△x若取右方像素,yk+1=yk,则：

dk+1=dk

+2△y

在每个整数x位置,从线段的坐标端点开始,反复进行决策参数的这种循环计算。在起始像素(x1,y1)的第一个参数d0可从方程(3–4)及k=△y/△x计算出：以下是Bresenham算法的C语言描述(斜率在0～l)。

d0=2△y·x1–2△x·y1+2△y+△x·(2b-1)=2△y·x1–2△x·(k·x1+b)+2△y+△x·(2b-1)=2△y·x1–2k△x·x1-2b△x+2△y+2b△x-△x

=2△y·x1–2(△y/△x)△x·x1+2△y-△xd0=2△y–△xvoidBresenham_Line(intx1,inty1,intx2,inty2,intcolor){intx,y,dx,dy,dk,I;dx=x2–x1;dy=y2–y1;dk=2dy–dx；x=x1;y=y1;for(i=0;i<=dx;i++){putpixel(x,y,color);x=x+1;dk=dk+2*dy;if(dk>=0){y=y+1;dk=dk–2*dx;}}}2.2圆与椭圆的生成下面仅以圆心在原点、半径R为整数的圆为例,讨论圆的生成算法。假设圆的方程为：X2+Y2=R2圆的特征:八对称性。只要扫描转换八分之一圆弧,就可以求出整个圆弧的象素集(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)解决问题：简单方程产生圆弧算法原理：利用其函数方程,直接离散计算圆的函数方程为：圆的极坐标方程为：1.中点画圆法利用圆的对称性,只须讨论1/8圆：第二个8分圆P为当前点亮象素,那么,下一个点亮的象素可能是P1（Xp+1,Yp）或P2（Xp+1,Yp+1)。MP1P2P（Xp,Yp）算法原理构造函数：F（X,Y）=X2+Y2-R2；则

F（X,Y）=0（X,Y）在圆上；F（X,Y）<0（X,Y）在圆内；F（X,Y）>0（X,Y）在圆外。设M为P1、P2间的中点,M=(Xp+1,Yp-0.5)MP1P2有如下结论：

F（M）<0->M在圆内->取P1F（M）>=0->M在圆外->取P2为此,可采用如下判别式：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,则P1为下一个象素,那么再下一个象素的判别式为：

d1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3即d的增量为2xp+3P1MP2算法原理若d>=0,则P2为下一个象素,那么再下一个象素的判别式为：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+（2xp+3）+（-2yp+2）即d的增量为2(xp-yp)+5.d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-RMP1P2算法原理voidCTestView::OnMindpointcircle(){ CDC*pDC=GetDC(); intx=100,y=200,r=150,color=RGB(0,0,255);floatd; x=0;y=r;d=1.25-r; pDC->SetPixel(x,y,color); while(x<=y) { if(d<0)d+=2*x+3; else{d+=2*(x-y)+5;y--;} x++; pDC->SetPixel(x,y,color);} }算法程序为了进一步提高算法的效率,可以将上面的算法中的浮点数改写成整数,将乘法运算改成加法运算,即仅用整数实现中点画圆法。使用e=d-0.25代替de0=1-R可以更快地实现圆的生成算法改进voidCTestView::OnMindpointcircle(){ CDC*pDC=GetDC(); intx0=150,y0=120,r=100,color=RGB(0,0,255),x,y,d;

x=0;y=r;d=1-r; pDC->SetPixel(x,y,color); while(x<=y) { if(d<0)d+=2*x+3; else{d+=2*(x-y)+5;y--;} x++; pDC->SetPixel(x,y,color);

pDC->SetPixel(-x+x0,y+y0,color); pDC->SetPixel(-x+x0,-y+y0,color); pDC->SetPixel(x+x0,-y+y0,color); pDC->SetPixel(y+x0,x+y0,color); pDC->SetPixel(-y+x0,x+y0,color); pDC->SetPixel(-y+x0,-x+y0,color); pDC->SetPixel(y+x0,-x+y0,color);}ReleaseDC(pDC);}算法实现

该算法以点(0,r)为起点,按顺时针方向生成圆时,相当于在第一象限内,所以y是x的单调递减函数。y的计算式为：令d1、d2分别为yi到y、yi-1到y的距离,可知：

令判断式di=d1-d2,并代入d1、d2,则有：

（0,r)yx(xi,yi)2.Bresenham画圆法（1）如果di<0,则y=yi,即选择当前像素的正右方作为下一个像素,递推公式为：（2）如果di≥0,则y=yi-1,即选择当前像素的右下方作为下一个像素,递推公式为：（3）计算判别式的初值。初始点为（0,R）,则：算法实现voidCMyView::OnBresenhamcircle(){ CDC*pDC=GetDC(); intx0=100,y0=100,x,y,r=80,c=0;//黑色圆弧

floate,d; e=3-2*r;x=0;y=r; while(x<=y) { if(e<0) {e=e+4*x+6;x++;} else{e=e+4*(x-y)+10;x++;y--;} pDC->SetPixel(x+x0,y+y0,c); pDC->SetPixel(-x+x0,y+y0,c); pDC->SetPixel(-x+x0,-y+y0,c); pDC->SetPixel(x+x0,-y+y0,c); pDC->SetPixel(y+x0,x+y0,c); pDC->SetPixel(-y+x0,x+y0,c); pDC->SetPixel(-y+x0,-x+y0,c); pDC->SetPixel(y+x0,-x+y0,c); } ReleaseDC(pDC);}3.椭圆的生成算法1.椭圆的特征椭圆函数:对于椭圆上的点,有F(x,y)=0；对于椭圆外的点,F(x,y)>0；对于椭圆内的点,F(x,y)<0。1.椭圆的特征解决第1象限问题：以弧上斜率为－1的点作为分界将第一象限椭圆弧分为上下两部分。引理：若在当前的中点（xm,ym）,法向量的y分量比x分量大,即：而在下一个中点,不等号改变方向,则说明椭圆弧从上部分转入下部分。法向量1.椭圆的特征先推导上半部分的椭圆绘制公式2.上部分算法推导判别式若di≤0,取Pu(xi+1,yi)若di>0,取Pd(xi+1,yi-1)2.上部分算法推导di≥0：判别式的初始值：增量为：2.上部分算法推导再来推导椭圆弧下半部分的绘制公式原理3.下部分算法推导判别方法：

若di≥0,取Pl(xi,yi-1)若di<0,取Pr(xi+1,yi-1)3.下部分算法推导误差项的递推,di≥0：增量：3.下部分算法推导4.中点椭圆算法小结第Ⅰ象限内椭圆弧的中点算法可以概括为：算法实现voidCTestView::OnMidpointellispe(){CDC*pDC=GetDC();inta=100,b=300,x,y,color=50;floatd1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);pDC->SetPixel(x,y,color);pDC->SetPixel(-x,-y,color);pDC->SetPixel(-x,y,color);pDC->SetPixel(x,-y,color);while(b*b*(x+1)<a*a*(y-0.5)){if(d1<=0){d1+=b*b*(2*x+3); x++;}else{d1+=b*b*(2*x+3)+a*a*(-2*y+2); x++;y--;}

pDC->SetPixel(x,y,color);pDC->SetPixel(-x,-y,color);pDC->SetPixel(-x,y,color);pDC->SetPixel(x,-y,color);}/*while上半部分*/d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;while(y>0){if(d2<=0){ d2+=b*b*(2*x+2)+a*a*(-2*y+3); x++;y--;}else{ d2+=a*a*(-2*y+3);y--;}pDC->SetPixel(x,y,color);pDC->SetPixel(-x,-y,color);pDC->SetPixel(-x,y,color);pDC->SetPixel(x,-y,color);} }2.3图元属性及走样控制图元的基本表现是线段,其基本属性包括线型、线宽和色彩。任何影响图元显示方法的参数称为属性参数。1.线型：实线、虚线、点线等。通过设置沿直线路径显示的实线线段的长度和间距来修改画线算法,产生各种类型的直线。

在显示器上实现具有一定宽度的直线,可以沿着生成直线时获得的象素点,通过移动一把具有一定宽度的“刷子”来实现。垂直线刷子:假设直线斜率在[-1,1]之间,把刷子放置成垂直方向,刷子中点对准直线一端点,然后让刷子中点往直线的另一端移动,即可“刷出”具有一定宽度的线。水平线刷子:直线斜率不在[-1,1]之间,可以把刷子放置成水平方向,刷子中点对准直线一端点并往直线的另一端移动,即可“刷出”具有一定宽度的线。

方形刷子:把边宽为指定线宽的正方形的中心沿直线作平行移动,即可获得具有线宽的线条。生成具有宽度的线条还可以采用区域填充的算法。2.线宽控制3.反走样用离散量表示连续量引起的失真,就叫做走样。走样现象：一是光栅图形产生的阶梯形一是图形中包含相对微小的物体时,这些物体在静态图形中容易被丢弃或忽略,在动画序列中时隐时现,产生闪烁用于减少或消除这种效果的技术,称为反走样简单方法：提高分辨率简单区域取样加权区域取样反走样技术

重叠过取样基于加权模板的过取样2.4平面区域填充表示一个区域

边界（闭合的线段）+填充（灰度或色彩）多边形区域填充：给出一个区域的定义,要求对此区域范围内的所有像素赋予指定的颜色代码多边形的扫描转换主要是通过确定穿越区域的扫描线的覆盖区间来填充区域填充是从给定的位置开始涂描直到指定的边界条件为止。（一）区域的表示及类型区域的表示有两种：顶点表示和点阵表示

顶点表示也称为几何表示,是用多边形的顶点序列来表示区域。点阵表示也称像素表示,是用位于多边形内的像素集合来刻画多边形。

（一）区域的表示及类型

点阵表示通常有两种情况：内点表示和边界表示。在内点表示中,区域内所有像素具有同一颜色,区域以外的所有像素是另外一种颜色；在边界表示中,区域边界上的所有像素具有特定的颜色（可以是填充颜色）,在区域内、外的所有像素均不能具有这种颜色。（一）区域的表示及类型

区域填充算法要求区域是连通的,因为只有在连通区域中,才能将种子点的颜色扩充到区域内的其他点。区域按连通情况可分为四连通区域和八连通区域。四连通区域是指从区域上一点出发,可通过上、下、左、右4个方向移动,在不越出区域的前提下到达区域内的任意像素；八连通区域是指从区域内每一像素出发,可通过上、下、左、右、左上、右上、左下、右下8个方向的移动,在不越出区域的前提下到达区域内的任意像素。

区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果例如:有的图形其边界像素是8连通的而内部像素是4连通的1.填充点的判别方法“扫描线交点的奇偶数判断”法：用一根水平扫描线自左而右通过多边形而与多边形的边界相交,扫描线与边界相交奇次数后进入该多边形,相交偶次数后离开该多边形。

（二）多边形的扫描转换有些在多边形顶点处的扫描线交点需要专门处理。在这些位置上,扫描线通过一个顶点与多边形的两条边相交。例如图所示,若交点算一个,则扫描线2与P6相交,求得交点(x坐标)序列3,6.5,7.5。这将导致[3,6.5]区间内的像素被填充,而这个区间的像素是属于多边形外部,不需要填充。若交点算二个,则扫描线7与P1相交,求得交点(x坐标)序列2,2,10。这将导致[2,10]区间内的像素不被填充,而这个区间的像素是属于多边形内部,需要填充。

ABCDP1P2P3P4P5P62468102468Oyx为了正确地进行交点取舍,必须对上述两种情况区别对待。在第一种情况,扫描线交于一顶点,而共享顶点的两条边分别落在扫描线的两边。这时,交点只算一个。在第二种情况,共享交点的两条边在扫描线的同一边,这时交点作为零个或两个,取决于该点是多边形的局部最高点还是局部最低点。具体实现时,只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定是取零个、一个、还是两个。2.交点的异常处理（1）当奇点在多边形两边之下方时,该点计为2个点,如图中的P1、P3和P5点。（2）当奇点在多边形两边之上方时,该点计为0个点,如图中的P2、P4和P6点。（3）当奇点在多边形两边之间时,该点计为1个点,如图中的P7点。具体实现时,只需检查顶点两条边的另外两个端点的y值,由这两个y值中大于交点y值的个数是0、1、2来决定。（4）扫描线与多边形的水平边重合,理论上是无穷多个交点,但在实际处理时不计其交点。10x2134567891111121012y123456789ABCDP1P2P3P4P5P6P7P00111102223.算法步骤：(1)确定多边形所占有的最大扫描线数,得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax,每次用一条扫描线进行填充。(3)对生成的多边形进行填充的过程可分为四个步骤： a.求交点 b.交点排序：按X值递增顺序排序 c.交点配对 d.区间填色有效边（ActiveEdge）：指与当前扫描线相交的多边形的边,也称为活性边。有效边表（ActiveEdgeTable,AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中,此链表称为有效边表。有效边表的每个结点：（三）有效边表算法（Y连贯性算法）原理：处理一条扫描线时,仅对有效边求交利用扫描线的连贯性利用多边形边的连贯性边表（EdgeTable）的构造：(1)首先构造一个纵向链表,链表的长度为多边形所占有的最大扫描线数,链表的每个结点,称为一个桶,则对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。即某边最低端点的x坐标放进相应扫描线桶中。(3)每条边的数据形成一个结点。同一桶中若干条边按x由小到大排序,若x相等,则△x由小到大排序。10x2134567891111121012y123456789ABCDP1P2P3P4P5P6P7P0算法步骤：①初始化：构造边表ET,AET表置空,取扫描线纵坐标y的初值置为ET中非空元素的最小序号,如在上图中,y=1。②按从下到上的顺序对每条扫描线重复以下各步,直至ET和AEL都为空。将ET中与当前y有关的结点加入至AET,同时保存AET中按x值从小到大实现的排列序列；对于AEL中的扫描线y,交点两两配对,在每一对交点之间填充填充所需的像素值；在AEL中删掉y≥ymax的结点。对于留在AEL中的每个结点,执行xi+1=xi+1/k；对AET中的各结点按x值从小到大排序；yi+1=yi+1成为下一条扫描线的坐标,根据计算并修改AET表,形成新的AET表。

1.边缘填充算法也称为正负相消法。该填充算法的基本原理是：对每一条扫描线,依次求与多边形各边的交点,将该扫描线上交点右边的所有像素求补。多边形所有边处理完毕,填充即完成。（四）边填充算法2.栅栏填充算法栅栏指的是一条过多边形顶点且与扫描线垂直的直线,它将多边形分成两半,只要将栅栏与多边形之间的像素求补即可。栅栏填充算法的基本原理是：对于每条扫描线与多边形的交点,将交点与栅栏之间的扫描线上的像素取补,也就是说,若交点位于栅栏左边,则将交点之右、栅栏之左的所有像素取补；若交点位于栅栏右边,则将栅栏之右、交点之左的所有像素取补。

（五）种子填充算法区域是指已经表示成点阵形式的填充图形,它是像素集合。根据填充方向分4-连通区域和8-连通区域。区域两种表示形式：边界表示：把位于给定区域的边界上的象素一一列举出来的方法。区域的边界点有相同颜色。其填充算法有扫描线填充算法或边界填充算法（Boundary-fillAlgorithm）。内点表示：枚举出给定区域内所有象素的表示方法。即区域内的所有象素有相同的颜色。其填充算法常为种子填充或泛填充算法（递归算法）1.边界表示的四连通区域种子填充算法基本思想：从多边形内部任一点像素出发,按照“左上右下”的顺序判断相邻像素,若不是边界像素且没有被填充过,则对其填充,并重复上述过程,直到所有像素填充完毕。可以使用栈结构来实现该算法,种子像素入栈,当栈非空时,重复执行如下操作：（1）栈顶像素出栈；（2）将出栈像素置成多边形填充的颜色；（3）按“左上右下”的顺序检查与出栈像素相邻的四个像素,若其中某个像素不在边界上且未置成多边形色,则把该像素入栈。设(x,y)为边界表示的四连通区域内的一点,bcolor为定义区域边界的颜色,要将整个区域填充为新的颜色ncolor,边界表示的四连通区域的递归填充算法如下：voidBoundaryFill(int

x,int

y,int

bcolor,int

ncolor){color=GetPixel(x,y)；

if((color!=bcolor)&&(color!=ncolor)){PutPixel(x,y,ncolor)；

BoundaryFill(x-1,y,bcolor,ncolor)；

BoundaryFill(x,y+1,bcolor,ncolor)；

BoundaryFill(x+1,y,bcolor,ncolor)；

BoundaryFill(x,y-1,bcolor,ncolor)；

}}1算法功能：按顺序重新着色顺序：上下左右思考：如果是左上右下顺序呢？请填写右下图序号23465其它颜色1其它颜色12463456789101112131415161718192021222324252627282930313233343536373839404142434445P递归填充算法（上下左右）：VoidFill(intx,inty,intbcolor,intncolor){intcolor；color=GetPixel(x,y)；if((color!=bcolor)&&(color!=ncolor)){PutPixel(x,y,ncolor)；Fill(x,y+1,bcolor,ncolor)；Fill(x,y-1,bcolor,ncolor)；Fill(x-1,y,bcolor,ncolor)；Fill(x+1,y,bcolor,ncolor)；}}思考：如果换成左上右下的顺序呢？2.内点表示的四连通区域种子填充算法基本思想：从多边形内部任一点像素出发,按照“左上右下”的顺序判断相邻像素,如果是区域内的像素,则对其填充,并重复上述过程,直到所有像素填充完毕,常称为漫水法。可以使用栈结构来实现该算法,种子像素入栈,当栈非空时,重复执行如下操作：（与边界表示类似）（1）栈顶像素出栈；（2）将出栈像素置成多边形填充的颜色；（3）按“左上右下”的顺序检查与出栈像素相邻的四个像素,若其中某个像素不在边界上且未置成多边形色,则把该像素入栈。(2)当栈非空时,重复如下步骤:从栈顶弹出一个像素,将该像素置成填充色;按右、上、左、下顺序检查与该像素相邻的四个像素是否是边界像素或者是否已被置填充色:若是,返回（2）；若不是,将该像素入栈后,返回（2）。

简单的种子填充算法它适合四连通、边界定义的区域。(1)种子像素入栈;

SABCDEFGH

GGGGGGHG

HHGGGGGG

HHGGGG

HHGH

HEFHDGSCBA下左上右此算法如何修改,便可适合八连通区域？简单的四连通种子填充算法的应用主要缺点是什么？此例中栈的最大深度为几层？简单的种子填充算法应用6754S9328S247938479484795684796847978479847994794796754S9328S799下左上右算法特点：可以用于填充带有内孔的平面区域。把太多的象素压入堆栈,有些象素会入栈多次,降低算法效率；栈结构占空间改进： 减少递归次数,提高效率。通过沿扫描线填充水平象素段,来代替处理4-邻接点和8-邻接点。方法之一：扫描线填充算法3.扫描线种子填充算法基本思想：在任意不间断区间（一条扫描线上的一组相邻像素）中,只取一个种子像素,填充当前扫描线上的该段区间,然后确定与这一区段相邻的上下两条扫描线位于区域内的区段,并依次把它们保存起来,反复进行这个过程,直到所保存的每个区段都填充完毕。算法执行步骤：1）初始化：堆栈置空,将种子点(x,y)入栈。2）出栈：若栈空则结束,否则栈顶元素(x,y)出栈,并以y值作为当前扫描线号。3)填充并确定种子点所在区段：从种子点(x,y)出发,沿当前扫描线向左、向右两个方向逐个像素填充,直到遇到边界像素为止。分别标记区段的左、右端点坐标为xl和xr。4)确定新的种子点：在区间[xl,xr]中检查与当前扫描