lesson04圓與橢圓的生成算法市公開課特等獎(jiǎng)市賽課微課一等獎(jiǎng)?wù)n件

lessonfour2.2

圓與橢圓掃描轉(zhuǎn)換算法1第二章第二節(jié)第1頁(yè)1、園特征依據(jù)圓方程：(x2+y2)=R2用掃描線方式生成圓時(shí)，會(huì)出現(xiàn)x方向增量取1，則y=±(R2-x2)1/2,這種方法，既增加了運(yùn)算復(fù)雜性，又會(huì)產(chǎn)生點(diǎn)集疏密不均現(xiàn)象：當(dāng)x=0時(shí)，圓周上切線斜率為零；當(dāng)x靠近R時(shí)，圓周上切線斜率趨向無(wú)窮大，所以出現(xiàn)靠近y軸處點(diǎn)集較密集、平坦，但靠近x軸處間隔較大、陡直。為了克服這一現(xiàn)象，能夠使x值改變范圍從0到R/21/2，即處為止，同時(shí)對(duì)于每一組(x,y)值，利用對(duì)稱求出其它7個(gè)點(diǎn)坐標(biāo)。yx2第二章第二節(jié)第2頁(yè)圓八對(duì)稱性圓被定義為到給定中心位置(xc,yc)距離為r點(diǎn)集。圓心位于原點(diǎn)圓有四條對(duì)稱軸x=0,y=0,x=y和x=-y。若已知圓弧上一點(diǎn)(x,y),能夠得到其關(guān)于四條對(duì)稱軸其它7個(gè)點(diǎn)，這種性質(zhì)稱為圓八對(duì)稱性。所以，只要掃描轉(zhuǎn)換八分之一圓弧，就能夠求出整個(gè)圓弧象素集。voidCirclePoints(intx,inty,intcolor){drawpixel(x,y,color);drawpixel(y,x,color);drawpixel(-x,y,color);drawpixel(y,-x,color);drawpixel(x,-y,color);drawpixel(-y,x,color);drawpixel(-x,-y,color);drawpixel(-y,-x,color);}3第二章第二節(jié)第3頁(yè)中點(diǎn)畫圓法

假如我們結(jié)構(gòu)函數(shù)

F(x,y)=x2+y2-R2，則對(duì)于圓上點(diǎn)有F(x,y)=0，對(duì)于圓外點(diǎn)有F(x,y)>0，對(duì)于圓內(nèi)點(diǎn)F(x,y)<0。與中點(diǎn)畫線法一樣，結(jié)構(gòu)判別式：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若

d<0，則應(yīng)取P1為下一象素，而且再下一象素判別式為：d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3若d≥0，則應(yīng)取P2為下一象素，而且下一象素判別式為d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2(xp-yp)+5我們這里討論第一個(gè)象素是（0,R），判別式d初始值為：d0=F(1,R-0.5)=1.25-R4第二章第二節(jié)第4頁(yè)中點(diǎn)畫圓算法MidPointCircle(intr，intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;circlepoints(x,y,color);while(x<=y){if(d<0)d+=2*x+3;else{d+=2*(x-y)+5;y--;}x++;circlepoints(x,y,color);}}5第二章第二節(jié)第5頁(yè)Bresenham圓算法Bresenham圓算法基本思想是尋找最靠近于實(shí)際圓周上點(diǎn)?，F(xiàn)僅討論八分之一圓周，

即x從0到R/21/2范圍，

所以F，G情況無(wú)須列入在內(nèi)。

對(duì)于Pi-1下一點(diǎn)Pi只有兩種可能，

即Si(xi-1+1,yi-1)和Ti(xi-1+1,yi-1-1)

誤差公式：D(Si)=(xi-1+1)2+(yi-1)2-R2

D(Ti)=(xi-1+1)2+(yi-1-1)2-R2

當(dāng)|D(Si)|≥|D(Ti)|，則Ti更靠近于圓周，選擇Ti

當(dāng)|D(Si)|＜|D(Ti)|，則Si更靠近于圓周，選擇Si

令di=|D(Si)|-|D(Ti)|

則

di≥0，取Ti

