圓的掃描轉(zhuǎn)換

1、圓的掃描轉(zhuǎn)換錢文華2007年11月3日l 圖形的掃描轉(zhuǎn)換l 簡(jiǎn)單方程產(chǎn)生圓弧l 中點(diǎn)圓生成算法l 實(shí)例圖形的生成圖形的生成：是在指定的輸出設(shè)備上，根據(jù)坐標(biāo)描述構(gòu)造二維幾何圖形。圖形的掃描轉(zhuǎn)換圖形的掃描轉(zhuǎn)換：在光柵顯示器等數(shù)字設(shè)備上確定一個(gè)最佳逼近于圖形的象素集的過程。 圖形的掃描轉(zhuǎn)換本質(zhì)：離散量逼近連續(xù)量圓的掃描轉(zhuǎn)換解決的問題：解決的問題：l 圓心在原點(diǎn),繪制半徑為整數(shù)R的圓x2+y2=R2l 圓心坐標(biāo)(xc, yc),繪制半徑為整數(shù)R的圓(xxc)2+(y-yc)2=R21.1.八分法畫圓八分法畫圓(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)(x,

2、y)偽代碼void circlePoint(int x , int y) 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.2.簡(jiǎn)單方程產(chǎn)生圓弧簡(jiǎn)單方程產(chǎn)生圓弧算法原理算法原理：利用其函數(shù)方程，直接離散計(jì)算 圓的函數(shù)方程為： 222Ryx122111 x0,R2() iiiixxyroundRx 圓的極坐標(biāo)方程為： sincosRyRx11111 ()(cos) (sin)iiiiiix

3、round Ryround R 為 一 固 定 角 度 步 長(zhǎng)3.3.中點(diǎn)中點(diǎn)BresenhamBresenham畫圓畫圓構(gòu)造函數(shù)F(x,y)=x2+y2-R2對(duì)于圓上的點(diǎn)，有F(x,y)=0 yx3.3.中點(diǎn)中點(diǎn)BresenhamBresenham畫圓畫圓構(gòu)造函數(shù)F(x,y)=x2-y2-R2對(duì)于圓上的點(diǎn)，有F(x,y)=0對(duì)于圓內(nèi)的點(diǎn)，F(xiàn)(x,y)0 yx3.3.中點(diǎn)中點(diǎn)BresenhamBresenham畫圓畫圓構(gòu)造函數(shù)F(x,y)=x2-y2-R2對(duì)于圓上的點(diǎn)，有F(x,y)=0對(duì)于圓內(nèi)的點(diǎn)，F(xiàn)(x,y)0 算法原理算法原理: : x方向上的更新 y方向上的更新yx當(dāng)d0時(shí)，下一點(diǎn)取P

4、u(xi+1,yi)；當(dāng)d0時(shí)，下一點(diǎn)取Pd(xi+1,yi-1)。M的坐標(biāo)為：M(xi +1,yi-0.5)當(dāng)F(xM,yM)0時(shí)，取Pd(xi +1,yi-1)當(dāng)F(xM,yM)=0時(shí)，約定取Pu。構(gòu)造判別式構(gòu)造判別式：222)5.0()1()5.0, 1(),(RyxyxFyxFdiiiiMM誤差項(xiàng)的遞推誤差項(xiàng)的遞推32 32)5 .0()1( )5 .0()2( )5 .0, 2(222222iiiiiiiixdxRyxRyxyxFdd0： d0： 5)(2 )22()32()5 .0()1( )5 .1()2( )5 .1, 2(222222iiiiiiiiiiyxdyxRyxRyx

5、yxFd(b) d0的情況Pxixi+2xi+1yi-1yiyi-2誤差項(xiàng)的遞推誤差項(xiàng)的遞推判別式的初始值判別式的初始值022(1,0 .5 ) 1(0 .5 ) 1 .2 5dFRRRR112302()50iiiiiiiiiddxdddxyd 判別式的遞推判別式的遞推x x與與y y的更新的更新11,01,0iiiiixxydyyd 算法步驟算法步驟：1.輸入圓的半徑R。2.計(jì)算初始值d=1.25-R、x=0、y=R。3.繪制點(diǎn)(x,y)及其在八分圓中的另外七個(gè)對(duì)稱點(diǎn)。4.判斷d的符號(hào)。若d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)； 否則先將d更新為d+2(x-y)

6、+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)xy時(shí)，重復(fù)步驟3和4。否則結(jié)束。改進(jìn)：改進(jìn)：用d-0.25代替d算法步驟算法步驟：1.輸入圓的半徑R。2.計(jì)算初始值d=1-Rd=1-R、x=0、y=R。3.繪制點(diǎn)(x,y)及其在八分圓中的另外七個(gè)對(duì)稱點(diǎn)。4.判斷d的符號(hào),若d0d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)xy時(shí)，重復(fù)步驟3和4。否則結(jié)束void MidBresenhamcircle(int r) int x, y, d; x=0; y=r; d=1-r; /*賦初值*/ while(xy) /*循環(huán)退出條件*/ cir