張 博， 周麗韞， 李興霞

?

中點生成橢圓的整數(shù)型算法

張 博， 周麗韞， 李興霞

（佳木斯大學(xué)應(yīng)用技術(shù)學(xué)院，黑龍江佳木斯154000）

在研究圓和橢圓生成算法基礎(chǔ)上，通過構(gòu)造遞推表達式，給出中點生成橢圓的整數(shù)型算法，并對算法效率進行了分析。算法初始化時需進行兩次乘法運算和一次移位運算，而生成各繪圖點時只需要整數(shù)型加法運算，因此算法運算精度高、速度快，適合硬件的實現(xiàn)。采用VB編寫程序?qū)λ惴ㄕ_性進行了驗證，該算法具有一定的理論和實用價值。

計算機應(yīng)用；橢圓；整數(shù)算法；中點；Bresenham算法

對直線、圓和橢圓等生成算法的研究是近幾年計算機圖形領(lǐng)域的熱點問題，關(guān)于圓和橢圓的生成算法較多，如Bresenham畫圓算法，中點畫圓法，橢圓雙步增量生成算法，圓的高質(zhì)量、快速生成算法等?？梢钥吹綑E圓的生成算法比圓的生成算法更加復(fù)雜，這些算法都采用構(gòu)造方法，通過遞推公式減少計算量，根據(jù)相應(yīng)的判定條件，每次生成圓或橢圓上一個點的坐標(biāo)，再調(diào)用畫點函數(shù)在顯示器上顯示。算法的理論基礎(chǔ)和構(gòu)造技巧極為重要，以下對中點生成橢圓原理進行闡述。

1 橢圓的描述及區(qū)間劃分

橢圓的方程為

其中為沿軸方向的長半軸長度，為沿軸方向短半軸長度。由于橢圓的對稱性，研究橢圓的生成問題，只需研究第一象限的橢圓弧。

考慮第一象限橢圓左上部分，分量的變化小于分量；在右下部分，分量的變化大于分量。以弧上切線斜率為-1的點作為分界，把橢圓弧的劃分為兩個部分，假設(shè)該點坐標(biāo)為(,)，該點的切線方程為

橢圓第一部分為0≤≤時生成的橢圓?。坏诙糠譃椤堋軙r生成的橢圓弧。把長半軸與短半軸互換，對應(yīng)的橢圓方程為

橢圓第一部分為0≤≤時生成的橢圓弧的對應(yīng)坐標(biāo)，按橫縱坐標(biāo)對調(diào)可以生成以上方程 （1）第二部分的橢圓弧。

由此可見，對于以上兩部分橢圓弧的生成，只需解決第一部分的橢圓弧的生成問題。

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

變換橢圓方程得

當(dāng)(,)>0時，坐標(biāo)點(,)在橢圓的外側(cè)。

當(dāng)(,)=0時，坐標(biāo)點(,)在橢圓上。

當(dāng)(,)<0時，坐標(biāo)點(,)在橢圓的內(nèi)側(cè)。

0≤≤，每次遞增量為1。

下面構(gòu)造遞推公式，根據(jù)已知的坐標(biāo)點(,)，確定下一個要選取的坐標(biāo)點，由(,)計算(+1,)和(+1,-1)。

取和-1的中間點，計算(+1,-0.5)得

確定一個點后的值要加1，重復(fù)以上構(gòu)造步驟，直到>時為止。

3 算法及說明

MidpointEllipse實現(xiàn)橢圓弧的繪制。為橢圓的兩軸，為橫坐標(biāo)，為縱坐標(biāo)。的每次增加量為1。While循環(huán)的結(jié)束條件為≤。

為前面構(gòu)造的函數(shù)(,)隨,的變化需要遞加偏移量。

用來構(gòu)造。

用來構(gòu)造。

為中點判別式。

繪制第一象限的橢圓弧由兩次調(diào)用完成：

MidpointEllipse( a, b, color );

MidpointEllipse( b, a, color );

其它三個象限可由對稱性生成。

算法描述：

