摘 要： 在等分圓周角的前提下，以泰勒公式為基礎(chǔ)，構(gòu)造出圓和橢圓的生成算法，并對(duì)算法的誤差進(jìn)行了詳細(xì)分析，給出了算法的適用范圍。算法生成的點(diǎn)分布均勻，可應(yīng)用于對(duì)圖形輸出有較高要求的場(chǎng)合。預(yù)處理后，計(jì)算每個(gè)點(diǎn)對(duì)只需要11次加法運(yùn)算，避免了大量的三角函數(shù)運(yùn)算，運(yùn)算速度快、運(yùn)算精度高。該快速算法的構(gòu)造方法新穎，具有較強(qiáng)的理論和實(shí)用價(jià)值。

關(guān)鍵詞： 等分圓周； 圓； 橢圓； 泰勒公式； 算法

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）08-37-03

A quick algorithm generating circle and ellipse about equal division circumference

Zhang Bo

（College of Bussiness， Jiamusi University， Jiamusi， Heilongjiang 154000， China）

Abstract： Based on equal division circumference angle and Taylor formula， algorithm of circle and ellipse is introduced. The errors of algorithm are analyzed and application scope of the algorithm is given. The algorithm generates uniform distribution dots and can be applied in the cases where graph output is of high quality. After preprocessing， every graphic dots are calculated by 11 times addition， avoiding much trigonometric function calculating. The algorithm is fast and precise， which is of practical value. A new and original construction method is proposed. It has great theoretical and practical value.

Key words： equal division circumference； circle； ellipse； Taylor Formula； algorithm

0 引言

圓和橢圓的生成算法較多，比較有名的有Bresenham畫(huà)圓算法，圓和橢圓的中點(diǎn)生成法[1]。但以上算法生成的繪圖點(diǎn)分布不均勻，視覺(jué)效果不好。等分圓生成的點(diǎn)之間距離相等，顯示效果最佳。以等分圓周生成的橢圓效果也比普通方法有很顯著的改善。

根據(jù)參數(shù)方程x=acos（θ），y=bsin（θ），采用直接計(jì)算的方法可生成對(duì)應(yīng)的繪圖點(diǎn)。由于有三角函數(shù)運(yùn)算和乘法運(yùn)算，逐點(diǎn)計(jì)算運(yùn)算量較大。文獻(xiàn)[4]給出了通過(guò)構(gòu)造遞推公式減少計(jì)算量的算法，算法執(zhí)行的速度快，但該算法的精度還不夠高，當(dāng)圓的半徑或長(zhǎng)短軸長(zhǎng)較大時(shí)，坐標(biāo)點(diǎn)的誤差大于1，理論上圓的半徑a不應(yīng)超過(guò)3067，很顯然該精度已經(jīng)不能滿(mǎn)足目前的需求。

對(duì)于圓只需生成1/8圓周，其他部分由對(duì)稱(chēng)性獲得；而對(duì)于橢圓就需要生成1/4橢圓弧。如果直接把文獻(xiàn)[4]生成圓的方法應(yīng)用到生成橢圓，橢圓弧對(duì)應(yīng)的最大角度變?yōu)棣?2，遞推公式計(jì)算出的值誤差也加大（文中論述原因）。針對(duì)以上問(wèn)題，通過(guò)遞推公式的重新構(gòu)造，給出了一個(gè)精度更高的圓的生成算法，并提出采用八分之一圓周非對(duì)稱(chēng)方式生成橢圓，實(shí)現(xiàn)了生成橢圓和生成圓的精度一樣高。

1 圓的遞推公式的構(gòu)造

1.1 圓方程的泰勒展開(kāi)

假設(shè)圓心在原點(diǎn)，圓的方程為：

因其對(duì)稱(chēng)性，這里只考慮圖形的生成。假設(shè)把以上區(qū)間分成n份，每份的角度為： 。當(dāng)θ=kt時(shí)（k=0，1，…，n），分別計(jì)算出x和y的值。把上面參數(shù)方程用泰勒公式展開(kāi)，取前幾項(xiàng)得到：

