第3章 基本图形的生成44278.ppt

3.3 圆的生成 3.3.1 八分法画圆算法 思路： （考虑到圆的对称性） 画出A点则剩下的7个点都能画出，画出B点则剩下的7个点都能画出， 因此，只讨论8分圆的画法即可 A(y,x) (-y,x) (-x,y) (-x,-y) (-y,-x) (y,-x) (x,-y) B 二 算法原理： 利用其函数方程，直接离散计算 圆的函数方程为： 缺点：计算量过大 三 圆的极坐标方程为： 可先通过平移变换，把计算所得的像素(x1,y1)坐标加上 一个位移量(delta_x和delta_y)即得所求像素坐标(x2,y2)。 即： x2=x1+delta_x y2=y1+delta_y 四 中点不在原点的圆： 3.3.2 中点画圆算法 （关键：找到d的增量） 一 基本思路： 利用中点M来选择下一个要显示的像素。 二 分析： M的坐标是（x+1,y-0.5） F(M)0 点M在圆的外边,圆离P2点近,取P2 F(M)=0 点M在圆的上边 , 取P2 F(M)0 点M在圆的里边, 圆离P1点近,取P1 问题：下一次取P3？P4？P5？ ? M1 P1 P2 M2 M3 P3 P4 P5 1 构造判别式： 若d0 点M在圆的里边，圆离P1点近,则应取P1 下一个中点M2的判别式为： d=F(xp+2, yp-0.5) =(xp+2)2+(yp-0.5)2-R2 =d+2xp+3 即求出d的增量为： 2xp+3 若d≥0 点M在圆的外边,圆离P2点近,则应取P2 下一个中点M3的判别式为： d=F(xp+2, yp-1.5) =(xp+2)2+(yp-1.5)2-R2 =d+2(xp-yp )+5 即求出d的增量为：2(xp-yp )+5 总结求得的d的增量： 2xp+3 d0 2(xp-yp )+5 d≥0 2 求d的增量： （目的：判断下一个该显示的像素） 解决方法： M1 P1 P2 M2 M3 P3 P4 P5 p 3 求d的初始值d0： 起始点（即第一个像素)为（0,R）, 判别式d的初始值为： d0=F(1,R-0.5) =1+(R-0.5)2-R2 =1.25-R 4 推导出的结果: d0＝1.25-R d+2xp+3 d0 d+2(xp-yp )+5 d≥0 M1 P1 P2 M2 M3 P3 P4 P5 d= 5 可以利用推导出的结果，编写程序。 三 算法步骤： 1.输入圆的半径R。 2.计算初始值d=1.25-R、x=0、y=R。 3.绘制点(x,y)及其在八分圆中的另外七个对称点。 4.判断d的符号。 若d≤0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)； 否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。 5.当xy时，重复步骤3和4。否则结束。 改进：用d-0.25代替d 算法步骤： 1.输入圆的半径R。 2.计算初始值d=1-R、x=0、y=R。 3.绘制点(x,y)及其在八分圆中的另外七个对称点。 4.判断d的符号。 若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)； 否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。 5.当xy时，重复步骤3和4。否则结束。 四 源程序： void MidpointCircle(r,color) int r, color ; { int x,y,d; x = 0; y = r; d = 1-r; wholecircle(x,y,color); while( x y) { if (d 0) { d += 2*x+3; x++; } else { d += 2*(x-y)+5; x++ ; y--; } wholecircle(x,y,color); } } void WholeCircle(xc,yc,x,y.color) int xc,yc,x,y,color ; { putpixel(xc+x,yc+y,color); putpixel(xc-x,yc+y,color); putpixel(