di＜0，取SiPi-1ABDEFGSiTi6第二章第二節(jié)第6頁(yè)圓生成算法原理情況C：因?yàn)镾i在圓外，所以D(Si)＞0，因?yàn)門i在圓內(nèi)，所以D(Ti)＜0所以di=D(Si)+D(Ti)情況A,B：①?gòu)膱A上看，Si更靠近于圓周，選擇Si(應(yīng)屬于di＜0情況）②因?yàn)镾i,Ti都在圓內(nèi)或圓上，即D(Si)≤0，D(Ti)＜0，所以用式di=D(Si)+D(Ti)(di＜0,取Si)判別即可。情況D,E：①?gòu)膱A上看，Ti更靠近于圓周，選擇Ti(應(yīng)屬于di>0情況）②因?yàn)镾i，Ti都在圓外或圓上，即D(Si)＞0，D(Ti)≥0，所以用式di=D(Si)+D(Ti)(di＞0,取Ti)判別即可?？偠灾贸?，只要計(jì)算下式di=D(Si)+D(Ti)符號(hào)，便可選定Si或Ti作為下一點(diǎn)。Pi-1ABCDEFGSiTi7第二章第二節(jié)第7頁(yè)圓生成算法改進(jìn)

設(shè)x0=0，y0=R，

則S1為(1,R)，T1為(1,R-1)，

d1=(12+R2-R2)+[(12+(R-1)2-R2]=3-2R

設(shè)Pi-1為(xi-1,yi-1)，則取下一點(diǎn)

Si

(xi-1+1,yi-1)，Ti

(xi-1+1,yi-1-1)，

則：di=[(xi-1+1)2+yi-12-R2]+[(xi-1+1)2+(yi-1-1)2-R2]

假設(shè)di＜0，則取Si作為下一點(diǎn)，

即Pi(xi-1+1,yi-1)且Si+1為(xi-1+2,yi-1)，Ti+1為(xi-1+2,yi-1-1)， 則：di+1=[(xi-1+2)2+(yi-1)2-R2]+[(xi-1+2)2+(yi-1-1)2-R2]

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

di+1=di+4xi-1+68第二章第二節(jié)第8頁(yè)圓生成算法改進(jìn)假設(shè)di≥0，則取Ti作為下一點(diǎn)，

即Pi(xi-1+1,yi-1-1)則第i+1次兩個(gè)可能點(diǎn)為

Si+1

(xi-1+2,yi-1-1)，Ti+1

(xi-1+2,yi-1-2)

di+1=[(xi-1+2)2+(yi-1-1)2-R2]+[(xi-1+2)2+(yi-1-2)2-R2]

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

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

即得di遞歸式:

d1=3-2R

(x0=0,y0=R)

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

當(dāng)di＜0時(shí)，取Si(xi-1+1,yi)

di+1=di+4(xi-1-yi-1)+10 當(dāng)di≥0時(shí)，取Ti(xi-1+1,yi-1)9第二章第二節(jié)第9頁(yè)圓生成算法描述置第一點(diǎn)坐標(biāo)：x=0，y=R置初始誤差：d=3-2Rwhilex＜ydo

begin

輸出點(diǎn)(x,y)以及其它7點(diǎn)(y,x),(-x,y),

(-y,x),(-y,-x),(-x,-y),(x,-y),(y,-x)

ifd＜0thend=d+4·x+6

elsed=d+4·(x-y)+10，y=y-1

x=x+1

endif

x=ythen輸出點(diǎn)(x,y)以及(-x,y),(-x,-y),(x,-y)endofalgorithm10第二章第二節(jié)第10頁(yè)2、橢圓特征橢圓被定義為到兩個(gè)定點(diǎn)(焦點(diǎn))距離之和等于常數(shù)點(diǎn)集合。橢圓上任意點(diǎn)p(x,y)到兩個(gè)焦點(diǎn)距離記為d1和d2，那么，橢圓方程可表示為：d1+d2=常數(shù)設(shè)兩個(gè)焦點(diǎn)坐標(biāo)F1=(x1,y1)和F2=(x2,y2)來(lái)表示橢圓方程： [(x-x1)2+(y-y1)2]1/2+[(x-x2)2+(y-y2)2]1/2=常數(shù)改寫橢圓方程，則通用橢圓方程： Ax2+By2+Cxy+Dx+Ey+F=011第二章第二節(jié)第11頁(yè)標(biāo)準(zhǔn)位置橢圓：長(zhǎng)軸和短軸與X和Y軸平行，橢圓中心可在(xc,yc)。標(biāo)準(zhǔn)位置橢圓方程： [(x-xc)/rx]2+[(y-yc)/ry]2=1 其中：rx和ry分別為長(zhǎng)半軸和短半軸。極坐標(biāo)表示： x=xc+rxcosθ,y=yc+rysinθ標(biāo)準(zhǔn)位置橢圓其在四分象限是對(duì)稱，所以我們只需要計(jì)算一個(gè)四分象限橢圓曲線位置，然后依據(jù)對(duì)稱性得到其余部分。12第二章第二節(jié)第12頁(yè)3.5.2中點(diǎn)橢圓算法首先計(jì)算橢圓中心在(0,0)標(biāo)準(zhǔn)位置橢圓曲線第一分象限曲線部分位置像素(x,y)，然后將點(diǎn)變換到橢圓中心在(xc,yc)。依據(jù)前面DDA算法討論，當(dāng)|m|≤1時(shí)，取x方向單位步長(zhǎng)(1或-1)，相反，取y方向單位步長(zhǎng)(1或-1)。所以，對(duì)于第一分象限橢圓曲線分成兩部分：一部分曲線斜率絕對(duì)值小于1和斜率絕對(duì)值大于1。并分別對(duì)兩段曲線分別取x方向步長(zhǎng)和y方向取步長(zhǎng).13第二章第二節(jié)第13頁(yè)這里可選擇(0,ry)或(rx,0)作為起點(diǎn)開始算法。以從(0,ry)開始從左到右進(jìn)行。橢圓函數(shù)作為決議參數(shù)： fellipse(x,y)=ry2x2+rx2y2-rx2ry2

該函數(shù)含有以下特征： <0(x,y)位于橢圓邊界內(nèi)fellipse(x,y)=0(x,y)位于橢圓邊界上 >0(x,y)位于橢圓邊界外橢圓函數(shù)fellipse(x,y)作為中點(diǎn)橢圓算法決議參數(shù)。在每個(gè)取樣位置，按照橢圓函數(shù)在沿橢圓軌跡兩個(gè)候選像素點(diǎn)中點(diǎn)求值符號(hào)選擇下一個(gè)像素

14第二章第二節(jié)第14頁(yè)從(0,ry)開始，在x方向取單位步長(zhǎng)1直到斜率變?yōu)椤?1。橢圓斜率： dy/dx=-ry2x/rx2y兩段曲線采取不一樣算法分界點(diǎn)： 2ry2x=2rx2y對(duì)于第1段曲線設(shè)用該算法計(jì)算出點(diǎn)(xk,yk)，下一個(gè)點(diǎn)(xk+1,yk+1)為A(xk+1,yk)或B(xk+1,yk-1)，即右邊點(diǎn)或右下點(diǎn)。依據(jù)以下決議參數(shù)符號(hào)判斷：15第二章第二節(jié)第15頁(yè) p1k=fellipse(xk+1,yk-0.5)=ry2(xk+1)2+rx2(yk-0.5)2-rx2ry2

