第3章生成算法

第三章 基本图形生成算法（书P107）本章讲直线、圆弧的生成及多边形填充的算法。

一．概念◆ 基本图形元素：指构成图形的基本元素，例如：点、直线、圆弧等。

◆ 象素：屏幕上的光点，它是最小的屏幕显示单位，其大小取决于显示器的尺寸和分辨率。

用坐标表示。

◆ 生成图形：确定最佳逼近于图形的象素，用图形颜色对象素进行写操作。

这称为图形的扫描转换。

◆ 生成直线的质量要求：①直线要直。

②直线的端点要准确，即无定向性和断裂情况。

③直线的亮度、色泽均匀。

④画线的速度要快。

二．直线生成算法下面介绍画一个象素宽的直线的三种常用算法：1．数值微分法（DDA ）所谓DDA 法就是先计算出直线的斜率K=xy ∆∆(其中Δy =y 1- y 0 , Δx= x 1- x 0 ,而（x 0 ，y 0）和（x 1 ,y 1）分别是直线的起点和终点)，然后从直线的起点开始，确定最佳逼近于直线的y 坐标，让x 从起点到终点变化，x 每递增1，计算对应的y 坐标。

令y=kx+b, 当x i+1 =x i +Δx 时y i+1=kx i+1+b=k(x i +Δx)+b= kx i +Δxk+b= kx i +b+Δxk= y i +Δxk= y i +k算法如下：DDAline(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;{int x;float dx,dy,k,y;dx=x1-x0;dy=y1-y0;k=dy/dx; 注意+0.5y=y0;for (x=x0;x<=x1;x++){putpixel (x,(int)(y+0.5),color); y=y+k;} 网格的交点表示象素}注意上述算法仅适用于│k│<=1的情况,见程序linedda.c 。

若│k│>1，必须把x,y 的角色互换，y 每增加1，x 相应增加1/k 。

书P108 的算法（DDA.c ）综合了各种情况。

2．中点画线法则y方向上的增量只能是0或1。

如图中假设P与直线最接近的象素已确定，其坐标为（x p ,y p）,那么下一个与直线最近的象素只能是P1(x p +1¸ y p)或P2(x p +1¸ y p+1)两者之一。

用M表示P1与P2的中点，即M=（x i +1¸ y i+0.5）。

若M在直线上方，则取P1 ;否则取P2。

这就是中点画线法的基本原理。

下面讨论中点画线法的实现。

设直线的起点和终点分别为（x0 ,y0）和（x1 ,y1），则直线方程为：F (x,y)= y-kx-b=0 其中，k为斜率，b为截距。

对于直线上的点F(x,y)=0; 对于直线上方的点F(x,y)>0; 对于直线下方的点F(x,y)<0。

因此要判断上图中Q(直线与垂直线的交点)在中点M的上方还是下方，只要把M代入F(x,y),并判断它的符号。

即F(M)=F(xi +1,yi +0.5)= yi +0.5–k（xi +1）–b，当F(M)<0时，M在直线的下方（即在Q的下方），故应取右上方的P2作为下一个象素。

而当F(M)>0时，则应取正右方的P1作为下一个象素。

当F(M)=0时，二者一样合适，可任选一个。

算法如下：MidpointLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;{ int x,y;float mid,k,b;k=(y1-y0)/(x1-x0);b=y0- k* x0;x=x0;y=y0;putpixel(x,y,color);do{ mid= y+0.5– k*(x+1)-b;if (mid<0) y++;x++;putpixel(x,y,color);} while (x<x1);}注：0<=k<=1。

为提高运算效率，可计算出mid的递推关系式，推导过程如下：在mid>=0的情况下，取正右方象素P1，欲判断再下一个象素应取那个，递推关系式为：F(x i+2 ,y i+0.5)= y i +0.5 -k(x i +2)-b= y i +0.5-k(x i +1)-b-k;= mid-k;在mid<0的情况下，则取右上方象素P2，要判断再下一个象素，则要计算F(x i+2 ,y i+1.5)= y i +1.5-k(x i +2)-b= y i +0.5-k(x i +1)-b+1-k=mid+1-k;F(M)的初始值为：F(x 0 +1,y 0 +0.5)= y 0 +0.5-k (x 0 +1)-b= y 0 -kx 0 - b + 0.5-k= F(x 0 ,y 0)+0.5-k=0.5-k由于(x 0 ,y 0 )在直线上，故F(x 0 ,y 0 )=0。

这样算法改为：MidpointLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;{ int x,y,mid,dx,dy,d_up,d_down;dy=y1-y0;dx=x1-x0;mid=dx-2*dy; /*mid 应该为0.5-k , 为了摆脱实数运算扩大2dx 倍*/d_up =2*dx - 2*dy;d_down = -2*dy; /*注意扩大了2dx 倍*/x=x0;y=y0;while (x<=x1){ putpixel(x,y,color);x++;if (mid<0) {y++;mid=mid+d_up;}else mid=mid+ d_down;}}作业1：用中点画线法光栅化一条连接两点(0,0)和(5,3) 的一条直线。

3．Bresenham 画线算法Bresenham 也是通过在每列象素中确定与理想直线最近的象素来进行画线的。

该算法是最为流行的画线方法，它将直线方程转换成一个迭代过程。

与中点画线法类似，只是判中点的方法不同。

如下图所示，只要判直线与垂线的交点到网格线的距离d ，当d>0.5往右上方走一步(当x i+1 =x i +1时, y i+1 =y i +1) ；当d<0.5时，往正右方走一步(当x i+1 =x i +1时, y i+1 =y i )。

从上图可得：⎩⎨⎧>-+<+=+时当时当5.015.01i ii i i d k d d kd d 为计算方便，令e=d-0.5, 所以有：⎩⎨⎧>-+=--+<+=-+=+时当时当015.0105.01i i i i i i i e k e k d e k e k d e初始的e 0= -0.5. 即有：⎪⎩⎪⎨⎧⎩⎨⎧>+<=+=++）（）（010111i i i i i i i e y e y y x x这种方法比中点画线法简单。

算法如下：BrsenhamLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;{int x,y,dx,dy,i;float k,e;dx=x1-x0;dy=y1-y0;k=dy/dx;e=-0.5;x=x0;y=y0;for(i=0;i<=dx;i++){ putpixel(x,y,color);x++; e=e+k;if (e>0){y++;e=e-1;}}}此算法适用于0<=k<=1。

此算法中用到除法，改进后见P113。

作业2：从键盘输入封闭多边形的端点坐标（任意斜率），试分别采用中点画线算法和Bresenham 算法画出该多边形。

（上机实现）三．圆的生成算法画圆的方法很多。

在本节中，主要讨论三种生成圆的算法一般方法有：直角坐标法：根据圆的方程x 2+y 2=R 2 来生成，如x i+1=x i +1, y=(int)(212+-i x R +0.5)。

极坐标法：用圆的极坐标方程（参数方程）圆x2+y2=R2的参数方程为：x=R*cosθy=R*sinθ 0<=θ<=360#include<graphics.h>#include<math.h>#define pi 3.14159main(){int driver,mode,x,y,maxx,maxy,r=60;float t;driver=DETECT;initgraph(&driver,&mode,"");maxx=getmaxx();maxy=getmaxy();line(0,maxy/2,maxx,maxy/2);line(maxx/2,0,maxx/2,maxy);for (t=0;t<=2*pi;t+=0.01){ x=maxx/2+r*cos(t);y=maxy/2+r*sin(t);if (t==0)moveto(x,y);lineto(x,y);}getch();closegraph();}1．绘圆的正负法设所要画的圆的圆心在（a,b）,半径为R，则圆的方程为：F(x,y)= (x- a)2 +(y- b)2-R2=0，当点(x,y)在圆内时，F(x,y)<0；当点(x,y)在圆外时，F(x,y)>0。

现以画第一四分之一圆弧(第一象限)为例说明正负画圆算法。

设P i (x i,y j)是已求得的象素点，那么找下一个点P i+1的原则为：当F(x i,y j)<=0时，取x i+1 = x i +1，y i+1 = y i当F(x i,y j)>0时，取x i+1 = x i，y i+1 = y i–1F(x i,y j)<0说明P i在圆内，要向右走一步得P i+1，即向圆外方向走去；F(x i,y j)>0, 说明P i在圆外，要向下走一步得P i+1，即向圆内方向走去。

向圆内或圆外走是取决于F(x,y)的正负，因此称为正负法。

设F(x i,y j)的值已经算出，在计算F(x i+1,y j+1)时有下列两种情况：当F(x i,y j)<=0时，F(x i+1,y j+1)= F(x i+1，y j)=(x i+1-a)2+(y i-b)2–R2=(x i-a)2+(y i-b)2–R2 +2(x i -a)+1= F(x i，y j) +2(x i -a)+1当F(x i,y j)>0时，F(x i+1,y j+1)= F(x i，y j-1）=(x i-a)2+(y i-1-b)2–R2=(x i-a)2+(y i-b)2–R2 -2(y i -b)+1= F(x i，y j)- 2(y i -b)+1具体算法如下：PMcircle(a,b,r,color)int a,b,r,color;{int x,y,f;x=a,y=b+r;f=0;while (x<=a+r){putpixel(x,y,color);if(f<=0){f+=2*(x-a)+1;x++;}else {f=f-2*(y-b)+1;y--;}}}见程序circle1.c下面只讨论圆的中心在坐标的原点（0,0），半径为整数R的圆，圆的方程为x2 +y2= R2。