2、△x
3、,
4、△y
5、)取时间步长为1/△t,若当前像素点坐标为(xi,yi),则下一个像素点的坐标可由以下两式
6、确定：xi+1=xi+dx=xi+Dx/Dtyi+1=yi+dy=yi+Dy/Dt2、中点直线生成算法:假定直线斜率0P2离直线更近更近->取P2。M在Q的上方->P1离直线更近更近->取P1M与Q重合，P1、P2任取一点。设直线方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0F(x,y)=0点在直线上面F(x,y)>0点在直线上方F(x,y
7、)<0点在直线下方欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。令d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d<0，M在直线下方，取右上方P2；当d>0，M在直线上方，取右方P1；当d=0，选P1或P2均可，约定取P1；若d0->M在直线上方->取P1;此时再下一个象素的判别式为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；增量为a若d<0->M在直线下方->取P2;此时再下一个
8、象素的判别式为d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b；增量为a＋b画线从(x0,y0)开始，d的初值d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b由于只用d的符号作判断，为了只包含整数运算,可以用2d代替d来摆脱小数，提高效率。同时d每次的增量也已相应乘2操作。3、Bresenham画线算法基本思想：根据直线的斜率确定选择X或者Y方向作为计长方向,在此方向上每次递增一
9、个单位步长(或者一个像素单位),另一个方向上是否同时产生一个单位增量由一个计算量很小的判别式来判断。算法原理：以斜率在0~1之间的直线段为例，在第一象限内piDC这种情况下,选择X方向为计长方向，即增量dx=1。，设Pi(xi,yi)是已选定的离直线最近的像素,现在要决定Pi+1是D还是C显然,若d<0.5,则C靠近直线,应选C；若d>=0.5,则应选D。(m=△y/△x)令e=d-0.5(初值为m-0.5),即有：e<0时,选Pi+1(xi+1,yi),更新e=e+m;e>=0时,选Pi+1(xi+1,yi+1),更新e=e+m-1
10、;为计算简便(整数计算),将判别式e替换为e=2e△x;初值e=-△x结论：得到递推公式e<0时,选Pi+1(xi+1,yi);e=e+2△ye>=0时,选Pi+1(xi+1,yi+1);e=e+2△y-2△x其中,△x=xe-xs;△y=ye-ys实验二：圆生成算法的实现1.圆的中点生成算法：利用圆的对称性，只须讨论1/8圆。第二个8分圆P（Xp,Yp）为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。构造函数：F（X，Y）=X2+Y2-R2；则F（X，Y）=0（X，Y）在圆上；F（X，
11、Y）<0（X，Y）在圆内；F（X，Y）>0（X，Y）在圆外。设M为P1、P2间的中点，M=(Xp+1,Yp-0.5)F（M）<0->M在圆内->取P1F（M）>=0->M在圆外->取P2令判别式d=F(M)=F(Yp+1,Yp-0.5)=(Yp+1)2+(Yp-0.5)2-R2若d<0,取P1d1=F(Xp+2,Yp-0.5)=(Xp+2)2+(Yp-0.5)2-R2=d+2Xp+3d的增量为2Xp+3d>=0,取P2d2=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+（2xp+3）+（-2yp+2）d的
12、增量为2(xp-yp)+5d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25–R将d=0与d>0看成一种情况，每次d的增量为整型值，因此此时0.25对d的符号没有影响，可将d的初始值定为1-R。2
