lesson04圓與橢圓的生成算法市公開課特等獎市賽課微課一等獎課件

lessonfour2.2

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

假如我們結構函數(shù)

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

d<0，則應取P1為下一象素，而且再下一象素判別式為：d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3若d≥0，則應取P2為下一象素，而且下一象素判別式為d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2(xp-yp)+5我們這里討論第一個象素是（0,R），判別式d初始值為：d0=F(1,R-0.5)=1.25-R4第二章第二節(jié)第4頁中點畫圓算法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頁Bresenham圓算法Bresenham圓算法基本思想是尋找最靠近于實際圓周上點?，F(xiàn)僅討論八分之一圓周，

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

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

對于Pi-1下一點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(Si)|≥|D(Ti)|，則Ti更靠近于圓周，選擇Ti

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

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

則

di≥0，取Ti

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

設x0=0，y0=R，

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

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

設Pi-1為(xi-1,yi-1)，則取下一點

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]

假設di＜0，則取Si作為下一點，

即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頁圓生成算法改進假設di≥0，則取Ti作為下一點，

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

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

當di＜0時，取Si(xi-1+1,yi)

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

begin

輸出點(x,y)以及其它7點(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輸出點(x,y)以及(-x,y),(-x,-y),(x,-y)endofalgorithm10第二章第二節(jié)第10頁2、橢圓特征橢圓被定義為到兩個定點(焦點)距離之和等于常數(shù)點集合。橢圓上任意點p(x,y)到兩個焦點距離記為d1和d2，那么，橢圓方程可表示為：d1+d2=常數(shù)設兩個焦點坐標F1=(x1,y1)和F2=(x2,y2)來表示橢圓方程： [(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頁標準位置橢圓：長軸和短軸與X和Y軸平行，橢圓中心可在(xc,yc)。標準位置橢圓方程： [(x-xc)/rx]2+[(y-yc)/ry]2=1 其中：rx和ry分別為長半軸和短半軸。極坐標表示： x=xc+rxcosθ,y=yc+rysinθ標準位置橢圓其在四分象限是對稱，所以我們只需要計算一個四分象限橢圓曲線位置，然后依據(jù)對稱性得到其余部分。12第二章第二節(jié)第12頁3.5.2中點橢圓算法首先計算橢圓中心在(0,0)標準位置橢圓曲線第一分象限曲線部分位置像素(x,y)，然后將點變換到橢圓中心在(xc,yc)。依據(jù)前面DDA算法討論，當|m|≤1時，取x方向單位步長(1或-1)，相反，取y方向單位步長(1或-1)。所以，對于第一分象限橢圓曲線分成兩部分：一部分曲線斜率絕對值小于1和斜率絕對值大于1。并分別對兩段曲線分別取x方向步長和y方向取步長.13第二章第二節(jié)第13頁這里可選擇(0,ry)或(rx,0)作為起點開始算法。以從(0,ry)開始從左到右進行。橢圓函數(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)作為中點橢圓算法決議參數(shù)。在每個取樣位置，按照橢圓函數(shù)在沿橢圓軌跡兩個候選像素點中點求值符號選擇下一個像素

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

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

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

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