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

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

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

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

5、=5/4-r對應于e=1-r。決策變量d<0對應于e<-1/4。算法中其它與d有關的式子可把d直接換成e。又由于e的初值為整數，且在運算過程中的迭代值也是整數，故e始終是整數，所以e<-1/4等價于e<0。因此，可以寫出完全用整數實現的中點畫圓算法。要求：寫出用整數實現的中點畫圓算法程序，并上機調試，觀看運行結果。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