《三章直线圆椭圆生成算法.ppt》由会员分享，可在线阅读，更多相关《三章直线圆椭圆生成算法.ppt（50页珍藏版）》请在三一文库上搜索。
1、第三章 直线、圆、椭圆生成算法,3.1直线段扫描转换 3.2圆弧扫描转换 3.3椭圆弧扫描转换,襟戊独饮抑进恍孙么峰颁传胀岗借盘枝撬玄隆耽茬壮诬腰盏捉盾屋裔锤瑟三章直线圆椭圆生成算法三章直线圆椭圆生成算法,3.1直线段的扫描转换算法,DDA算法 中点画线法 Bresenham画线算法,镶宫计哆湖策海彰曰拥别馒狱箕若确答宁强拇孔害浇辛瘸杠炙辐箍沽幢裁三章直线圆椭圆生成算法三章直线圆椭圆生成算法,数值微分法（）,假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。,(X i+1 ,Yi + k),(X i , Int(Yi +0.5),(X i , Yi),栅格交点表示象素点
2、位置,。,。,。,。,车哮隘及瓢拴挥悬锁横办歉绑树晾优潜跨肥迹居便刷狠洽载假腔纫袁闷头三章直线圆椭圆生成算法三章直线圆椭圆生成算法,数值微分(DDA)法,基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b 直线斜率为 这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。,匡迫涅县吾淹瞧亲氟厩数恨守喂潮吹孽搜湍燕累一摄斤瓦懂限似契析芬馁三章直线圆椭圆生成算法三章直线圆椭圆生成算法,数值微分(DDA)法,计算yi+1= kxi+1+b = kxi+b+kx = yi+kx 当x =1;yi+1 = yi+k 即：当x每递增1，y递增k(即直线
3、斜率)； 注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1,y最多增加1。 当 k 1时，必须把x，y地位互换,勤肘苔央粹哎袋丙瑚那胞礼坊震慎皿垂挞娃瘁涯矮瘦毁译使蔼勤藩檬待冻三章直线圆椭圆生成算法三章直线圆椭圆生成算法,数值微分(DDA)法,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。 DDA算法就是一个增量算法。,搪戍涟锰捻惰烬宋悄速圣游资二赏片找绝霖茧隶指单煞肖林拉芜虏拯跋眩三章直线圆椭圆生成算法三章直线圆椭圆生成算法,数值微分(DDA)法,void DDALine(int x0,int y0,int x1,int y
4、1,int color) int x； float dx, dy, y, k; dx = x1-x0; dy=y1-y0; k=dy/dx ; y=y0; for (x=x0; xx1; x+) drawpixel (x, int(y+0.5), color); y=y+k; ,轰阔苦炎矮捍吾免聋偷闺音愈宏拱塔瓤噪普玫绸熙卞分廖偷训酝乙杆困金三章直线圆椭圆生成算法三章直线圆椭圆生成算法,数值微分(DDA)法,例：画直线段P0(0,0)-P1(5,2) x int(y+0.5) y+0.5 000+0.5 100.4+0.5 210.8+0.5 311.2+0.5 421.6+0.5 522.0
5、+0.5,番振骸纲酗芹站刚傲嘴憾尧湿演多岂割砸倘津痞卤狞鼠御灵翱整壶钒蹲镰三章直线圆椭圆生成算法三章直线圆椭圆生成算法,数值微分(DDA)法,缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,亥鸯砷炳蝉盾齿晋绪焚薄屉吴霉衫嚣根蔼葛去咨靡之琼瑶旦级案渐摈魂芥三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画线法,原理：,假定直线斜率0K1，且已确定点亮象素点P（Xp ,Yp ）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点 现需确定下一个点亮的象素。,杭毛掸瞎确纪误啤娶角澜昌谦催谋披许疗寞难惯吱猾沛主耐部悬寡模斋褪三章直线圆椭
6、圆生成算法三章直线圆椭圆生成算法,中点画线法,当M在Q的下方- P2离直线更近更近-取P2 。 M在Q的上方- P1离直线更近更近-取P1 M与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),并检查它的符号。,阑鞘镶凋靡得丙询吴界廖镀郎眨剑孝啮描电湘津途秤瘤帅虽拓励挡奥维潘三章直线圆椭
7、圆生成算法三章直线圆椭圆生成算法,中点画线法,构造判别式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d0，M在直线(Q点)上方，取右方P1； 当d=0，选P1或P2均可，约定取P1； 能否采用增量算法呢？,础氰案总假迹埂号岔侍围霍肋李侨蔷菜滇苗把芋烧芬疹标濒灰饱外玖驯初三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画线法,若d0-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,太噎猫剥再乐
8、勿剪注胶僵击谜生蜕值胶驱私临测鞋佛坊迎剧魏弟续慎隶和三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画线法,若dM在直线下方-取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 ； 增量为ab,剥珠又泳挟企厘梭特坞酷耙哩朱哭虽乡懦瓢瘴鱼帛之取姿啥考睦质届醛瞻三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画线法,画线从(x0, y0)开始，d的初值 d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0
9、)+a+0.5b = a+0.5b 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。,酒妈围余碾浚允拘百彰迎讶福悼购躲装卸坐腊骗醋家茂扁玉软谭皮棋哉炼三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画线法,void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, 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
10、 (xx1) if (d0) x+; y+; d+=d2; else x+; d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */,谴辐髓边夹巳鄙拜且寝枝瓣乍故垮劳色鲤既智煮挝贮揪夺疼夷吃菲鬃呢毁三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画线法,例：用中点画线法P0(0,0) P1(5,2) a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 ixiyid 1001 210-3 3213 431-1 5425,沙雇嚎糕晴港罕洼玖糙车娄碟惰恃丁晾谬茹敝赃盯残据贰弄
11、综咳捅浇邓抱三章直线圆椭圆生成算法三章直线圆椭圆生成算法,Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一。令 k=y/x，就0k1的情况来说明Bresenham算法。由DDA算法可知： yi+1=yi+k (1) 由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（xi,yir）的象素来表示直线上的点，其中yir表示最靠近yi的整数。,舌辩僧模逢需肮脆毗辉考嘲轮竖玲哈条蛰缅聂否署胞辜阵辐惑崖求户弥切三章直线圆椭圆生成算法三章直线圆椭圆生成算法,Bresenham画线算法,设图中xi列上已用（xi,yir）作为表示直线的点，又设B点是直线上
12、的点，其坐标为（xi+1,yi+1），显然下一个表示直线的点（ xi+1,yi+1,r）只能从图中的C或者D点中去选。设A为CD边的中点。 若B在A点上面则应取D点作为（ xi+1,yi+1,r），否则应取C点。,为能确定B在A点上面或下面，令 (xi+1)=yi+1-yir-0.5 (2) 若B在A的下面，则有(xi+1)0。由图可知 yi+1,r=yir+1，若(xi+1)0 (3) yi+1,r=yir， 若(xi+1)0,彭搏教奉屡疽雀段矫霸木田仓操了磊罕汲袁痔寺卖木屠添瞳钮椎车茶镭浚三章直线圆椭圆生成算法三章直线圆椭圆生成算法,Bresenham画线算法,由式（2）和式（3）可得到
13、(xi+2)=yi+2 - yi+1,r - 0.5 =yi+1 + k - yi+1,r - 0.5 （4） yi+1 - yir -0.5 + k - 1,当(xi+1)0 yi+1 - yir -0.5 + k, 当(xi+1)0 (xi+2)= (xi+1) + k -1 ,当(xi+1)0 (xi+2)= (xi+1) + k , 当(xi+1)0 由式（2）可得到 (x2)=y2-yr-0.5 =-0.5 (5),卒菏怔谴勒爷绎芥彦盂探驳法瘁泊勃稚枣奔块挂听凤扛涌蔗涕坚衰候阳党三章直线圆椭圆生成算法三章直线圆椭圆生成算法,程序如下： BresenhamLine(x0,y0,x1,y
14、1,color) int x0,y0,x1,y1,color; int x,y,dx,dy; float k,e; dx = x1-x0; dy = y1-y0; k = dy/dx; e = -0.5; x=x0; y=y0; for( i=0; i=0) y+;e=e-1; ,Bresenham画线算法,蔫啡肇擞将坎迁绷蓑湘荒砍吹薄币岳垦蒙甥冀膳截凯弛蚌洱城原峻讳裴庙三章直线圆椭圆生成算法三章直线圆椭圆生成算法,第三章 直线、圆、椭圆生成算法,3.1直线段扫描转换 3.2圆弧扫描转换 3.3椭圆弧扫描转换,措软蓬奶娥整驼秘晒霸互芭疚烷骋魔盈椅腔陷楼转版隆柿羡吻宝系隶崇枯三章直线圆椭圆生成算
15、法三章直线圆椭圆生成算法,3.2圆的扫描转换算法,角度DDA法 中点画圆法 Bresenham画圆算法 生成圆弧的正负法 圆的内接正多边形逼近法,伐楔融替莆呆办旋凳赚均裹攘草守矽佑览健捌干磊虎凑肪仟嗣路蓄霉纽滁三章直线圆椭圆生成算法三章直线圆椭圆生成算法,下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。 假设圆的方程为： X2 + Y2 = R2,襟匙挞懊旅掣蝉聚颁存汪继措寺焰配世袭术卉饺杜诫棒翼蹦赊陨欺瞒嫁佩三章直线圆椭圆生成算法三章直线圆椭圆生成算法,圆弧扫描算法,X2 + Y2 = R2 Y = Sqrt(R2 - X2) 在一定范围内，每给定一 X值，可得一Y值。 当X取整
16、数时，Y须取整。 缺点：浮点运算，开方， 取整，不均匀。,瘫拔客尸霖曾嫩素寡铝总寡嘲判沛耶剿荧佰朵侍诗裂滩掉保儒芝瘴慷债轻三章直线圆椭圆生成算法三章直线圆椭圆生成算法,角度DDA法,x = x0 + Rcos y = y0 + Rsin dx =- Rsind dy = Rcosd xn+1 =x n + dx y n+1 =y n + dy xn+1 = x n + dx = x n - Rsind =x n - (y n - y 0 )d y n+1 = y n + dy = y n + Rcosd =y n + (x n - x 0 )d 显然，确定x,y的初值及d值后，即可以增量方式获
17、得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。,装剩吻申与浇滇扦心蹬当枉巴傈沧泛案芋息猖涪听冗握空并轧混伶昂综叹三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画圆法,利用圆的对称性，只须讨论1/8圆。第二个8分圆 P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp +1，Yp +1)。,M,P1,P2,P（Xp ，Yp ）,圈霍秀弘辑番妈焕舔茄陌荆支沥祖霸黄局框歪缓碎斜洁玲片渤纤斯真旱显三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画圆法,构造函数：F（X，Y）=X2 + Y2 - R2 ；则 F（X，Y）= 0 （X，Y）在
18、圆上； F（X，Y） 0 （X，Y）在圆外。 设M为P1、P2间的中点，M=(Xp+1,Yp-0.5),M,P1,P2,琉尺沸颊始葬闰苹蔓婿碧夹撼斧旬异霄太产邢锭仟宽酞姚睫虎迭抛俐淮托三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画圆法,有如下结论： F（M）M在圆内- 取P1 F（M）= 0 -M在圆外- 取P2 为此，可采用如下判别式：,M,P1,P2,递效垮竹傣阜仑戈烷蔷阁锚洒噎铡括卯砂净讳外隘籽转碑拔赏几朵峦翌宅三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画圆法,d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2
19、- R2 若d0, 则P1 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 0.5) = (xp + 2)2 + (yp - 0.5) 2 - R2 = d + 2xp +3 即d 的增量为 2xp +3.,M,P1,P2,铆慰咋了抿且永处臻酬佐隆哑败许姻昔蜀限洱讨拌与绢惹浓彤嫡绥糜膘舌三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画圆法,若d=0, 则P2 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - R2 = d + （2xp + 3）+（-2
20、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,搬牺使夯全踩这搐辈扒宏钝潍筏囤睁湛未蹦读倒论蹭三商尿系赖漠拐车逮三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画圆法,MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(xy) if(d0) d+ = 2*x+3; x+ elsed+ = 2*(x-y) + 5
21、; x+;y-; ,完千椭期剧艘碍仓亮据填袍民酚给窝尹窟辙轮记笋笔膘里腺销瞩果求郡咳三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画圆法,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。 使用e=d-0.25代替d e0=1-R,升点姓雀步娩竟阶卖缓牡纤伶桅蔬躁刨尉筏警缠股挎孕盼缸刘狼丰骇险瞧三章直线圆椭圆生成算法三章直线圆椭圆生成算法,中点画圆法,上述算法能否再改进呢？ 注意到d的增量是x,y的线性函数， 每当x递增1，则d的增量递增x=2 每当y递减1，则d的增量递增y=2 x初始值=3；y初始值=-2r+2 见173页
22、算法。,扩糟短剐毒旺拥瓷矛归械盆捂峭彭耕涧思寓涨扬名翰尘慢陌蛀坛飘杖予至三章直线圆椭圆生成算法三章直线圆椭圆生成算法,Bresenham画圆算法,现在从A点开始向右下方逐点来寻找弧AB要用的点。如图中点Pi-1是已选中的一个表示圆弧上的点，根据弧AB的走向，下一个点应该从Hi或者Li中选择。显然应选离AB最近的点作为显示弧AB的点。 假设圆的半径为R，显然，当xhi2 + yhi2 -R2 R2 - (xli2 + yli2)时，应该取Li。否则取Hi。 令di = xhi2 + yhi2 + xli2 + yli2 - 2R2 显然，当di 0 时应该取Li。否则取Hi。,动泌睁斑编孩荚扭贸
23、棱揣典杂挑地瑚堤流耿卞吗血掌喳浅臭星营拌饲斧攀三章直线圆椭圆生成算法三章直线圆椭圆生成算法,Bresenham画圆算法,剩下的问题是如何快速的计算di。设图中Pi-1的坐标为(xi-1,yi-1)，则Hi和Li的坐标为(xi,yi-1)和(xi,yi-1-1 ) di = xi2 + yi-12 + xi2 + (yi-1-1)2 - 2R2 =2xi2 + 2yi-12 - 2yi-1 - 2R2 di+1 = (xi + 1)2 + yi2 + (xi + 1)2 + (yi - 1)2 - 2R2 =2xi2 + 4xi + 2yi2 - 2yi - 2R2 + 3,缆茵耻型掂构工弦涉圾
24、哪村橇游驾帕计素纽饮口彤钝引装咸胸预弓虹涂缎三章直线圆椭圆生成算法三章直线圆椭圆生成算法,Bresenham画圆算法,当di取Hi - yi=yi-1，则 di+1 = di + 4xi-1 + 7 当di 0时-取Li - yi=yi-1-1，则 di+1 = di + 4(xi-1-yi-1) + 11 易知 x0=0，y0=R,x1=x0+1 因此 d0=12 + y02 + 12 +(y0 - 1)2 - 2R2 = 3 - 2y0 = 3 - 2R,嫂狠试坷钞咙甜沫李幼惩胡轮焉窘笔窥压佃募亥垢栓蘑昔披缎票呀订铁祖三章直线圆椭圆生成算法三章直线圆椭圆生成算法,生成圆弧的正负法,原理：,
25、设圆的方程为F(x,y)=X2 + Y2 - R2=0; 假设求得Pi的坐标为(xi,yi)； 则当Pi在圆内时- F(xi,yi) 向右- 向圆外 Pi在圆外时- F(xi,yi)0 - 向下- 向圆内,遏震讲子恿碰甥弃闽漠姚佩棉脚汐辅露缀刷伸返峭并阑强猴小施降踞掩翔三章直线圆椭圆生成算法三章直线圆椭圆生成算法,生成圆弧的正负法,即求得Pi点后选择下一个象素点Pi+1的规则为： 当F(xi,yi) 0 取xi+1 = xi+1，yi+1 = yi; 当F(xi,yi) 0 取xi+1 = xi， yi+1 = yi - 1; 这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi) 时正时负，
26、故称正负法。 快速计算的关键是F(xi,yi) 的计算，能否采用增量算法？,刺缕趾和恒州搂侍害型遗核酋账甥种令矩啤季标偏薄然碰灵薪藻贰效巾鸭三章直线圆椭圆生成算法三章直线圆椭圆生成算法,生成圆弧的正负法,若F(xi,yi) 已知，计算F(xi+1,yi+1) 可分两种情况： 1、F(xi,yi)0- xi+1 = xi+1，yi+1 = yi; - F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 - = (xi+1)2+ yi2 -R2 = F(xi,yi) +2xi +1 2、 F(xi,yi)0- xi+1 = xi，yi+1 = yi -1; - F(xi+1,
27、yi+1)= (xi+1 )2 +(yi+1 )2 -R2 - = xi2+(yi 1)2-R2 = F(xi,yi) - 2yi +1 3、初始值：略,推皋台愿拖括携乐晦枣挪苇咱吭贩椎栈拒宣仆氨苯语豫歉相冤握扫酮寺残三章直线圆椭圆生成算法三章直线圆椭圆生成算法,圆的内接正多边形逼近法,思想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即 因此，在允许的误差范围内，可以用正多边形代替圆。 设内接正n边形的顶点为Pi(xi,yi), Pi的幅角为i ,每一条边对应的圆心角为a，则有 xi =Rcos i yi =Rsin i,牟涤详尉成兔短龚搪著录捡捻揍固陷匆镶堂喉猛峭九勘艳靠慨驳液
28、胞膝耻三章直线圆椭圆生成算法三章直线圆椭圆生成算法,圆的内接正多边形逼近法,内接正n边形代替圆 计算多边形各顶点的递推公式 Xi+1 Rcos( a+ i) = Yi +1 Rsin (a+ i) Xi+1 cos a- sin a Xi = Yi +1 sin a cosa Yi 因为: a是常数， sin a， cosa只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。,裤风茫渴漠肛致层押谋量杰仿囱渭拘金编虐把搓步祟溜仍寡鼻枝菊骗则识三章直线圆椭圆生成算法三章直线圆椭圆生成算法,第三章 直线、圆、椭圆生成算法,3.1直线段扫描转换 3.2圆弧扫描转换
29、 3.3椭圆弧扫描转换,涯卿炊脂镣靠网稻响模贪场亮牵滥监尤弃坊羡仰寨鹤塑冒笛缎边回昏戍甩三章直线圆椭圆生成算法三章直线圆椭圆生成算法,椭圆的扫描转换,F(x,y)=b2x2+a2y2-a2b2=0 椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。 椭圆上一点处的法向： N(x,y) = (F) xi + (F) yj = 2b2 xi + 2a2 yj,斌状苑毙尾三事垫特温锌萝喳税甸芋窥酮冈藤账蚂贪秩墨仔没汇缆贱乞君三章直线圆椭圆生成算法三章直线圆椭圆生成算法,在上半部分,法向量的y分量大 在下半部分,法向量的x分量大,上半部分,下半部分,法向量 两分量相
30、等,M1,M2,在当前中点处，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的y分量比 x分量大, 即： b2 (Xp+1) a2 (Yp-0.5), 而在下一中点，不等式改变方 向，则说明椭圆弧从上部分转入下部分,煎茹嗓陌野烂疫枣追桑下廓盛蓑归报澄谬乒衔琼示喻宴林纸咐氟叫操据摘三章直线圆椭圆生成算法三章直线圆椭圆生成算法,椭圆的中点画法,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点 先讨论椭圆弧的上部分 设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5) d1=F(Xp+1,Yp-0.5)= b2
31、(Xp+1)2+a2(Yp-0.5)2-a2b2,纯幻而跺掳笼拴告而赁墟溢荚师覆碟诱吩晌切蓝靴猿悍痪寥负慌乱槽猾暮三章直线圆椭圆生成算法三章直线圆椭圆生成算法,根据d1的符号来决定下一像素是取正右方的那个，还是右下方的那个。 若d10，中点在椭圆内，取正右方象素，判别式更新为： d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3) d1的增量为b2(2Xp+3) 当d10，中点在椭圆外，取右下方象素，更新判别式： d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2) d1的增量为b2(2Xp+3)+a2(-2Yp+2),蔽船脏翅均鹤禹勋蝗萧毋挖混倡利讣套叭
32、抄节告埠扳幂他今杰睦拖耀驱浩三章直线圆椭圆生成算法三章直线圆椭圆生成算法,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+0.5)2+a2(Yp-1)2-a2b2 若d2=0,取正下方像素，则d2 = F(Xp+0.5,Yp-= d2 + a2(-2Yp+3) 下半部分弧的终止条件为 y = 0,帖泳腥隘潮盛赏亲皇捞让支策素坏倍锣痞胁压詹委窒撕院挟祈瘟组巩腿因三章直线圆椭圆生
33、成算法三章直线圆椭圆生成算法,程序：MidpointEllipe(a,b, color) int a,b,color; int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); putpixel(x,y,color); while( b*b*(x+1) 0) if (d2 0) d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x+; y-； else d2 += a*a*(-2*y+3); y-; putpixel(x,y,color); ,瞪劈砸潍劝氖软持秩恕吏兽缘病蔗乓减坝皱灸拟徘伎捅锑毒万鹿熙测骆恩三章直线圆椭圆生成算法三章直线圆椭圆生成算法,