圓的掃描轉換錢文華2007年11月3日圖形的掃描轉換

簡單方程產生圓弧中點圓生成算法實例圖形的生成：是在指定的輸出設備上，根據坐標描述構造二維幾何圖形。圖形的掃描轉換：在光柵顯示器等數字設備上確定一個最佳逼近于圖形的象素集的過程。

圖形的掃描轉換本質：離散量逼近連續量圓的掃描轉換解決的問題：圓心在原點,繪制半徑為整數R的圓x2+y2=R2圓心坐標(xc,yc),繪制半徑為整數R的圓(x－xc)2+(y-yc)2=R21.八分法畫圓(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)(x,y)偽代碼voidcirclePoint(intx,inty){

putpixel(x,y);

putpixel(y,x);

putpixel(-y,x);

putpixel(-x,y);

putpixel(-x,-y);

putpixel(-y,-x);

putpixel(y,-x);

putpixel(x,-y);}2.簡單方程產生圓弧算法原理：利用其函數方程，直接離散計算圓的函數方程為：

圓的極坐標方程為：3.中點Bresenham畫圓構造函數F(x,y)=x2+y2-R2對于圓上的點，有F(x,y)=0

yx3.中點Bresenham畫圓構造函數F(x,y)=x2-y2-R2對于圓上的點，有F(x,y)=0對于圓內的點，F(x,y)<0

yx3.中點Bresenham畫圓構造函數F(x,y)=x2-y2-R2對于圓上的點，有F(x,y)=0對于圓內的點，F(x,y)<0對于圓外的點，F(x,y)>0

算法原理:

x方向上的更新

y方向上的更新yx當d≤0時，下一點取Pu(xi+1,yi)；當d>0時，下一點取Pd(xi+1,yi-1)。M的坐標為：M(xi

+1,yi-0.5)當F(xM,yM)<0時，取Pu(xi

+1,yi)當F(xM,yM)>0時，取Pd(xi

+1,yi-1)當F(xM,yM)=0時，約定取Pu。構造判別式：誤差項的遞推d≤0：

d>0：

誤差項的遞推判別式的初始值判別式的遞推x與y的更新算法步驟：1.輸入圓的半徑R。2.計算初始值d=1.25-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d≤0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當x<y時，重復步驟3和4。否則結束。改進：用d-0.25代替d算法步驟：1.輸入圓的半徑R。2.計算初始值d=1-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號,若d≤0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當x<y時，重復步驟3和4。否則結束voidMidBresenhamcircle(intr){

intx,y,d;x=0;y=r;d=1-r;/*賦初值*/

while(x<y)/*循環退出條件*/{

circlePoint(x,y);/*繪制一個點*/if(d<0)d+=2*x+3;/*判別式更新*/else{d+=2*(x-y)+5;y--;/*y方向上走一步*/}x++;/*x方向上走一步*/}/*while循環結