基于Bresenham算法圓弧的設(shè)計(jì)與算法分析

唐啟見 湖南軟件職業(yè)學(xué)院

一、圓的構(gòu)建

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

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

圖1 Bresenham算法構(gòu)建1/8段圓弧

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

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點(diǎn)比Si點(diǎn)更靠近理論圓弧，即選擇Ti點(diǎn)更合適；反之選擇Si點(diǎn)。

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點(diǎn)，即：

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

若di＜0，則選擇Si點(diǎn)，即：

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

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

d1=3-2R

通過上述討論可通過Bresenham畫圓算法得到第一象限的1/8圓弧，再通過對(duì)稱復(fù)制的方法即可創(chuàng)建整個(gè)圓形。

二、橢圓的構(gòu)建

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

隱式方程式為：

選取第一象限的1/4段橢圓弧來進(jìn)行討論，如圖2所示，N為橢圓弧上的某個(gè)點(diǎn)，N左邊的點(diǎn)在區(qū)域-1，N右邊的點(diǎn)在區(qū)域2，設(shè)N點(diǎn)的斜率為-1，那么區(qū)域1的點(diǎn)的斜率大于-1，區(qū)域2的點(diǎn)的斜率小于-1。

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

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

對(duì)式(3)進(jìn)行求導(dǎo)：

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

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

b2x＜a2y

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

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

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

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

若di≥0，則選擇Ti點(diǎn)，此時(shí)有：

若di＜0，則選擇Si點(diǎn)，此時(shí)有：

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

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

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

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

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

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

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

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

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

三、結(jié)語

很多設(shè)計(jì)人員在LCD的GUI設(shè)計(jì)時(shí)面臨著算法的選擇，筆者也不例外，目前廣泛被大家接受的算法主要有數(shù)值微分法(DDA)、中點(diǎn)畫線法、Bresenham算法等，它們?cè)诓煌瑘D形設(shè)計(jì)時(shí)各具特色，這就需要設(shè)計(jì)人員根據(jù)自己的專長(zhǎng)與需要進(jìn)行選擇。筆者在進(jìn)行大量的實(shí)驗(yàn)的基礎(chǔ)上認(rèn)為Bresenham算法是一種具有高效性強(qiáng)、準(zhǔn)確度高等特點(diǎn)的算法。上述分析有不到之處敬請(qǐng)指教。