第3章二维线画图元的生成

第3章二维线画图元的生成内容摘要：

d0 = F(1, ) = R  算法中有浮点数，用 h=4d  H0＝ 5－ 4R  递推公式  程序： p51－ 52 10010020)(8128*451110iiiiiiiiiiiiiiixxHHyyyHHyxHxHHRH27 圆弧的中点算法  消除乘法运算 P  0020)(8128*4510iiiiiiii HHyxHxHHRH令 20)(8128iiiiiyxSExE递推公式 01608 20)(88812812)1(81111iiiiiiiiiiiHSEHSEyxSEExxE28 圆弧的中点算法 变量关系 初始值 RyxSExEiii82020)(81212800x y H E SE x=x+1 H=0 不变 H+E E+8 SE+8 H0 y1 H+SE E+8 SE+16 29 圆弧的多边形逼近法  两种方法  正内接多边形迫近法  等面积正多边形迫近法  特点  多边形边数足够多时接近圆  误差控制边数  显示多边形的边可用扫描转换直线段的中点算法来实现 30 圆弧的多边形逼近法 （ 1）正内接多边形迫近法  圆： x2 + y2 = R2  内接多边形顶点集： 令 pi 的幅角为 ，边的圆心角为 则有 10)},({ niiii yxpi 是常数， ， 只在开始时计算一次所以，一个顶点只需 4次乘法，共 4n次乘法，外加直线段的中点算法的计算量 )s i n()c os (s i nc os11iiiiiiiiRyRxRyRx iiiiiiyxRRyxc oss i ns i nc os)s i n()c os (11 sin cos31 圆弧的多边形逼近法 问题：多少条边合适。  给定最大逼近误差（最大 距离） d ，如何确定多边形的边数 n或 a。 R – Rcos(a/2) = d cos(a/2) = (R – d)/R a = 2 arc cos (R – d)/R amax = 2 arc cos (R – d)/R n = 360 /a 即 n = 2π/ a 32 圆弧的多边形逼近法  例 d = 20 d = 10 d = 5 d = 2 教材更正 p59： alfa＝ 2*acos… p60： 第一行添加 alfa =。 p60 ： cos改成 cosa sin改成 sina 33 圆弧的多边形逼近法 （ 2）等面积正多边形迫近法  面积  正多边形的面积等于圆的面积  内接正多边形的面积小于圆的面积  步骤  求多边形边长，从而求所有顶点坐标值  由逼近误差值，确定边所对应的圆心角 α 34 圆弧的多边形逼近法  求多边形径长 |OP0|= |OPi| ，从而求所有顶点坐标值 （假定圆心角为 ） s i n21)2c o s)(2s i n2(21212O D C E2121iiiiiiiOPOPOPOBPPRPOP的面积面积＝扇形积圆的面积＝多边形的面ROPROP iis i ns i n22 所以}d 35 圆弧的多边形逼近法  由逼近误差值 d，确定边所对应的圆心角 α }d dRRdOPRdBC i2c oss i n2c os36 椭圆的中点算法 *  基本思想  与圆弧中点算法类似：确定一个像素后，接着用两个候选像素的中点计算一个判别式的值，由判别式的符号确定下一个像素点  椭圆弧对称性与划分  四部分  每部分组成  上部分  下部分 y x P点处切线斜率为 1 37 椭圆的中点算法 *  正负划分性  椭圆的方程：  隐函数方式：  P点的坐标  椭圆弧上的法向量  椭圆弧上的切向量  切线斜率为－ 1的点满足  坐标 12222 byax0)()()(),( 222  abaybxyxF)),(,),(( y yxFx yxF )2,2( 22 yaxb)2,2( 22 yaxb yaxbyaxbxbya 222222 22122 ),( 222222babbaa38 正负划分性 椭圆的中点算法 * b x a ab F(x,y)0 F(x,y)0 F(x,y)=0 39  先讨论椭圆弧的上部分  (xp, yp)下一个点所取两点连线的 中点坐标为 (xp +1, )  d1=F(xp +1, ) = b2(xp +1)2+a2()2－ a2b2  根据 d1的符号来决定下一像素是取正右方的那个，还是右上方的那个。  若 d1＜ 0,中点在椭圆内 ， 取正右方象素 ， 判别式更新为： d139。 =F(xp +2, )= d1 +b2(2 xp +3) d1的增量为 b2(2 xp +3)  当 d1≥0， 中点在椭圆外 ， 取右下方象素 ， 更新判别式： d139。 =F(xp +2, )= d1 +b2(2 xp +3)+a2(2yp+2) d1的增量为 b2(2 xp +3)+a2(2 yp +2) 椭圆的中点算法 * 40  d1的初始条件  椭圆弧起点为 (0， b)，第一个中点为 (1,)  初始判别式： d10=F(1,)=b*b+a*a(b+)  椭圆弧的下部分  下部分，下一象素可能是一正下方或右下方 (x发生变化 )  d2 = F(xp+, yp1) = b2(xp+)2+a2(yp1)2a2b2。