中心算法畫圓

1、精選優(yōu)質(zhì)文檔-傾情為你奉上2.2.2 中點(diǎn)算法生成圓中點(diǎn)畫圓算法在一個方向上取單位間隔，在另一個方向的取值由兩種可能取值的中點(diǎn)離圓的遠(yuǎn)近而定。實際處理中，用決策變量的符號來確定象素點(diǎn)的選擇，因此算法效率較高。設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，起點(diǎn)在(0，R)處，終點(diǎn)在(，)處，順時針生成八分之一圓，利用對稱性掃描轉(zhuǎn)換全部圓。為了應(yīng)用中點(diǎn)畫圓法，我們定義一個圓函數(shù)F(x，y)=x2+y2-R2(219)任何點(diǎn)(x，y)的相對位置可由圓函數(shù)的符號來檢測：F(x，y)<0點(diǎn)(x，y)位于數(shù)學(xué)圓內(nèi)=0點(diǎn)(x，y)位于數(shù)學(xué)圓上>0點(diǎn)(x，y)位于數(shù)學(xué)圓外(220)如下圖所示，圖中有

2、兩條圓弧A和B，假定當(dāng)前取點(diǎn)為Pi(xi，yi)，如果順時針生成圓，那么下一點(diǎn)只能取正右方的點(diǎn)E(xi+1，yi)或右下方的點(diǎn)SE(xi+1，yi-1)兩者之一。中點(diǎn)畫線算法假設(shè)M是E和SE的中點(diǎn)，即 ，則：1、當(dāng)F(M)<0時，M在圓內(nèi)(圓弧A)，這說明點(diǎn)E距離圓更近，應(yīng)取點(diǎn)E作為下一象素點(diǎn)；2、當(dāng)F(M)>0時，M在圓外(圓弧B)，表明SE點(diǎn)離圓更近，應(yīng)取SE點(diǎn)；3、當(dāng)F(M)=0時，在E點(diǎn)與SE點(diǎn)之中隨便取一個即可，我們約定取SE點(diǎn)。 因此，我們用中點(diǎn)M的圓函數(shù)作為決策變量di，同時用增量法來迭代計算下一個中點(diǎn)M的決策變量di+1。(221)下面分兩種情況來討論在迭代計算中決

3、策變量di+1的推導(dǎo)。1、見圖（a），若di<0，則選擇E點(diǎn)，接著下一個中點(diǎn)就是，這時新的決策變量為：(222)（a）(di<0) 中點(diǎn)畫線算法式(222)減去(221)得：di+1=di+2xi+3(223)2、見圖（b），若di0，則選擇SE點(diǎn)，接著下一個中點(diǎn)就是 ，這時新的決策變量為：(224)（b）(di0) 中點(diǎn)畫線算法式(224)減去(221)得：di+1=di+2(xi-yi)+5(225)我們利用遞推迭代計算這八分之一圓弧上的每個點(diǎn)，每次迭代需要兩步處理：（1）用前一次迭代算出的決策變量的符號來決定本次選擇的點(diǎn)。（2）對本次選擇的點(diǎn)，重新遞推計算得出新的決策變量的值

4、。剩下的問題是計算初始決策變量d0，如下圖所示。對于初始點(diǎn)(0，R)，順時針生成八分之一圓，下一個中點(diǎn)M的坐標(biāo)是 ，所以：(226)生成圓的初始條件和圓的生成方向1、輸入：圓半徑r、圓心(x0，y0)；2、確定初值：x=0，y=r、d=5/4-r；3、While(x<=y)·利用八分對稱性，用規(guī)定的顏色color畫八個象素點(diǎn)(x，y)；· 若d0y=y-1； d=d+2(x-y)+5)；否則d=d+2x+3；·x=x+1；s 在上述算法中，使用了浮點(diǎn)數(shù)來表示決策變量d。為了簡化算法，擺脫浮點(diǎn)數(shù)，在算法中全部使用整數(shù)，我們使用e=d-1/4代替d。顯然，初值d

5、=5/4-r對應(yīng)于e=1-r。決策變量d<0對應(yīng)于e<-1/4。算法中其它與d有關(guān)的式子可把d直接換成e。又由于e的初值為整數(shù)，且在運(yùn)算過程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e<-1/4等價于e<0。因此，可以寫出完全用整數(shù)實現(xiàn)的中點(diǎn)畫圓算法。要求：寫出用整數(shù)實現(xiàn)的中點(diǎn)畫圓算法程序，并上機(jī)調(diào)試，觀看運(yùn)行結(jié)果。void MidpointCircle(int x0,int y0,int r,int color)int x,y;float d;x=0;y=r;d=5.0/4-r;while(x<=y)putdot(x0,y0,x,y,color);if(d<0)d+=x*2.0+3;elsed+=2.0*(x-y)+5;y-; x+;putdot(x0,y0,x,y,color)putpixel(x0+x,y0+y,color);putpixel(x0+x,y0-y,color);putpixel(x0-x,y0+y,color);putpixel(x0-x,y0-y,color);putpixel(x0+y,y0+x,color