直线-圆-椭圆生成算法.ppt

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

1、第三章直线、圆、椭圆生成算法3.1直线段扫描转换3.2圆弧扫描转换3.3椭圆弧扫描转换3.1直线段的扫描转换算法DDA算法中点画线法Bresenham画线算法数值微分法（ＤＤＡ）假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)栅格交点表示象素点位置。。。。数值微分(DDA)法基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。数值微分(DDA)法计算yi+1=kxi+1+b=kxi+b

2、+kx=yi+kx当x=1;yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k≤1的情形。在这种情况下，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=

3、x0;xx1;x++)drawpixel(x,int(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

4、画线法当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在直线(Q点)下方，取右上方P2；当d>0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1

5、；能否采用增量算法呢？中点画线法若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)+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)

6、+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=2*a;d2=2*(a+b);x=x0;y=y0;drawpixel(x,y,color);while(x

7、intLine*/中点画线法例：用中点画线法P0(0,0)P1(5,2)a=y0-y1=-2b=x1-x0=5d0=2a+b=1d1=2a=-4d2=2(a+b)=6ixiyid1001210-33213431-15425Bresenham画线算法在直线生成的算法中Bresenham算法是最有效的算法之一。令k=Δy/Δx，就0≤k≤1的情况来说明Bresenham算法。由DDA算法可知：yi+1=yi+k(1)由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（