算法之橢圓的生成算法

1、橢圓和直線(xiàn)、圓一樣，是圖形學(xué)領(lǐng)域中的一種常見(jiàn)圖元，橢圓的生成算法（光柵轉(zhuǎn)換算法）也是圖形學(xué)軟件中最常見(jiàn)的生成算法之一。在平面解析幾何中，橢圓的方程可以描述為 (x x0)2 / a2+ (y y0)2 / b2 = 1，其中 (x0, y0)是圓心坐標(biāo)， a和 b 是橢圓的長(zhǎng)短軸，特別的，當(dāng) (x0, y0)就是坐標(biāo)中心點(diǎn)時(shí)，橢圓方程可以簡(jiǎn)化為 x2 / a2 + y2 / b2 = 1。在計(jì)算機(jī)圖形學(xué)中，橢圓圖形也存在在點(diǎn)陣輸出設(shè)備上顯示或輸出的問(wèn)題， 因此也需要一套光柵掃描轉(zhuǎn)換算法。 為了簡(jiǎn)化， 我們先考慮圓心在原點(diǎn)的橢圓的生成， 對(duì)于中心不是原點(diǎn)的橢圓， 可以通過(guò)坐標(biāo)的平移變換獲得相應(yīng)位

2、置的橢圓。在進(jìn)行掃描轉(zhuǎn)換之前，需要了解一下橢圓的對(duì)稱(chēng)性，如圖（1）所示：圖（ 1）橢圓的對(duì)稱(chēng)性中心在原點(diǎn)。焦點(diǎn)在坐標(biāo)軸上的標(biāo)準(zhǔn)橢圓具有 X 軸對(duì)稱(chēng)、 Y 軸對(duì)稱(chēng)和原點(diǎn)對(duì)稱(chēng)特性，已知橢圓上第一象限的 P 點(diǎn)坐標(biāo)是 (x, y) ，則橢圓在另外三個(gè)象限的對(duì)稱(chēng)點(diǎn)分別是 (x, -y)、(-x, y) 和 (-x, -y) 。因此，只要畫(huà)出第一象限的四分之一橢圓，就可以利用這三個(gè)對(duì)稱(chēng)性得到整個(gè)橢圓。在光柵設(shè)備上輸出橢圓有很多種方法， 可以根據(jù)直角平面坐標(biāo)方程直接求解點(diǎn)坐標(biāo)， yekeyii 利用極坐標(biāo)方程求解，但是因?yàn)樯婕暗礁↑c(diǎn)數(shù)取整，效果都不家用制氧機(jī)十大品牌好，一般都不使用直接求解的方式。 本文就

3、介紹幾種計(jì)算機(jī)圖形學(xué)中兩種比較常用的橢圓生成方法：中點(diǎn)畫(huà)橢圓算法和 Bresenham橢圓生成算法。1、 中點(diǎn)畫(huà)橢圓法中點(diǎn)在坐標(biāo)原點(diǎn)，焦點(diǎn)在坐標(biāo)軸上（軸對(duì)齊）的橢圓的平面集合方程是：x2 / a2 + y2 / b2 = 1，也可以轉(zhuǎn)化為如下非參數(shù)化方程形式：F(x, y) = b2x2 + a2y2 - a2b2 = 0（方程 1）無(wú)論是中點(diǎn)畫(huà)線(xiàn)算法、 中點(diǎn)畫(huà)圓算法還是本節(jié)要介紹的中點(diǎn)畫(huà)橢圓算法，對(duì)選擇x 方向像素增量還是 y 方向像素增量都是很敏感的。 舉個(gè)例子，如果某段圓弧上， x 方向上增量 +1 個(gè)像素時(shí)， y 方向上的增量如果 < 1，則比較適合用中點(diǎn)算法，如果 y 方向上的

4、增量 > 1，就會(huì)產(chǎn)生一些跳躍的點(diǎn)，最后生成的光柵位圖圓弧會(huì)有一些突變的點(diǎn)，看起來(lái)好像不在圓弧上。因此，對(duì)于中點(diǎn)畫(huà)圓弧算法，要區(qū)分出橢圓弧上哪段 x 增量變化顯著，哪段 y 增量變化顯著，然后區(qū)別對(duì)待。由于橢圓的對(duì)稱(chēng)性，我們只考慮第一象限的橢圓圓弧，如圖（2）所示：家用制氧機(jī)十大品牌圖（ 2）第一象限橢圓弧示意圖定義橢圓弧上某點(diǎn)的切線(xiàn)法向量N 如下：對(duì)方程 1 分別求 x 偏導(dǎo)和 y 偏導(dǎo)，最后得到橢圓弧上 (x,y) 點(diǎn)處的法向量是 （2b2x, 2a2 y）。 dy/dx = -1 的點(diǎn)是橢圓弧上的分界點(diǎn)。此點(diǎn)之上的部分（橙褐色部分）橢圓弧法向量的 y 分量比較大，即：2b22 ；此