下一點(diǎn)判斷：當(dāng)p1k<0，取A(xk+1,yk)，yk+1=yk當(dāng)p1k≥0，取B(xk+1,yk-1)，yk+1=yk-1其中xk+1=xk+1遞歸表示式：p1k+1=p1k+2ry2(xk+1)+ry2+rx2[(yk+1-0.5)2-(yk-0.5)2]16第二章第二節(jié)第16頁(yè)初始決議參數(shù)：將(x0,y0)=(0,ry)帶入:p10=fellipse(1,ry-0.5)=ry2-rx2ry+rx2/4該橢圓第一分象限第一部分橢圓曲線中點(diǎn)算法表示：p10=ry2-rx2ry+rx2/4xk+1=xk+1yk+1=yk，p1k+1=p1k+2ry2xk+1+ry2當(dāng)p1k<0yk+1=yk-1，p1k+1=p1k+2ry2xk+1+ry2-2rx2yk+1當(dāng)p1k≥017第二章第二節(jié)第17頁(yè)決議參數(shù)增量=2ry2xk+1+ry2當(dāng)p1k<02ry2xk+1+ry2-2rx2yk+1當(dāng)p1k≥0對(duì)于2ry2xk+1和2rx2yk+1本身又是一個(gè)增量表示式，2ry2xk+1增量一直為2ry2，而2rx2yk+1增量為0(當(dāng)p1k<0)或-2rx2(當(dāng)p1k≥0)，在起始位置(x0,y0)=(0,ry)，2ry2xk+1和2rx2yk+1初始值分別為0和2rx2ry。18第二章第二節(jié)第18頁(yè)然而對(duì)于第一分象限第2段曲線，取y方向單位步長(zhǎng)。在每一步，計(jì)算決議參數(shù)時(shí)取兩個(gè)候選水平像素中點(diǎn)。設(shè)前一步取(xk,yk)，下一個(gè)點(diǎn)(xk+1,yk+1)選擇：B(xk,yk-1)或A(xk+1,yk-1)，即下邊點(diǎn)或右下點(diǎn)。M(xk+0/5,yk-1)為AB中點(diǎn)。依據(jù)以下決議參數(shù)符號(hào)判斷：p2k=fellipse(xk+0.5,yk-1)=ry2(xk+0.5)2+rx2(yk-1)2-rx2ry2

