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

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

中圖分類號：TP391 文獻標志碼：A 文章編號：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畫圓算法，圓和橢圓的中點生成法[1]。但以上算法生成的繪圖點分布不均勻，視覺效果不好。等分圓生成的點之間距離相等，顯示效果最佳。以等分圓周生成的橢圓效果也比普通方法有很顯著的改善。

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

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

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

1.1 圓方程的泰勒展開

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

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

1.2 構(gòu)造表達式

對于y構(gòu)造六個表達式：

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

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

1.3 系數(shù)的確定

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

解得：

采用同樣的方法可對x泰勒展開式進行構(gòu)造：

仿造上面方法還要構(gòu)造g5（k）、g4（k）…g0（k）等六個式子。設(shè)x=g6（k），令k=0，1，2，3，4，5，6，計算出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）分別存放表達式x 對應(yīng)的構(gòu)造表達式的值。初始時k=0，把k帶入構(gòu)造表達式并對數(shù)組元素進行初始化，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）分別存放表達式f5（k）、f4（k）、f3（k）、f2（k）、f1（k）、f0（k）的值。初始時k=0，代入構(gòu)造表達式對數(shù)組元素進行初始化，b（5）、b（4）、b（3）、b（2）、b（1）和b（0）的值分別為b5、b4、b3、b2、b1、b0。

⑴ 預處理

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

{

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

/*在（a（6），b（5））畫點，color為點的顏色*/

drawpixel（b（5），a（6），color）； /*在對稱點（b（5），a（6））處畫點*/

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 理論分析

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

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

由此可知，當r≤27340時，生成圓的算法計算的x，y值與真實值誤差小于1。預處理后，生成每個點對需要11次加法運算。

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

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

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

3.3 生成圓算法的實驗分析

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

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

cx=-Sin（3.1416/4）*r

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

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

r=35000時，第三列融合的很好，誤差很小。r=100000時，第三列圓有一半相交。r=200000時，第三列圓相切。在圖2和圖3中，下面位置顯示兩個點距離很近，這是因為正好選在圓的π/4處，繪圖時對稱顯示的結(jié)果。

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

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

4 橢圓的生成算法

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

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

5 橢圓算法的算法分析

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

6 結(jié)束語

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

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

參考文獻：

[1] 孫家廣等.計算機圖形學[M].清華大學出版社，1998.

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

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

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

計，2008.11：2984-2986

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

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

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

[6] 屠曉明，劉雄偉.直線Bresenham生成算法的三維推廣[J].計算機輔

助設(shè)計與圖形學學報，2001.9：13-16

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

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