第二节 圆的扫描转换算法 x2+y2=R2

中点画圆法

讨论如何从点(0，R)至 ( ， )的1／8圆周 x坐标为xi的象素(xi,yi)，下一个象素只能是(xi+1,yi) 的P1点或 (xi+1,yi-1) 的P2点

构造函数：F(x,y)=x2+y2-R2 圆上的点，F(x,y)=0 圆外的点，F(x,y)>0 圆内的点，F(x,y)<0 P1和P2的中点为 M=( xi+1,yi-0.5) F(M)<0时，M在圆内，取P1 F(M)>0时，M在圆外，取P2 F(M)=0时，P1或P2随取一个即可，取P2

构造判别式 若d<0，取P1作为下一个象素，而且再下一个象素的判别式为

而若d≥0，应取P2作为下一个象素，而且再下一个象素的判别式 第一个象素是(0,R)，判别式d的初始值为 d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R。

void MidpointCircle(int R) { int x,y; double d; x=0;y=R;d=1.25-R; SetPixel(x,y); while(x<y) { if(d<0) { d+=2*x+3; x++;

} else { d+=2*(x-y)+5; x++; y--; SetPixel(x,y);

在上述算法中，使用了浮点数来表示判别式d。 简化算法，在算法中全部使用整数，使用e=d-0.25代替d。 显然，初始化运算d=1.25-R对应于e=1-R。 判别式d<0对应于e<-0.25。 算法中可把d直接换成e。又由于e的初值为整数，且在运算过程中的增量也是整数，故e始终是整数，所以e<-0.25等价于e<0。

上述算法还可以进一步改进。以提高效率。注意到d的增量是x、y的线性函数，每当x递增1，d递增Δx=2。每当y递减1，d递增Δy =2。由于初始象素为(0,R)，所以Δx的初值为3，Δy的初值为-2R+5。

void MidpointCircle2(int R) { int x,y,deltax,deltay,d; x=0;y=R;d=1-R; deltax=3; deltay=5-R-R; SetPixel(x,y); while(x<y) { if(d<0) { d+=deltax; deltax+=2; x++;

} else { d+=(deltax+deltay); deltax+=2; deltay+=2; x++; y--; SetPixel(x,y);

Bresenham画圆算法 在0≤x≤y的1/8圆周上，象素坐标x值单调增加，y值单调减少。 设第i步已确定（xi,yi）是要画圆上的象素点，看第i+1步象素点（xi+1,yi+1）应如何确定。下一个象素点只能是 或者 中的一个

精确圆弧是③，则dH >0和dD>0．若pi<0，即dH <dD应选H点。若pi≥0，即dH ≥dD应选D点。 若精确圆弧是①或②，显然H是应选择点，而此时dH ≤0，dD>0，必有pi<0。 若精确圆弧是④或⑤，显然D是应选择点，而此时dH >0，dD≤0，必有pi>0。 得出结论： pi做判别量， pi<0选H点为下一个象素点，当pi≥0时，选D点为下一个象素点。

从 计算 当pi≥0时，应选D点，即选

当pi<0时，应选H，即选 画圆的起始点是(0，R)， 即x1=0，y1=R，代入式(11)，令i=1， 就得到：

void BresenhamCircle(int R) { int x,y,p; x=0; y=R; p=3-2*R; for(;x<=y;x++) { SetPixel(x,y); if(p>=0) { p+=4*(x-y)+10; y--; }

只需修改语句SetPixel(x,y)，画八个对称的点，就可以画出全部圆周。若加一个平移，就可以画出圆心在任意位置的圆周。 else { p+=4*x+6; } 只需修改语句SetPixel(x,y)，画八个对称的点，就可以画出全部圆周。若加一个平移，就可以画出圆心在任意位置的圆周。

第四节 区域填充 一、种子填充算法 区域是指光栅网格上的一组象素。 区域填充是把某确定的象素值送入到区域内部的所有象素中。 区域填充方法分为两大类。 区域由多边形围成，区域由多边形的顶点序列来定义;另一类方法是通过象素的值来定义区域的内部，相应的技术称为是以象素为基础的。

内定义区域，定义方法是指出区域内部所具有的象素值,此时区域内部所有象素有某个原值oldvalue; 边界定义区域，定义方法是指出区域边界所具有的象素值。此时区域边界上所有象素具有某个边界boundary value。区域的边界应该是封闭的，并且应该指明区域的内部。 以象素为基础的区域填充主要是依据区域的连通性进行。

四连通:从区域中的一个象素出发，经连续地向上下左右四个相邻象素的移动，就可以到达区域内的任意另一个象素. 八连通:如果除了要经上下左右的移动，还要经左上、右上、左下和右下的移动，才能由一个象素走到区域中另外任意一个象素.

利用区域的连通性进行区域填充，除了需要区域应该明确定义外，还需要事先给定一个区域内部象素，这个象素称为种子。 做区域填充时，要进行对光栅网格的遍历，找出由种子出发能达到而又不穿过边界的所有象素。 这种利用连通性的填充，其主要优点是不受区域不规则性的影响，主要缺点是需要事先知道一个内部象素。

void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue) /*(x，y)为种子 oldvalue是原值 newvalue是新值，应不等于原值。*/ { if (GetPixel(x,y) == oldvalue) { SetPixel(x,y,newvalue);//赋值为新值Floodfill(x,y-1,oldvalue,newvalue);//四向扩散Floodfill(x,y+1,oldvalue,newvalue); Floodfill(x-1,y,oldvalue,newvalue); Floodfill(x+1,y,oldvalue,newvalue); }

void Boundaryfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue) /*(x,y) 为种子位置 boundaryvalue是边界象素值 newvalue是区域内象素新值，未填充前区域内不应有值为newvalue的象素。*/ { if( GetPixel(x,y)!=boundaryvalue && GetPixel(x,y)!=newvalue) // 未达边界且未访问过

{ SetPixel(x,y,newvalue);//赋以新值。 Boundaryfill(x,y-1,boundaryvalue,newvalue);//向四个方向扩散。 Boundaryfill(x,y+1,boundaryvalue,newvalue); Boundaryfill(x-1,y,boundaryvalue,newvalue); Boundaryfill(x+1,y,boundaryvalue,newvalue); }

扫描线种子填充算法 将区域内由边界点限定的同一行内相连接的不具有新值newvalue的一组象素称为一个象素段，象素段用它最右边的象素来标识。 算法的步骤如下： 1．对种子所在象素段进行填充。 2．从右至左检查种子所在行的上一横行，将查得的象素段依次编号存入堆栈。接着对种子所在行的下一横行同样处理。

3．若堆栈为空则算法结束，否则从堆栈顶部取出一个象素段。就以这个象素为新的种子，返回到1。 下面我们用伪C语言写出扫描线填充算法。 void ScanlineSeedfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue) { int x0,xl,xr,y0,xid; int flag; Stack s;

Point p; s.push(Point(x,y));//种子象素入栈 while(!s.isempty()) { p=s.pop(); //栈顶象素出栈 x=p.x; y=p.y; SetPixel(x ,y ,newvalue); x0= x+1; while(GetPixel(x0,y)!=boundaryvalue)//填充右方象素

{ SetPixel(x0 ,y ,newvalue); } xr=x0-1;//最右象素 x0= x-1; while(GetPixel(x0,y)!=boundaryvalue)//填充左方象素 { SetPixel(x0 ,y ,newvalue); x0--;

xl=x0+1;//最左象素 //检查上一条扫描线和下一条扫描线， //若存在非边界且未填充的象素， //则选取代表各连续区间的种子象素入栈。 y0=y; for(int i=1;i>=-1;i-=2) { x0=xr; y=y0+i;

while(x0>=xl) { flag=0; while((GetPixel(x0,y)!=boundaryvalue) && (GetPixel(x0,y)!=newvalue) && (x0>xl)) if(flag==0)

flag=1; xid=x0; } x0--; //将最右侧可填充象素压入栈中 if(flag==1) { s.push(Point(xid,y));

flag=0; } //检查当前填充行是否被中断，若被中断，寻找左方第一个可填充象素 while((GetPixel(x0,y)==boundaryvalue)//判断当前点是否为边界点 ||(GetPixel(x0,y)==newvalue)) //判断当前点是否为已填充点 x0--;//若当前点为边界点或已填充点，根据前面的判断，当前点必然未超出左边界，则当前点向左移动 }//while(x0>=xl)

}//for(int i=1;i>=-1;i-=2) }//while(!s.isempty()) }

二、多边形的扫描转换算法 多边形扫描转换产生面填充的图形。多边形扫描转换可以依据区域的一种“奇偶”性质，即一条直线与任意封闭的曲线相交时，总是从第一个交点进入内部，再从第二个交点退出，以下交替的进入退出，即奇数次进入，偶数次退出。当然可能有一些“相切”的点应特殊处理。 可以分如下三个步骤来做： 1．找出扫描线与多边形边界线的所有交点； 2．按x坐标增加顺序对交点排序； 3．在交点对之间进行填充。

正确的解决办法是，当顶点表现为是局部极大或局部极小时，就看做是二个，否则看做一个。这里一个顶点是局部极大，如果这个顶点的前面和后面各有一些相邻顶点的y坐标，都小于该顶点的y坐标。是局部极小可类似地确定。 实际处理这个问题可以有一个简便办法，那就是对应该看做是一个的顶点，将其上面的边缩短两条相邻扫描线对应的一个单位。

怎样计算扫描线与多边形边界线的交点。注意到若扫描线yi与多边形边界线交点x的坐标是xi，则对下一条扫描线yi+l，它与那条边界线的交点的x坐标xi+1，可如下求出：

活跃边表AET(Active—Edge—Table)，用这个表存贮与当前扫描线相交的各边。每次离开一条扫描线进入下一条之前，将表中有但与下一条扫描线不相交的边清除出表，将与下一条扫描线相交而表中没有的边加入表中。 边表ET(Edge—Table)，ET中各登记项按y坐标递增排序，每一登记项下的“吊桶”按所记x坐标递增排序，“吊桶”中各项的内容依次是：

2．与较小的y坐标对应的边的端点的x坐标xmin。 3．斜率的倒数，即1/m。 1．边的另—端点的较大的y坐标ymax。 2．与较小的y坐标对应的边的端点的x坐标xmin。 3．斜率的倒数，即1/m。 Void Polygonfill(EdgeTableET,COLORREF color) { y=置y为边表ET中各登记项对应的y坐标中最小的值; 活跃边表AET初始化为空表; while(ET表中仍有扫描线未被处理) //处理ET表中的每一条扫描线

{ 将ET中登记项y对应的各“吊桶”合并到表AET中，将AET中各吊桶按x坐标递增排序； 在扫描线y上，按照AET表提供的x坐标对，用color实施填充； 将AET表中有y=ymax的各项清除出表； 对AET中留下的各项，分别将x换为x+1/m，这是求出AET中各边与下一条扫描线交点的x坐标； 由于前一步可能破坏了AET表中各项x坐标的递增次序，故按x坐标重新排序；

y=y+1，去处理下一条扫描线。 }  }

思 考 题 P27：8、10、11。