第三章 生成直线和圆弧算法

《第三章 生成直线和圆弧算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章生成直线和圆弧的算法一、生成直线的常用算法1逐点比较法2数值微分（DDA）法3中点画线法4Bresenham画线算法二、生成圆弧、椭圆弧的常用算法中点算法内接正多边形迫近法等面积正多边形逼近法生成圆弧的正负法第一节直线图形直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。四个常用算法：逐点比较法数值微分法（DDA）中点画线法Bresenham算法。一逐点比较法算法：1、偏差计算1）一般公式A(xA,xA)M(xM,xM)βα偏差偏差的判断公式为2）递推公式A

2、(xA,xA)M1(x1,x1)M2(x2,x2)M3(x3,x3)3)任意象限中的偏差计算公式：（同学们课下自己推导）4）终点判断二、数值微分(DDA)法基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。数值微分(DDA)法计算yi+1=kxi+1+b=kxi+b+kx=yi+kx当x=1;yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k≤1的情

3、形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换数值微分(DDA)法增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。数值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)intx；floatdx,dy,y,k;dx,=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;xx1,x++)drawpixel(x,i

4、nt(y+0.5),color);y=y+k;数值微分(DDA)法例：画直线段P0(0,0)--P1(5,2)xint(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5数值微分(DDA)法缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。三、中点画线法原理：假定直线斜率0

5、点现需确定下一个点亮的象素。中点画线法当M在Q的下方->P2离直线更近更近->取P2。M在Q的上方->P1离直线更近更近->取P1M与Q重合，P1、P2任取一点。问题：如何判断M与Q点的关系？中点画线法假设直线方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知：∴欲判断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在直

6、线(Q点)下方，取右上方P2；当d>0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采用增量算法呢？中点画线法若d0->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;此时再下一个象素的判别式为d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+

7、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来摆脱小数，提高效率。中点画线法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=

8、2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x