MidpointEllipse( a , b ,color )

int a, b, color;

{

int x, y;

long u, v, p, midcon, q, f, delt ;

x = 0; /*初始化*/

y = b;

p = 0;

u = a * a;

v = b * b;

midcon = Int( u / 4 ); /*可用移位運算代替*/

q = u * y;

While ( p <= q ) /*循環(huán)結(jié)束條件*/

{

If ( a > b ) /*a>b時，畫線在橢圓的第一部分*/

{

drawpixel( x, y, color ); /*在坐標(biāo)( x, y )位置color顏色畫點*/

}

Else

{

drawpixel( y, x, color ); /*畫線在橢圓的第二部分，坐標(biāo)互換*/

}

f = f + p + p + v; /*計算x加1后，f和p的值*/

p = p + v;

x = x+1;

delt = f-q + midcon;

If ( delt > 0) /*delt>0取中點下面的點，否則取上面的點*/

{

f = f -q - q + u;

q = q – u;

y = y – 1;

}

} /*While結(jié)束*/

} /* MidpointEllipse*/

4 算法分析

以上算法執(zhí)行兩次調(diào)用，初始化需要一定時間，而算法的運行時間主要取決于While循環(huán)的次數(shù)。

由

解得

再把兩個循環(huán)次數(shù)相加，可得中點生成橢圓整數(shù)型算法的時間復(fù)雜度為次加法運算。

5 中點生成橢圓的整數(shù)型算法的驗證

見圖1，用VB編寫程序顯示三個1/4圓周的橢圓?。ㄆ渲?4000,=2000），第一個是用“中點生成橢圓的整數(shù)算法”實現(xiàn)的，第二個是用常規(guī)直接計算法實現(xiàn)的（給定，根據(jù)橢圓方程計算點，再進行顯示）。第三個圖形是兩種算法生成的圖形共同顯示，看一下圖形重疊情況，用以驗證算法的正確性。采用多組數(shù)據(jù)進行實際驗證，第三個圖形都重合的很好。

圖1 橢圓生成算法驗證

6 結(jié)束語

本文給出的算法已經(jīng)編寫程序上機進行了驗證，生成的點平滑、連續(xù)性好。初始化后，算法采用整數(shù)加法運算，運算精度高、速度快，非常適合硬件的實現(xiàn)。中點生成橢圓的整數(shù)算法在遞推公式的構(gòu)造上有特點，算法具有一定的理論和實用價值。

[1] 劉勇奎. 直線與曲線的逐點生成算法[J]. 工程圖學(xué)學(xué)報, 2005, 26(6): 41-50.

[2] 劉 凱, 侯伯亨, 吳成柯. 橢圓雙步增量生成算法及其硬件實現(xiàn)[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2003, 15(4): 18-21.

[3] 張 博. 圓的高質(zhì)量、快速生成算法[J]. 計算機應(yīng)用與軟件, 1994, 11(2): 51-55.

[4] 譚浩強, 張基溫, 唐永炎. C語言程序設(shè)計教程[M].北京: 高等教育出版社, 1999. 69-90.

[5] 嚴偉敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京: 清華大學(xué)出版社, 1997. 21-26.

Integer Algorithm of Midpoint Generating Ellipse

ZHANG Bo, ZHOU Li-yun, LI Xing-xia

( College of Application Technology, Jiamusi University, Jiamusi Heilongjiang 154000, China )

Based on the research on circle and ellipse generating algorithm, integer algorithm of midpoint generating ellipse is presented by constructing recursion expressions, whose efficiency is also analysed. In initialization, the algorithm needs conduct multiplication twice and shift operation once, and every graphic point is calculated by integer addition, so the algorithm is fast and precise and can be realized by hardware. The correctness of the algorithm is tested by VB programming, and it is of theoretical and practical value.

computer application; ellipse; integer algorithm; midpoint; Bresenham algorithm

TP 391

A

1003-0158(2011)01-0001-04

2009-03-20

張 博（1966-），男，黑龍江伊春人，副教授，主要研究方向為計算機算法。