19第二章第二節(jié)第19頁(yè)取點(diǎn)判斷：p2k≤0，取(xk+1,yk-1),(xk+1,yk+1)=(xk+1,yk-1),即右下點(diǎn)Ap2k>0，取(xk,yk-1),(xk+1,yk+1)=(xk,yk-1),即下邊點(diǎn)B遞歸表示式： p2k+1=p2k-2rx2(yk-1)+rx2+ry2[(xk+1+0.5)2-(xk+0.5)2]20第二章第二節(jié)第20頁(yè)當(dāng)從第一分象限橢圓第1段曲線進(jìn)入第2段曲線時(shí)，采取p2k作為決議參數(shù)，此時(shí)，p2k初始點(diǎn)為第段曲線最終計(jì)算點(diǎn)，設(shè)為(x0,y0)。則第二部分曲線初始決議參數(shù):p20=fellipse(x0+0.5,y0-1)=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2

21第二章第二節(jié)第21頁(yè)該橢圓第一分象限第2段橢圓曲線中點(diǎn)算法表示： p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2yk+1=yk-1xk+1=xk，p2k+1=p2k-2rx2yk+1+rx2,當(dāng)p2k>0xk+1=xk+1，p2k+1=p2k-rx2yk+1+rx2+2ry2xk+1當(dāng)p2k≤022第二章第二節(jié)第22頁(yè)決議參數(shù)增量=-2rx2yk+1+rx2當(dāng)p2k>0-2rx2yk+1+rx2+2ry2xk+1當(dāng)p2k≤0對(duì)于2rx2yk+1和2ry2xk+1本身又是一個(gè)增量表示式，2rx2yk+1增量一直為-2rx2，而2ry2xk+1增量為0(當(dāng)p2k>0)或2ry2(當(dāng)p2k≤0)，在起始位置(x0,y0)，2rx2yk+1和2ry2xk+1初始值分別為2rx2y0和2ry2x0。23第二章第二節(jié)第23頁(yè)中點(diǎn)橢圓算法步驟：1.輸入rx,ry和橢圓中心(xc,yc)，并得到中心在原點(diǎn)橢圓上第一個(gè)點(diǎn)。2.計(jì)算第一分象限第1段橢圓曲線決議參數(shù)初值：p10=ry2-rx2ry+rx2/43.在第1段曲線每個(gè)xk處，從k=0開始，完成以下測(cè)試：假如當(dāng)p1k<0，則下一個(gè)點(diǎn)為(xk+1,yk+1)=(xk+1,yk)，且：p1k+1=p1k+2ry2(xk+1)+ry2，不然，下一個(gè)點(diǎn)為(xk+1,yk+1)=(xk+1,yk-1)，且：p1k+1=p1k+2ry2(xk+1)+ry2-2rx2(yk-1)。且循環(huán)至2ry2x≥2rx2y，循環(huán)結(jié)束得到最終點(diǎn)(x0,y0)。24第二章第二節(jié)第24頁(yè)4.使用第1段曲線計(jì)算最終得到點(diǎn)(x0,y0)，來(lái)計(jì)算第2段曲線初始決議參數(shù)： p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry25.在第2段曲線每個(gè)yk處，從k=0開始，完成以下檢測(cè)：假如p2k>0，則下一個(gè)點(diǎn)為(xk+1,yk+1)=(xk,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2，不然下一個(gè)點(diǎn)為(xk+1,yk+1)=(xk+1,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2+2ry2(xk+1)，且循環(huán)至2rx2y=0即y=0。6.確定其它三個(gè)分象限中對(duì)稱點(diǎn)。7.將每個(gè)計(jì)算出像素位置(x,y)移到中心在(xc,yc)橢圓軌跡上，并按坐標(biāo)畫點(diǎn)：x=x+xc，y=y+yc。25第二章第二節(jié)第25頁(yè)中點(diǎn)橢圓算法C實(shí)現(xiàn)#defineROUND(