1.2 構(gòu)造表達(dá)式

對(duì)于y構(gòu)造六個(gè)表達(dá)式：

以上各式有如下性質(zhì)：

只要把y對(duì)應(yīng)的泰勒展開(kāi)式構(gòu)造成以上六個(gè)表達(dá)式的形式，f5（k）的值就對(duì)應(yīng)θ=kt時(shí)的y值。重復(fù)以上過(guò)程，可計(jì)算出f5（k+2），f5（k+3），f5（k+4）等。也就可計(jì)算出θ=（k+1）t，θ=（k+2）t，θ=（k+3）t時(shí)對(duì)應(yīng)的y值。

1.3 系數(shù)的確定

設(shè)y=f5（k），令k=0，1，2，3，4，5得到如下各式：

解得：

采用同樣的方法可對(duì)x泰勒展開(kāi)式進(jìn)行構(gòu)造：

仿造上面方法還要構(gòu)造g5（k）、g4（k）…g0（k）等六個(gè)式子。設(shè)x=g6（k），令k=0，1，2，3，4，5，6，計(jì)算出a0、a1、a2、a3、a4、a5、a6的值（相應(yīng)求解省略，在下面算法中直接給出）。

2 圓的生成算法

在區(qū)間分成n份，每份的角度為。算法生成第一象限的圓弧。

數(shù)組元素a（6）、a（5）、a（4）、a（3）、a（2）、a（1）、a（0）分別存放表達(dá)式x 對(duì)應(yīng)的構(gòu)造表達(dá)式的值。初始時(shí)k=0，把k帶入構(gòu)造表達(dá)式并對(duì)數(shù)組元素進(jìn)行初始化，a（6）、a（5）、a（4）、a（3）、a（2）、a（1）、a（0）的值分別為a6、a5、a4、a3、a2、a1、a0。

數(shù)組元素b（5）、b（4）、b（3）、b（2）、b（1）、b（0）分別存放表達(dá)式f5（k）、f4（k）、f3（k）、f2（k）、f1（k）、f0（k）的值。初始時(shí)k=0，代入構(gòu)造表達(dá)式對(duì)數(shù)組元素進(jìn)行初始化，b（5）、b（4）、b（3）、b（2）、b（1）和b（0）的值分別為b5、b4、b3、b2、b1、b0。

⑴ 預(yù)處理

⑵ for {k=0； k<=n； k++}

{

drawpixel（a（6），b（5），color）；

/*在（a（6），b（5））畫(huà)點(diǎn)，color為點(diǎn)的顏色*/

drawpixel（b（5），a（6），color）； /*在對(duì)稱(chēng)點(diǎn)（b（5），a（6））處畫(huà)點(diǎn)*/

for （i=6； i>=1； i--）

{

a（i）=a（i）+a（i-1）；

}

for（j=5； j>=1； j--）

{

b（j）=b（j）+b（j-1）；

}

}

3 生成圓的算法分析

3.1 理論分析

當(dāng)kt=時(shí)，rcos（θ）泰勒展開(kāi)的余項(xiàng)為（ξ在0和之間，（8）為八階導(dǎo)數(shù)，因此誤差不超過(guò)。令<1，解得r<278454.54（π=3.141593）。

rsin（θ）泰勒展開(kāi)的余項(xiàng)為 （ξ在0和之間，（7）為七階導(dǎo)數(shù)），因此誤差不超過(guò)，令<1，解得r<27340.16（π=3.141593）。

由此可知，當(dāng)r≤27340時(shí)，生成圓的算法計(jì)算的x，y值與真實(shí)值誤差小于1。預(yù)處理后，生成每個(gè)點(diǎn)對(duì)需要11次加法運(yùn)算。

3.2 生成圓算法直接應(yīng)用于橢圓產(chǎn)生的誤差分析

