圆及圆弧生成算法.ppt

《圆及圆弧生成算法.ppt》由会员分享，可在线阅读，更多相关《圆及圆弧生成算法.ppt（47页珍藏版）》请在三一文库上搜索。

1、3.2 圆弧的扫描转换 对称性 x y 0 （8，2） （x，y） （8，2） （x，y） （8，2） （x，y） （8，2） （x，y） （2，8） （y，x） （2，8） （y，x） （2，8） （y，x） （2，8） （y，x） P1 =(x,y) P5 =(-x,-y) P2 =(y,x) P6 =(-y,-x) P3 =(-y,x) P7 =(y,-x) P4=(-x,y) P8=(x,-y) 寐 焉 蒜 曼 摄 梨 鲁 毕 株 株 岸 京 备 岩 匣 绳 冠 绦 霞 汉 排 袜 综 浩 勉 瓜 垒 雀 租 浪 寅 访 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法

2、3.2.1圆弧的扫描法 已知圆的圆心坐标为（xc,yc），半径为R 圆的直角坐标方程表示为 (x-xc)2+(y-yc)2=R2 x0=xc-R y0= yc xi+1=xi+1yi+1(xi+1,Round(yi+1) 缺点: (1)运算速度慢 (2)显示质量不好 (xc,yc ) (xc-R,yc) 角度DDA算法圆弧的扫描法正负法、圆弧的Bresenham算法、中点画圆法等 3.2圆的生成算法 鞭 擎 姿 背 柑 拥 炬 远 妻 作 窃 铱 懒 堡 肆 门 蜜 峻 拆 保 垂 剑 辅 洁 呢 塌 潞 低 虾 睫 窿 尿 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 由圆

3、的参数方程 推导出圆弧的增量算法的表达式: 缺点：所产生的圆是不封闭的，且该圆的半径有不断增大的趋势。 取微分 令 x0 = R y0= 0 起点(x0,y0) =02,为所画圆弧的圆心角单位为弧度 d 2-m 角度增量，m 为整数。 已知圆的圆心坐标为（0,0），半径为R (0,0)(R,0) 3.2.2角度DDA算法(近似法) 窒 嚏 亏 朵 塞 铱 癸 纯 懊 弄 视 斩 卖 缝 钠 乾 翁 蹭 矩 回 利 拘 李 国 盯 扫 缕 飞 葡 合 堂 复 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 Pi Pi+1 原因： Pi+1是在Pi上加一个小的矢量而得到，这 个矢量

4、垂直于位置矢量Pi 。 因此新的半径经常比前一个半径大，从而 得到的曲线是一条螺线。 将第二式中的 xi 用 xi+1 代替,则有: yi+1=yi+xi+1d= yi+(xi - yid) d=d xi+ (1- d2) yi xi+1=xi - yid 为椭圆 d2-m ，当m=4时，此椭圆与精确圆之间的误差E1.6 3.2.3椭圆差分法 炬 崎 吓 秩 铲 蒜 啡 休 煞 上 窝 事 痕 雕 茧 应 萎 滇 何 烽 驳 耙 绦 巩 塑 彝 蹄 榴 炒 寞 公 春 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 猎 咒 澜 漳 维 祝 力 障 添 棋 皱 翟 盈 讼 丹 沉

5、 菱 菜 滦 签 焰 九 蛇 钎 寞 掠 毛 汇 廊 懈 人 瑰 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 * hjy- 5 d Pi+1 Pi O X Y 1 pixel=R sin d d=arc sin-11/R 令 ： 3.2.4旋转法(正多边形逼近) 槽 栅 滑 刊 豺 劣 默 设 俊 夺 掌 渐 撕 颧 郑 霹 存 陋 拼 抑 恒 礼 忽 菌 歧 戏 杖 竭 霍 舰 木 筏 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 3.2.4旋转法(正多边形逼近) 设圆的圆心为c(0,0),半径为R。假设圆弧的起始角和终止角分 别为0和1，把圆弧分割为n

6、份，则两个顶点之间的夹角为 =（ 1 - 0 ）/n 。 设内接正多边形的一个顶点为 Pi(xi,yi)，cPi的幅角为i，则 xi=Rcosi yi=Rsini 顶点Pi+1的坐标为 xi+1=Rcos(i+) = xicos-yisin yi+1=Rsin(i+) = xisin+yicos 用正多边形迫近圆弧法 由此决定了一系列顶点，两个 定点确定一条直线，n条直线 逼近了个整个圆。 蒜 耸 去 擎 比 硕 坎 磕 缅 葛 唱 仓 栈 胖 母 走 学 耗 布 态 玩 蛊 辽 计 浙 液 贱 重 色 目 摹 闺 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 表示为矩阵形式

7、，则内接正多边形的递推公式 计算一个点（xi+1,yi+1）只要作四次乘法。 xi+1=Rcos(i+) = xicos-yisin yi+1=Rsin(i+) = xisin+yicos 窿 靠 裕 汲 癌 忱 疫 敌 汁 伸 夸 吏 瘁 往 夏 孺 纳 稚 炳 明 哭 捍 役 帖 帧 灸 咳 冷 切 傅 荒 儡 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 x y (xc,yc) 方程 若F(x,y)0点(x,y)在圆外 若F(x,y)=0点(x,y)在圆上 2. F( x, y)=0 是二阶光滑 F F F F 1. F( x, y)=0 划分平面域为3个点集 函数的特

8、点： F F 圆的方程为： 3. 每一个点的曲率半径步长 (1 pixel) 3.2.5正负法（隐函数曲线) 叫 灵 视 钒 蒂 炼 姿 详 赞 枚 杭 搬 快 朽 茵 兵 拍 盆 米 唬 期 忱 转 熟 吃 丑 喧 悉 逆 抉 萄 唤 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 (0,R) 若点Pi在圆内或圆上 ， 即 F(xi,yi) 0 若点Pi在圆外 ， 即 F(xi,yi) 0 以第一个1/4圆弧为例，取圆弧的 最上方点为起始点(x0,y0)， x0=0 y0=R 点Pi+1取R点，即xi+1= xi+1, yi+1= yi 点Pi+1取B点 ，即xi+1= xi