5、點(diǎn)之下的部分（藍(lán)(x + 1) < 2a (y0.5)紫色部分）橢圓弧法向量的 x 分量比較大，即： 2b22。(x + 1) > 2a (y0.5)對(duì)于圖（ 2）中橙褐色標(biāo)識(shí)的上部區(qū)域， y 方向每變化 1 個(gè)單位， x 方向變化大于一個(gè)單位，因此中點(diǎn)算法需要沿著x 方向步進(jìn)畫(huà)點(diǎn)， x 每次增量加 1，求y 的值。同理，對(duì)于圖（ 2）中藍(lán)紫色標(biāo)識(shí)的下部區(qū)域，中點(diǎn)算法沿著y 方向反家用制氧機(jī)十大品牌向步進(jìn)， y 每次減 1，求 x 的值。先來(lái)討論上部區(qū)域橢圓弧的生成，如圖（3）所示：圖（ 3）中點(diǎn)畫(huà)橢圓算法對(duì)上部區(qū)域處理示意圖假設(shè)當(dāng)前位置是 P(xii，則下一個(gè)可能的點(diǎn)就是P點(diǎn)右邊

6、的ii點(diǎn)或右, y )P1(x +1, y )下方的 P2(x+1, y-1)點(diǎn)，取舍的方法取決于判別式d ，d 的定義如下：iiiidi = F(xi +1, yi -0.5) = b2(x i+1)2 + a2(yi-0.5)2 a2b2若 di < 0，表示像素點(diǎn) P1 和 P2 的中點(diǎn)在橢圓內(nèi)， 這時(shí)可取 P1 為下一個(gè)像素點(diǎn)。此時(shí) xi+1 = xi + 1， yi+1 = yi，代入判別式 di 得到 di+1：di+1 = F(xi+1 +1, yi+1-0.5) = b2(xi +2)2 + a2(yi -0.5)2 a2b2 = di + b2(2xi + 3)家用制氧

7、機(jī)十大品牌計(jì)算出 di 的增量是 b2(2xi + 3)。同理，若 di >= 0，表示像素點(diǎn) P1 和 P2 的中點(diǎn)在橢圓外，這時(shí)應(yīng)當(dāng)取 P2 為下一個(gè)像素點(diǎn)。此時(shí) xi+1 = xi + 1，yi+1 = yi - 1，代入判別式 di 得到 di+1：di+1 = F(xi+1 +1, yi+1-0.5) = b2(xi +2)2 + a2(yi -1.5)2 a2b2 = d1 + b2(2xi+3) + a2(-2yi +2)計(jì)算出 di 的增量是 b2(2xi +3)+a2(-2yi +2)。計(jì)算 di 的增量的目的是減少計(jì)算量，提高算法效率，每次判斷一個(gè)點(diǎn)時(shí)，不必完整的計(jì)算

8、判別式 di ，只需在上一次計(jì)算出的判別式上增加一個(gè)增量即可。接下來(lái)繼續(xù)討論下部區(qū)域橢圓弧的生成，如圖（4）所示：圖（ 4）中點(diǎn)畫(huà)橢圓算法對(duì)下部區(qū)域處理示意圖假設(shè)當(dāng)前位置是 P(xi , yi )，則下一個(gè)可能的點(diǎn)就是 P 點(diǎn)左下方的 P1(xi -1, yi-1)點(diǎn)或下方的 P2(xi , yi -1)點(diǎn)，取舍的方法同樣取決于判別式 di ，di 的定義如下：di = F(xi +0.5, yi -1) = b2(x i+0.5)2 + a2(yi -1)2 a2b2家用制氧機(jī)十大品牌若 di < 0，表示像素點(diǎn) P1 和 P2 的中點(diǎn)在橢圓內(nèi)， 這時(shí)可取 P2 為下一個(gè)像素點(diǎn)。此時(shí)