如果直接把以上算法應(yīng)用于橢圓的生成，需要把r分別用橢圓的長(zhǎng)半軸和短半軸代替，而橢圓相對(duì)于直線(xiàn)x=y是非對(duì)稱(chēng)的，因此還需要算法擴(kuò)大區(qū)間生成第一象限的橢圓弧。

采用以上分析方法，當(dāng)kt=π/2時(shí)，令<1，解得r<213.59。r的取值范圍太小了，該算法由于誤差原因不能直接應(yīng)用于橢圓生成（后面給出一種方法解決此問(wèn)題）。

3.3 生成圓算法的實(shí)驗(yàn)分析

見(jiàn)圖1、圖2和圖3，把生成圓算法與直接計(jì)算進(jìn)行對(duì)比，用VB進(jìn)行編程實(shí)現(xiàn)。直接計(jì)算角度θ從0到π，變化的步長(zhǎng)也取t，直接用參數(shù)方程x=rcos（θ），y=rsin（θ）計(jì)算。生成圓算法誤差最大的地方在圓的π/4處（由于該位置迭代次數(shù)最多），把顯示分辨率設(shè)置成1024×768。由于半徑的值太大，把坐標(biāo)偏移量設(shè)為（cx，cy）。

Form1.Scale（0，768）-（1024，0）

cx=-Sin（3.1416/4）*r

cy=-Cos（3.1416/4）*r+500

m是圓弧的取點(diǎn)數(shù)，當(dāng)r值大時(shí)m的值也要大些，這樣可保證顯示足夠的點(diǎn)做對(duì)比。實(shí)驗(yàn)中觀察，改變m值對(duì)精度影響不大，精度主要取決于r 的大小。為顯示清晰，在畫(huà)點(diǎn)的位置繪制半徑為3的圓。生成圓算法在第一和第三列位置繪制兩次（實(shí)心圓），直接計(jì)算方法在第二和第三列繪制兩次（空心圓）。第一和第二列圓心的偏移量不同，第三列圓心的偏移量相同。由于r的值太大，顯示在屏幕上的點(diǎn)看上去象是在一條直線(xiàn)上。

r=35000時(shí)，第三列融合的很好，誤差很小。r=100000時(shí)，第三列圓有一半相交。r=200000時(shí)，第三列圓相切。在圖2和圖3中，下面位置顯示兩個(gè)點(diǎn)距離很近，這是因?yàn)檎眠x在圓的π/4處，繪圖時(shí)對(duì)稱(chēng)顯示的結(jié)果。

為準(zhǔn)確分析算法的誤差情況，采用編程計(jì)算的方法，對(duì)于不同的半徑r，整個(gè)圓周取2*π*r個(gè)點(diǎn)。對(duì)于所有的k（kt從0變化到π/4 ），計(jì)算a（6）-a*cos（kt）的值，并把絕對(duì)值最大者作為x的最大差；對(duì)于所有的k，計(jì)算b（5）-a*sin（kt）的值，并把絕對(duì)值最大者作為y軸方向的最大差。

從圖4數(shù)據(jù)可看出，當(dāng)r=27579時(shí)，算法計(jì)算坐標(biāo)值與直接計(jì)算法之差小于1，與理論分析吻合。另外，從輸出的結(jié)果可看出，計(jì)算的y比x誤差大，這是由于y的泰勒展開(kāi)式?jīng)]有x的展開(kāi)式階數(shù)高。當(dāng)r=200000時(shí)，y值的誤差較大。

4 橢圓的生成算法

在圖5中，圓的方程為：x2+y2=a2，橢圓的方程為：，其中，a為圓的半徑，又為橢圓的長(zhǎng)半軸，b為橢圓的短半軸。