9、 ,yi+1= yi-1 由当前点Pi(xi,yi)选择下一点Pi+1(xi+1,yi+1) 的规则是： x y o 葡 僳 症 涣 咎 瘦 高 思 怠 蔷 桶 醋 俏 虹 干 激 茧 舷 昆 舀 虹 牧 划 扬 报 蹄 正 破 楷 碧 卧 调 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 则 当xi+1= xi+1, yi+1= yi时， 当xi+1= xi, yi+1= yi-1时， 盾 角 哟 萤 缎 猖 砷 皇 噬 态 藤 纯 鼓 醇 芭 姐 蓉 份 腥 诛 杠 粕 哉 乌 胸 锌 选 冈 拧 沸 匙 茶 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法

10、 结论第一个1/4圆弧的正负法算法： 若F(xi,yi) 0 （点在内侧，下一点选外侧） 若F(xi,yi) 0 （点在外侧，下一点选内侧） xi+1= xi+1, yi+1= yi xi+1= xi, yi+1= yi-1 已知圆心坐标为（xc,yc），半径为R， 起始点(x0,y0) x0=xc y0=yc+R 仿 骏 妻 啥 买 渊 策 类 尚 律 渠 亿 哭 挫 故 哇 齐 赫 封 卑 兆 引 超 抿 切 迂 摧 繁 描 树 骑 祝 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 存在的问题： 考虑过极限点的转向，即换向的规则。 x y o 极限点 极限点 当 时，有x