9、xi+1 = xi + 1， yi+1 = yi - 1，代入判別式 di 得到 di+1：di+1 = F(xi+1 +0.5, yi+1 -1) = b2(xi +1.5)2 + a2(yi -2)2 a2b2 = di + b2(2xi +2)+a2(-2yi +3)計(jì)算出 di 的增量是2i2i+3)。同理，若i，表示像素點(diǎn)P1和P2b (2x+2)+a (-2yd >= 0的中點(diǎn)在橢圓外，這時(shí)應(yīng)當(dāng)取P1 為下一個(gè)像素點(diǎn)。此時(shí)xi+1i ，i+1i- 1，= x y= y代入判別式 di 得到 di+1：di+1 = F(xi+1 +0.5, yi+1 -1) = b2(xi +

10、0.5)2 + a2(yi -2)2 a2b2 = d1 + a2(-2yi +3)計(jì)算出 di 的增量是 a2(-2yi +3)。中點(diǎn)畫(huà)橢圓算法從 (0, b)點(diǎn)開(kāi)始，第一個(gè)中點(diǎn)是 (1, b 0.5)，判別式 d 的初始值是：d0 = F(1, b0.5) = b2 + a2 (-b+0.25)上部區(qū)域生成算法的循環(huán)終止條件是： 2b22 ，下部區(qū)域的循(x + 1) >= 2a (y0.5)環(huán)終止條件是 y = 0，至此，中點(diǎn)畫(huà)橢圓算法就可以完整給出了：20 voidMP_Ellipse( intxc,intyc,inta ,intb )21 22 double sqa = a *

11、 a ;23 double sqb = b * b ;2425doubled= sqb+ sqa*(- b + 0.25 );家用制氧機(jī)十大品牌26 int x = 0;27 int y = b ;28EllipsePlot( xc , yc , x , y );29while( sqb*( x+1 )< sqa*( y-0.5 )3031if( d<0)3233d+= sqb*( 2* x+ 3);3435else3637d+=( sqb*( 2 * x+3)+ sqa*(-2* y +2);38y-;3940x+;41EllipsePlot( xc ,yc,x ,y );424

12、3d=( b* ( x+ 0.5 )*2+( a*( y-1)*2- ( a* b ) * 2;44 while ( y > 0)45 46if( d < 0)4748d+= sqb*( 2* x+ 2) + sqa * (- 2 * y + 3);49x+;5051else5253d+= sqa*(- 2* y+ 3);5455y-;56EllipsePlot( xc ,yc, x ,y );57 58 EllipsePlot() 函數(shù)利用橢圓的三個(gè)對(duì)稱(chēng)性，一次完成四個(gè)對(duì)稱(chēng)點(diǎn)的繪制，因?yàn)楹?jiǎn)單，此處就不再列出代碼。家用制氧機(jī)十大品牌2、Bresenham 算法中點(diǎn)畫(huà)橢圓法中，計(jì)算判

13、別式 d 使用了浮點(diǎn)運(yùn)算，影響了橢圓的生成效率。如果能將判別式規(guī)約到整數(shù)運(yùn)算， 則可以簡(jiǎn)化計(jì)算， 提高效率。 于是人們針對(duì)中點(diǎn)畫(huà)橢圓法進(jìn)行了多種改進(jìn)，提出了很多種中點(diǎn)生成橢圓的整數(shù)型算法，Bresenham橢圓生成算法就是其中之一。在生成橢圓上部區(qū)域時(shí)，以x 軸為步進(jìn)方向，如圖（ 5-a）所示：圖（ 5）Bresenham橢圓生成算法判別式x 每步進(jìn)一個(gè)單位， 就需要在判斷 y 保持不變還是也步進(jìn)減 1，bresenham算法定義判別式為：D = d1 d2家用制氧機(jī)十大品牌如果 D < 0，則取 P1 為下一個(gè)點(diǎn)，否則，取 P2 為下一個(gè)點(diǎn)。采用判別式 D，避免了中點(diǎn)算法因 y-0.5

14、 而引入的浮點(diǎn)運(yùn)算，使得判別式規(guī)約為全整數(shù)運(yùn)算，算法效率得到了很大的提升。根據(jù)橢圓方程，可以計(jì)算出d1 和 d2 分別是：d1 = a2(yi 2 y2)d2 = a2(y2 yi+1 2)以 (0, b)作為橢圓上部區(qū)域的起點(diǎn)，將其代入判別式D 可以得到如下遞推關(guān)系：Di+1 = Di + 2b2(2xi + 3)(Di < 0)Di+1 = Di + 2b2(2xi + 3) 4a2(yi - 1)(Di >= 0)D0 = 2b2 2a2b + a2在生成橢圓下部區(qū)域時(shí)，以 y 軸為步進(jìn)方向，如圖（ 5-b）所示，y 每步進(jìn)減一個(gè)單位，就需要在判斷 x 保持不變還是步進(jìn)加一個(gè)

15、單位，對(duì)于下部區(qū)域，計(jì)算出 d1 和 d2 分別是：d1 = b2(xi+12 x2)d2 = b2(x2 xi 2)以 (xp p 作為橢圓下部區(qū)域的起點(diǎn)，將其代入判別式D可以得到如下遞推關(guān)系：, y )家用制氧機(jī)十大品牌Di+1 = Di 4a2(yi - 1) + 2a2(Di < 0)Di+1 = Di + 2b2(xi + 1) 4a2(y - 1) + 2a2 + b2(Di >= 0)D0 = b2(xp + 1)2 +b2xp2 - 2a2b2 + 2a2(yp - 1)2根據(jù)以上分析， Bresenham橢圓生成算法的實(shí)現(xiàn)就比較簡(jiǎn)單了：61voidBresenha

16、m_Ellipse( intxc,intyc,inta ,intb )62 63 int sqa = a * a ;64 int sqb = b * b ;6566 int x = 0;67inty= b ;68intd=2 * sqb-2* b* sqa + sqa ;69EllipsePlot( xc ,yc, x ,y );70intP_x= ROUND_INT( double ) sqa / sqrt ( double )( sqa +sqb ) );71 while ( x <= P_x )72 73if( d< 0)7475d+=2* sqb*( 2* x+3);7677else7879d+=2* sqb*( 2* x+3) - 4 * sqa * ( y - 1);80y-;8182x+;83EllipsePlot( xc ,yc ,x ,y );84 85家用制氧機(jī)十大品牌86d= sqb*( x * x+ x )+ sqa*( y * y- y )- sqa* sqb ;87 while (