設(shè)圓上B點(diǎn)坐標(biāo)為（acos（α），asin（α））（α在0和π/4之間），過(guò)B點(diǎn)作x軸的垂線(xiàn)交橢圓于A點(diǎn)，該點(diǎn)的坐標(biāo)為（acos（α），bsin（α））。B點(diǎn)相對(duì)于直線(xiàn)x=y的對(duì)稱(chēng)點(diǎn)為圓上的點(diǎn)D，D點(diǎn)的坐標(biāo)為（asin（α），acos（α））。過(guò)D作x軸的垂線(xiàn)，交橢圓于C點(diǎn)，解得C點(diǎn)的坐標(biāo)為（asin（α），bcos（α））。A點(diǎn)和C點(diǎn)為要繪圖的點(diǎn)，按生成圓的算法只要同步構(gòu)造出半徑分別為a和b的兩個(gè)圓，就可獲得A點(diǎn)和C點(diǎn)的坐標(biāo)值。具體算法與生成圓的算法類(lèi)似。

5 橢圓算法的算法分析

每次循環(huán)生成兩個(gè)點(diǎn)，進(jìn)行22次加法運(yùn)算，平均每個(gè)點(diǎn)需要11次加法運(yùn)算。由于橢圓需要生成1/4橢圓，而圓只需要生成1/8圓，其他部分由對(duì)稱(chēng)獲得。因此，生成橢圓的計(jì)算量相當(dāng)于圓的兩倍。采用以上方法構(gòu)造的橢圓生成算法，其運(yùn)算的精度與生成圓的算法是一樣的。

6 結(jié)束語(yǔ)

本文在等分圓周角的前提下，以泰勒公式為基礎(chǔ)，構(gòu)造出圓和橢圓的生成算法，所給出的圓和橢圓的算法已經(jīng)通過(guò)實(shí)驗(yàn)驗(yàn)證。當(dāng)圓的半徑、橢圓的長(zhǎng)半軸或短半軸t≤27579時(shí)，該算法是非常精確的。當(dāng)t≤100000時(shí)，相對(duì)誤差也不大，算法也是可用的（對(duì)一般的應(yīng)用已經(jīng)是足夠了）。通過(guò)對(duì)y構(gòu)造更高階的泰勒展開(kāi)式，可使算法的運(yùn)算精度進(jìn)一步提高。

該算法生成的點(diǎn)分布均勻、美觀，生成的點(diǎn)數(shù)可控，可應(yīng)用于對(duì)圖形輸出有較高要求的場(chǎng)合。預(yù)處理后，計(jì)算每個(gè)點(diǎn)對(duì)只需要11次加法運(yùn)算，避免了大量的三角函數(shù)運(yùn)算，因此，運(yùn)算速度快、運(yùn)算精度高。本文給出的構(gòu)造方法新穎，所提出的算法具有較強(qiáng)的理論和實(shí)用價(jià)值。

參考文獻(xiàn)：

[1] 孫家廣等.計(jì)算機(jī)圖形學(xué)[M].清華大學(xué)出版社，1998.

[2] 鄧四清，王平，謝進(jìn).有理四次插值樣條曲線(xiàn)的區(qū)域控制[J].計(jì)算機(jī)工

程與設(shè)計(jì)，2008.12：3243-3246

[3] 鄭豪.切割線(xiàn)法圓弧插補(bǔ)新算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)

計(jì)，2008.11：2984-2986

[4] 張博.圓的高質(zhì)量、快速生成算法[J].計(jì)算機(jī)應(yīng)用與軟件，1994.2：51-55

[5] 楊一山，顧耀林.基于樣條模型插值在科學(xué)可視化上的應(yīng)用[J].計(jì)算

機(jī)應(yīng)用，2006.5：1045-1047

[6] 屠曉明，劉雄偉.直線(xiàn)Bresenham生成算法的三維推廣[J].計(jì)算機(jī)輔

助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2001.9：13-16

[7] 王棟.Visual Basic程序設(shè)計(jì)[M].清華大學(xué)出版社，2002.

[8] 嚴(yán)偉敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，1997.