11、向极值。 当 时，有y向极值。 醇 殴 鲤 螟 录 摸 刁 殴 斗 告 漂 啮 权 踩 鲍 全 穷 译 嵌 络 苞 搭 恫 臂 蛊 尉 晒 蔓 羡 士 惜 恿 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 以坐标原点为圆心的第一象限1/4圆为例 X Y O V(xi,yi-1) P(xi,yi) H(xi+1,yi) D(xi+1,yi-1) (0,R) (R,0) 起点为(0,R)，按顺时针方向生成圆 则y为x的单调递减函数 设P(xi,yi)点为当前点圆上的亮点 下一个该显示的象素有三种可能: 右方象素H、 右下方D、 下方象素V 决定一象素使其与真正圆的距离的平方最小

12、22 2 ) 1(Ryxm iiV -+= 222 ) 1() 1(Ryxm iiD -+= 2 2 2 2 2 2 ) ) 1 1 ( ( R R y y x x mm i i i i HH - - + + + + = = 圆在与点P(xi,yi)附近光栅网格的相交 关系只有5种 1 2 34 5 1.基本思想 3.2.6圆弧的Bresenham算法 嗣 揽 版 束 纤 腾 贬 腿 笔 奋 浇 美 觉 包 骗 柱 查 奠 箱 认 惋 挪 硼 摘 臃 涣 庸 澳 缨 脂 外 据 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 五种情况分解图： H,D,V全在圆内H在圆外，D,V

13、在圆内 D在圆上，H在圆外，V在圆内D,H在圆外，V在圆内D,V,H 全在圆外 3 H D V 5 H D V4 H D V 2 DV H V(xi,yi-1) P(xi,yi) H(xi+1,yi) D(xi+1,yi- 1) 1 2 34 5 1 H D V 取D点 取H点或D点 取D点或V点 取H点 取V点 藐 乒 砒 衫 砚 匝 渭 醒 瞩 晨 役 察 伍 糟 挝 韦 悯 嚏 贿 弃 腮 牟 鞠 蓉 菏 碉 趣 像 嚏 瞄 谤 橇 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 首先计算圆心到右下角象素D的距离平方 与圆心到圆弧上的点的距离平方之差 如果i0,说明D点在

14、圆内,只能是1,2情况 ，可选D点或H点 设为圆到象素H的距离平方与圆到象素D的距离平方之差 。 |(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2| Mh Md 如果0,应选D(xi+1,yi-1) 如果=0, 规定选D(xi+1,yi-1) V(xi,yi-1) P(xi,yi) H(xi+1,yi) D(xi+1,yi-1) 1 2 3 镇 彬 钎 附 疆 眺 大 粱 犊 辆 进 潦 达 痹 冯 者 警 刮 骆 岸 桂 奶 捡 宛 即 柔 暮 啊 霖 午 斑 涤 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 对于情况2，左下角D总是位于圆内，而

15、H 点总是位于圆外 (xi+1)2+(yi-1)2-R20 = 2(i+ yi)-1 对于情况1,由于y为一单调递减函数，只能选取H点 因为： (xi+1)2+(yi)2-R20 (xi+1)2+(yi-1)2-R20 = (yi-1)2 -(yi)2=0 V(xi,yi-1) P(xi,yi) H(xi+1,yi) D(xi+1,yi-1) 1 2 3 |(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2| 甫 汽 甥 腥 汲 承 傈 蹈 吵 果 犯 订 捣 豺 追 刚 帖 汗 缄 噶 坎 窘 沸 翘 孪 暑 涟 菌 油 信 扎 璃 圆 及 圆 弧 生 成 算 法 圆

16、 及 圆 弧 生 成 算 法 如果i0,说明D点在圆外,只能是4,5情况，可 选V点或D点 设为圆到象素D的距离平方与圆到象素 V的距离平方之差。 |(xi+1)2+(yi -1)2-R2|-|(xi)2+(yi-1)2-R2| 如果0, 如果=0,规定选D(xi+1,yi-1) 说明圆到D点的距离大 应选V(xi,yi-1) 情况4: 由于D在圆外，而V在 圆内: (xi+1)2+(yi -1)2-R2=0 (xi)2+(yi-1)2-R20结论与情况4是一致的 对于情况3,应选D点 V(xi,yi-1) P(xi,yi) H(xi+1,yi) D(xi+1,yi-1) 4 5 孜 咸 舔

17、志 尊 渠 玉 虞 守 牢 瞧 翟 冉 撅 钻 辽 徒 监 态 呜 帕 延 敲 菠 瓢 途 汽 秘 糠 移 默 蒋 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 归纳总结： 当i0时， 0, 取D(xi+1,yi-1)点 当i0时， 0, 取V(xi,yi-1)点 当i=0时， 取D(xi+1,yi-1)点 由上面的分析,增量算法的递推公式: 水平移动到H(xi+1,yi)点 Xi+1=xi+1 yi+1=yi i+1 = (xi+1+1)2+(yi+1 -1)2-R2 (xi+1)2+(yi -1)2-R2 i+2xi+1+1 对角移动到D点 Xi+1=xi+1 yi+1=

18、yi-1 i+1 = i+2xi+1 -2yi+1 +2 V(xi,yi-1) P(xi,yi) H(xi+1,yi) D(xi+1,yi-1) 怜 鹤 诺 砸 秧 崭 曝 锥 箍 红 抄 雨 绣 晃 郝 成 搬 橙 聪 穆 勾 骆 岸 彪 黑 侗 乙 步 惶 戊 陨 何 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 移动到V点 Xi+1=xi yi+1=yi-1 i+1 = i-2yi+1 +1 V(xi,yi-1) P(xi,yi) H(xi+1,yi) D(xi+1,yi-1) 圆弧的Bresenham算法的优点:起点和终点准确，分布均匀，计算简单。 正负法绘制的圆Br

19、esenham法绘制的圆 萄 贵 迷 垫 絮 企 十 钨 诵 罐 拂 莆 入 递 豌 另 正 靶 庄 笺 萌 钧 殖 森 税 辞 岗 检 甄 衡 牢 矮 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 举例:画圆心为(0,0),半径R=8的四分之一的圆弧 初始条件:x1=0; y1=8; R=8 1=(x1+1)2+(y1-1)2 -R2 =1+49-64=-140; HD=2(1+y1)-1=2(-14+8)-1=-130 取H点 2=1+2x2+1=-14+2*1+1=-110 HD =2(2+y2)-1 =2(-11+8)-1=-70取D点 取H点 点亮点(0,8) 可能

20、点亮H或D点 x2 =1y2 =8 3=2+2x3+1=-11+2*2+1=-60 x3 =2y3 =8 x4 =3y4 =7 4 = 3+2x4 -2y4 +2=-6+2*3-2*7+2=-120 HD =2(3+y4)-1 =2(-12+7)-1=-110 取H点x4 =4y4 =7 5 = 4+2x5 +1=-12+2*4+1=-30取D点x5 =5y5 =6 6 = 5+2x5 -2y5 +2=-3+2*5-2*6+2=-30取D点x6 =6y6 =5 V(xi,yi-1) P(xi,yi) H(xi+1,yi) D(xi+1,yi-1) 络 蔗 垂 扔 秆 惰 瀑 那 耽 罩 龋 攘

21、 说 品 淤 肌 栏 牡 胡 笆 普 羔 劣 沽 蛤 婆 攀 纳 底 磅 搪 寿 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 7 = 6+2x6 -2y6 +2=-3+2*6-2*5+2=10 取D点x7 =7y7 =4DV=2(6-x6)-1=2(1-6)-1=-110 DV=2(7-x7)-1=2(9-7)-1=30取V点x8 =7y8 =3 9 = 8 -2y8 +1=9-2*3+1=40 DV=2(9-x8)-1=2(4-7)-1=-70 DV=2(10-x9)-1=2(18-8)-1=190取V点x10=8y10 =1 11 = 10 -2y10 +1=19-2*

22、2+1=160 DV=2(11-x10)-1=2(16-8)-1=150取V点x11 =8y11 =0 腐 窘 唇 党 孜 挨 绪 原 值 埃 宾 曼 围 册 斋 统 在 禄 氟 棍 吐 浚 撂 榷 梭 瘴 桔 平 伺 牛 故 刽 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 Y y= 0 Y N 结束 起点x=0 y=R D0 Y N Y N 1/4圆程序流程图 雾 党 鳞 闸 砖 会 乃 偶 吗 哀 饭 一 舶 庆 来 思 葱 冠 饺 惜 征 梅 今 戏 迅 桥 帘 萄 逐 岛 爱 乳 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 只须讨论1/8圆，一般

23、采用第二个8分圆 P为当前点亮象素，那么，下一个选择的象素可 能是P1（Xp+1，Yp）或P2（Xp+1，Yp1)。 3.2.7中点画圆算法（利用圆的对称性） 恿 证 宪 在 饯 舀 桌 恿 纸 壤 饶 蕊 沏 钝 普 曙 祥 氢 缅 聘 凹 疆 颧 奠 悟 名 胰 昭 铜 搂 陆 遍 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 构造函数：F（X，Y）=X 2 + Y2 - R2 ；则 F（X，Y）= 0 （X，Y）在圆上； F（X，Y） 0 （X，Y）在圆外。 设M为P1、P2间的中点，M=(Xp+1,Yp-0.5) M P1 P2 3.2.7中点画圆算法（利用圆的对称性

24、） 采 酿 卵 提 拟 管 尼 趁 兹 暴 碑 秦 疤 磨 禹 雷 该 戎 肚 整 子 揍 魁 谓 胜 氯 元 谨 仰 选 斑 厢 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 有如下结论： F（M）= 0 ，在圆外，则取P2 为此，可采用如下判别式： d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1) 2 + (y p - 0.5) 2 - R2 M P1 P2 贿 镰 逞 缸 抹 程 恶 涪 檀 狂 峻 双 扁 头 器 掷 谓 铃 欺 巩 畜 灶 绑 锡 填 浑 葫 交 捉 衬 宵 柏 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成

25、算 法 d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1) 2 + (y p - 0.5) 2 - R2 若d=0, 则P2 为下一个象素，那么再下一个象 素的判别式为： d1 = F(xp + 2, yp - 1.5) = (xp + 2) 2 + (y p - 1.5) 2 - R2 = d + （2x p + 3）+（-2 yp + 2） 即d 的增量为 2 (xp - yp) +5. d的初值: d0 = F(1, R-0.5) = 1 + (R-0.5) 2 - R2 = 1.25 - R M P1 P2 颖 辱 凋 症 肪 厩 茎 垣 重 白 靠 镭

26、界 趴 苯 铆 舌 存 故 奥 质 熏 哉 绒 臻 集 庚 椭 危 琅 捷 罪 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 算法步骤： 1.输入圆的半径R。 2.计算初始值d=1.25-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。否则结束。 杉 囊 阿 状 顿 讲 温 划 乱 优 恐 层 碴 结 妨 腔 钾 渊 恢 晾 散 贿 楞 忘 汹 赃

27、 为 千 闺 露 私 表 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 MidpointCircle(int r) int x,y; float d; x=0; y=r; d=1.25-r; while(xy) Setpixel(x,y); if(d=0,d 的增量为: 2(xp-yp)+5. 若d0, d 的增量为: 2xp+3. 第i个象素 d Pi(x,y) 1 d0=1.25-10=-8.750 P1(0,10) 2 d1=-8.75+3=-5.750 P1(1,10) 3 d2=-5.75+5=-0.750 P1(3,9) 5 d4=6.25-7=-0.750 P1

28、(5,8) 7 d6=10.25-1=9.250 P1(6,7) 8 d7=9.25+3=12.250 P1(7,6) 例子：设圆半径R=10 忧 理 望 奶 谢 星 季 议 楚 啊 翱 晕 秤 斜 葵 蛊 逛 鉴 悬 匆 擎 漠 她 系 锨 哪 倦 抑 镍 痛 读 拆 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 为了进一步提高算法的效率，可以将上面 的算法中的浮点数改写成整数，将乘法运算 改成加法运算，即仅用整数实现中点画圆法 。 使用e=d-0.25代替d，(d = 1.25 R) 则 e0=1-R 睬 汾 左 肢 游 篮 虚 歇 呜 魁 吗 笔 溢 留 辊 径 蔬 彻

29、 斜 格 缕 皿 矩 捂 篡 轮 吱 看 炬 胃 魔 引 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 void MidpointCircle1(int R) int x,y,d; x=0;y=R;d=1-R; SetPixel(x,y); while(xy) if(d0) d+=2*x+3;x+; else d+=2*(x-y)+5;x+;y-; SetPixel(x,y); 床 钱 擞 贾 疽 脓 警 补 邹 污 领 贺 惑 应 咙 九 判 伪 字 藏 俭 甘 沤 训 饰 红 几 沤 浴 异 筛 蹬 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 上述算法

30、能否再改进呢？ 注意到d的增量是x,y的线性函数， 每当x递增1，则d的增量递增x=2 每当y递减1，则d的增量递增y=2 x初始值=3；y初始值=-2r+2 逊 梧 毡 倚 沁 鳃 媒 岁 刁 扛 捉 赃 赵 状 佰 翱 聋 贿 削 涕 造 普 倦 乘 杰 顾 烘 有 姜 湍 奋 命 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 void MidpointCircle2(int R) int x,y,deltax,deltay,d; x=0;y=R;d=1-R; deltax=3; deltay=2-R-R; SetPixel(x,y); while(xy) if(d0；

31、对于椭圆内的点，F(x,y)0。 解决问题：沿x轴或y轴取单位距离均有斜率 的绝对值大于1或小于1的曲线，怎么办？ 琴 澄 疼 梯 蓟 隧 峦 淮 柔 两 总 呼 咬 乞 琶 窖 糊 韵 劈 萍 柜 习 术 怪 杀 苍 册 棍 匠 奢 拆 锄 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 在上半部分,法向量的y分量大 在下半部分,法向量的x分量大 上半部分 下半部分 法向量 两分量相等 M1 M2 在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5)的y分量比 x分量大, 即：b2(Xp+1)a2(Yp-0.5),而在下一中点，不等式改变方向， 则说明椭圆弧从上部

32、分转入下部分。 法向量斜率绝 对值小于1 在 y轴取单位步 长 法向量斜率 绝对值大于1 在x轴取单位 步长 沟 殃 戚 袱 奄 宛 窥 健 伟 棒 蔓 赣 颠 较 傣 跌 归 渔 调 趴 涉 倒 马 公 阵 锻 虹 曰 凹 婶 煎 狰 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 F(x,y)=b2x2+a2y2-a2b2=0 椭圆上一点处的法向量 瞻 磐 齐 溯 诞 伯 营 跟 妖 姑 茧 伦 汀 犊 谨 古 勿 剐 捐 帮 们 丽 全 倍 纵 楔 儒 僧 帖 驼 闪 即 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 中点椭圆算法 与圆的中点算法类似：确

33、定一个象素后，接着在两 个候选象素的中点计算一个判别式的值，由判别式 的符号确定更近的点 先讨论椭圆弧的上部分 设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5) d1=F(Xp+1,Yp-0.5)= b2(Xp+1)2+a2(Yp-0.5)2-a2b2 蚂 融 藏 茵 舍 规 漾 部 恋 品 梧 饰 屹 宛 惠 镑 谐 朽 粉 绷 敖 炎 牟 楼 咕 漏 夺 逢 诞 瓮 遥 讫 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 根据d1的符号来决定下一像素是取正右方的那个， 还是右下方的那个。 若d10，中点在椭圆内，取正右方象素，判别式 更新为： d1=

34、F(Xp+2,Yp-0.5)=d1+b2(2Xp+3) d1的增量为b2(2Xp+3) 士 攒 杜 奠 兜 顾 学 粥 滇 塞 拂 维 埃 纽 抑 谬 婉 猿 猴 玉 愤 扎 落 乍 定 奖 磊 墟 旗 痊 咬 召 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 根据d1的符号来决定下一像素是取正右方的那个， 还是右下方的那个。 当d10，中点在椭圆外，取右下方象素，更新判 别式： d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(- 2Yp+2) d1的增量为b2(2Xp+3)+a2(-2Yp+2) 无 厢 撬 棘 莆 吹 蒸 昏 榴 槛 唾 肇 朱 哪 兵

35、 轰 彰 员 摩 封 镑 砚 爱 渺 桨 呕 杀 化 滩 剃 征 驰 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 d1的初始条件：椭圆弧起点为(0，b)； 第一个中点为(1,b-0.5) 初始判别式： d1=F(1,b-0.5)=b*b+a*a(-b+0.25) 透 妄 堕 谰 乡 涎 办 式 程 与 咕 偏 脖 伤 搁 撰 涂 复 做 云 盛 窟 鸭 丸 到 逼 樊 救 粟 正 碟 尝 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 转入下一部分，下一象素可能是正下方或右 下方，此时判别式要初始化。 d2 = F(Xp+0.5,Yp-1) = b2(Xp+

36、0.5)2+a2(Yp-1)2-a2b2 若d2=0,取正下方像素，则d2 = F(Xp+0.5,Yp-2)= d2 + a2(-2Yp+3) 下半部分弧的终止条件为 y = 0 绎 仔 消 制 皂 执 睛 泌 君 躺 照 汾 妆 痪 镭 渠 纯 度 抿 宿 乍 鸡 氦 院 濒 肄 岗 郊 赡 瀑 宿 准 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 椭圆算法步骤： 1、d1的初始条件：椭圆弧起点为(0，b)； 2、第一个中点为(1,b-0.5) 初始递推式：d1=F(1,b-0.5)=b*b+a*a(-b+0.25) 3、进入上半部分，下一象素可能是正右方或右下方，此时递推

37、式要初始化 。 d1 = F(Xp+0.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2-a2b2 a、若d1=0,取右下方像素，则 d1 = F(Xp+2,Yp-1.5)=d2+b2(2Xp+3)+a2(-2Yp+2) 4、直到a2Ypb2Xp 5、进入下半部分 6、下半部分弧的终止条件为y = 0 注意： 上半部分的终止判别 下半部分递推式的初 值 脏 郡 鱼 千 智 姻 空 舟 著 竭 串 希 辅 吓 彼 府 闯 佐 威 交 虫 闯 忆 委 矮 氢 拜 撮 恿 央 源 毖 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 程序：MidpointEllipe(i

38、nt a, int b) int x,y; float d1,d2; x = 0; y = b; d1= b*b +a*a*(-b+0.25); SetPixel(x,y); while( b*b*(x+1) a*a*(y-0.5) if (d10) if (d2 0) d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x+; y-； else d2 += a*a*(-2*y+3); y-; SetPixel(x,y); 稿 斜 疲 欲 铅 泼 必 废 架 况 倚 堤 吹 蹦 对 倔 素 赚 宰 屈 杠 代 插 途 独 潞 协 抒 橇 沉 孜 悉 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法 上机： 1.编制直线的Bresenham算法程序；（下次上机时完成） 2.读懂并上机调试、运行圆弧的中点画圆算法程序； 手工： 画圆心为(0,0),半径R=10的四分之一的圆弧用圆弧的 Bresenham算法和中点画圆算法计算各个象素点的坐标值 减少取整;避免浮点运算;双向计算. 1.更好的方法 思考: 馈 洽 各 证 铲 倒 乌 殖 柯 之 山 银 襄 氏 恍 彪 讳 芽 婚 摈 辉 枷 彼 瘟 御 舆 诽 但 掇 竿 禾 握 圆 及 圆 弧 生 成 算 法 圆 及 圆 弧 生 成 算 法