基于Bresenham算法圓弧的設計與算法分析

唐啟見 湖南軟件職業學院

一、圓的構建

圓形是在GUI設計過程中不可規避的重要圖形，可以通過確定“一點一線”來描述一個圓形，“一點”為圓心，“一線”為圓的半徑，圓心確定了圓的位置，半徑確定了圓的大小。圓形及圓弧的生成算法主要有數值微分法、Bresenham畫圓算法和中點畫線法等。

由于圓形是一個對稱的結構，不但左右對稱，而且中心對稱，所以利用Bresenham畫圓算法只需要繪制出圓的一段圓弧，然后通過對稱復制的方法即可實現整個圓的繪制。首先確定目標圓的圓心，然后以圓心為坐標原點建立對稱坐標系，如先繪制第一象限的1/8段圓弧(如圖1所示)。設最先確定的逼近像素點Pi-1的坐標為(xi-1,yi-1)，那么在圓弧附近有兩個或者多個逼近像素點，如圖1中的Si(xi-1+1,yi-1)和Ti(xi-1+1,yi-1-1)點，在這兩個點的選擇時需要計算這兩個點離理論圓弧的距離，選擇離理論圓弧比較近的那個點作為圓弧構建的下一個像素點，以此類推，可以形成一段1/8段圓弧。下面來討論一下Si點和Ti點到理論圓弧的距離，設Si點和Ti點到理論圓弧的距離分別為D(Si)、D(Ti)，計算公式如下：

圖1 Bresenham算法構建1/8段圓弧

因為Si點和Ti點的坐標分別為(xi-1+1,yi-1)、(xi-1+1,yi-1-1)，那么Si點和Ti點分別離坐標原點即圓心的距離的平方分別為：(xi-1+1)2+yi-12、(xi-1+1)2+(yi-1-1)2，將它們與圓的半徑的平方做差就可以得出Si點和Ti點離理論圓弧的距離大小了。假設Si點在圓弧的外部，Ti點在圓弧的內部。

D(Si)=[(xi-1+1)2+yi-12]-R2

D(Ti)=R2-[(xi-1+1)2+(yi-1-1)2]

令di=D(Si)-D(Ti)，如果di＞0，說明Ti點比Si點更靠近理論圓弧，即選擇Ti點更合適；反之選擇Si點。

di=D(Si)-D(Ti)=[(xi-1+1)2+yi-12]-2R2+[(xi-1+1)2+(yi-1-1)2] (1)

將i+1代入(1)式中，得：

di+1=[(xi+1)2+yi2]-2R2+[(xi+1)2+(yi-1)2]

將di+1-di，得：

di+1-di=2[(xi+1)2-(xi-1+1)2]+(yi2-yi-12)+(yi-1)2-(yi-1-1)2

如果di≥0，則選擇Ti點，即：

xi=xi-1+1，yi=yi-1-1，di+1=di+4(xi-1-yi-1)+10

若di＜0，則選擇Si點，即：

xi=xi-1+1，yi=yi-1，di+1=di+4xi-1+6

以此類推，可通過計算di和di+1來對Si和Ti進行取舍。將i=1、x0=0、y0=R代入式(1)中：

d1=3-2R

通過上述討論可通過Bresenham畫圓算法得到第一象限的1/8圓弧，再通過對稱復制的方法即可創建整個圓形。

二、橢圓的構建

橢圓與圓的形狀的相似性，決定了它們的算法具有一定的相似性。橢圓也是一個對稱結構的圖形，由于橢圓的對稱性相對于圓形的對稱性來說有一定的局限性，所以需要把橢圓的在一個象限的1/4段圓弧構建出來，然后再用對稱復制的方法形成整個橢圓。首先將坐標原點設為橢圓的中心點，x軸方向的半徑設為a，y軸方向的半徑設為b，橢圓上的點如下關系：

隱式方程式為：

選取第一象限的1/4段橢圓弧來進行討論，如圖2所示，N為橢圓弧上的某個點，N左邊的點在區域-1，N右邊的點在區域2，設N點的斜率為-1，那么區域1的點的斜率大于-1，區域2的點的斜率小于-1。

圖2 Bresenham算法構建橢圓弧(一)

通過上述分析，以N點為界分為區域1和區域2兩個區域，在區域1中，x增長速度比y減小的速度要快，所以選取x軸為基軸進行討論，反之在區域2中，x增長速度比y減小的速度要慢，所以選取y軸為基軸進行討論。無論是在區域1作圖時隨著x的不斷加1，y是否作減1？還是在區域2作圖時隨著y的不斷減1，x是否作加1？都需要通過計算來決定。若在區域1作圖時，每確定一點后都需要判斷是否到達N點。如果到達N點，就需要轉換到區域2進行作圖。由式(2)得：

對式(3)進行求導：

dy/dx=-(b2·x)/(a2y)

如果斜率大于-1(區域1)，則有：

b2x＜a2y

根據Bresenham算法的基本思想進行討論，首先建立對稱坐標系，把坐標原點定為橢圓中心點。設Pi-1點為已確定的逼近像素點，坐標為(xi-1,yi-1)，Pi-1點有兩個靠近點Si點和Ti點，它們的坐標分別為：(xi-1+1,yi-1)、(xi-1+1,yi-1-1)。下面來分析討論這兩個點哪一個更靠近理論橢圓弧，然后選擇更靠近的那個點作為橢圓弧的逼近像素點。設Si點和Ti點離橢圓弧的距離分別為D(Si)和D(Ti)，則有：

令di=D(Si)-D(Ti)，如果di≥0，則選擇Ti點作為橢圓弧的逼近像素點；反之則選擇Si點。

用i+1替代式(4)中的i，得：

將di+1-di，即可得到：

若di≥0，則選擇Ti點，此時有：

若di＜0，則選擇Si點，此時有：

同理，將di的初始值為d1，代入式(4)得：

下面來討論在區域2作圖時的情況。如圖3所示，設Pi-1點為已確定的逼近像素點，坐標為(xi-1,yi-1)，Pi-1點有兩個靠近點Si點和Ti點，坐標分別為：(xi-1+1,yi-1)、(xi-1+1,yi-1-1)。同理，設Si點和Ti點離橢圓弧的距離分別為D(Si)和D(Ti)，則有：

圖3 Bresenham算法構建橢圓弧(二)

D(Si)=b2·(xi-1+1)2+a2·(yi-1-1)2-a2·b2

D(Ti)=a2·b2-b2·xi-12-a2·(yi-1-1)2

根據式(2)同理可知，選擇D(Si)和D(Ti)中更接近0的點即可。

用i+1代替式(5)中的i，得：

將di+1-di，可以得到：

若di≥0，選擇Ti點作為橢圓弧的逼近像素點：

若di＜0，選擇Si點作為橢圓弧的逼近像素點：

三、結語

很多設計人員在LCD的GUI設計時面臨著算法的選擇，筆者也不例外，目前廣泛被大家接受的算法主要有數值微分法(DDA)、中點畫線法、Bresenham算法等，它們在不同圖形設計時各具特色，這就需要設計人員根據自己的專長與需要進行選擇。筆者在進行大量的實驗的基礎上認為Bresenham算法是一種具有高效性強、準確度高等特點的算法。上述分析有不到之處敬請指教。