第3章_点阵图形的基本算法.ppt

如果xi＞xc，则(xi+1，yi+1)只能从两点(xi，yi-1)，(xi+1，yi-1)中选择一个，并且判别时的初始值应重新设置为 扫描转换算法的终止条件应该是y=0。 2. 椭圆中点算法的伪代码描述 基于上述规则，我们可以得到如下所示的椭圆扫描转换算法: (3.4.19) Procedure Ellipse(a，b) BEGIN x=0:y=b； a=a*a:b=b*b； p1=b-a*y+a/4； PLOT(x，y)； x=x+1; WHILE(a*y-a/2＞b*x) DO BEGIN IF p1＜0 THEN p1=p1+2*b*x+b； ELSE y=y-1； p1=p1+2*b*x+b-2*a*y； ENDIF x=x+1； PLOT(x，y)； END p1=b*(x+1/2)*(x+1/2)+a*(y-1)*(y-1)-a*b； WHILE(y＞0) DO BEGIN y=y-1； IF p1＜0 THEN x=x+1； p1=p1+2*b*x-2*a*y+a； ELSE p1=p1-2*y*a+a； ENDIF PLOT(x，y)； END END 3.5 多项式曲线的算法 3.5.1 多项式函数的计算法 多项式函数f(x)=anxn+…+a1x+ a0可直接利用四则运算计算，也可以利用下述分解计算，以避免反复的求幂运算： f(x)=［…(anx+an-1)x+…］x+a1］x+a0 (3.5.1) 3.5.2 三次多项式函数的差分计算法 1. 三阶差分计算 设给定的三次多项式为 y=f(x)=a3x3+a2x2+a1x+a0 x∈［xs, xe］ (3.5.2)  并令当前给出的曲线上第i-1个像素点的坐标值为(xi-1，yi-1)，下一个像素点的x坐标值为xi=xi-1+Δx，y坐标为 yi=a3(xi-1+Δx) 3+a2(xi-1+Δx) 2+a1(xi-1+Δx)+a0 (3.5.3) 注意到 yi-1=a3x3i-1+a2x2i-1+a1xi-1+a0 (3.5.4) 可求得一阶差值 Δyi=yi-yi-1=a3(3x2i-1Δx+3xi-1 (Δx)2+(Δx)3)+a2(2xi-1Δx+(Δx)2)+a1Δx  为xi-1的二阶多项式，比原方程降了一阶。由一阶差值Δyi可得 yi=Δyi+yi-1 (3.5.6) 把i-1代入式(3.5.5)可得 Δyi-1=a3(3x2i-2Δx+3xi-2(Δx)2+(Δx)3)+a2(2xi-2Δx+(Δx)2)+a1Δx (3.5.7) (3.5.5) 由此可得二阶差值 Δ2yi=ΔyiΔyi-1=6a3(xi-2(Δx)2+(Δx)3)+2a2（Δx）2 (3.5.8) 为xi-2的一阶多项式，比原方程降了二阶。由二阶差值Δ2yi可得 Δyi=Δ2yi+Δyi-1 (3.5.9) 把i-1代入式(3.5.8)可得 Δ2yi-1=6a3 (xi -3(Δx)2+(Δx)3) (3.5.10) 由此可得三阶差值 Δ3yi=Δ2yi-Δ2yi-1=6a3(Δx)3 (3.5.11) 相对于x坐标为常数值，于是有 Δ2yi=6a3(Δx)3+Δ2yi-1 (3.5.12)  2. 差分计算法步骤 总结上述三阶差分的计算可以看出，若要计算出下一个像素点(xi, yi)，需要知道前面的三个像素点(xi -1， yi-1)、(xi -2， yi-2)和(xi -3，yi-3)。因此，用差分法绘制多项式曲线的计算步骤是： 第一步为初始计算，先计算必需的初始值： x0=xs, y0=f(x0) x1=x0+Δx, y1=f(x1), Δy1=y1-y0 x2=x1+Δx， y2=f(x2)， Δy2=y2-y1, Δ2y2=Δy2-Δy1