基本圖形生成算法

基本圖形生成算法第一頁(yè)，共六十四頁(yè)，2022年，8月28日一光柵掃描：

1光柵掃描的基本原理：電子束在熒光屏上按照固定的掃描線和掃描順序掃出一個(gè)由行和列組成的光的柵網(wǎng)。

2像素：柵網(wǎng)中的每一個(gè)孤立的光點(diǎn)，它是光柵顯示的最小單位。像素可以有不同的亮度,像素的坐標(biāo)值都是整數(shù)。

概論第二頁(yè)，共六十四頁(yè)，2022年，8月28日

3提出問(wèn)題(1)目前使用的圖形輸出設(shè)備顯示器：光柵圖形顯示器(2)光柵圖形顯示器:

以光柵掃描方式刷新線段、字符和圖形。其本質(zhì):是一種畫點(diǎn)設(shè)備，是由一定數(shù)量的網(wǎng)格狀細(xì)小光點(diǎn)（像素）組成，使其某些像素亮，某些像素不亮來(lái)顯示圖形或文字.(3)問(wèn)題：

光柵圖形顯示器是畫點(diǎn)設(shè)備，而二維圖形并不是點(diǎn)的集合，

如何在光柵圖形顯示器上構(gòu)造基本二維幾何圖形(線圓)？(4)解決方法：

進(jìn)行圖形掃描轉(zhuǎn)換

例：要在屏幕上顯示一條直線時(shí)，只能確定出逼近直線的一組像素，并按掃描線順序?qū)@些像素進(jìn)行寫操作，即進(jìn)行掃描轉(zhuǎn)換。

結(jié)果:使所畫的直線轉(zhuǎn)換成為逼近理想直線的由無(wú)數(shù)個(gè)點(diǎn)構(gòu)成的集合。

畫圖形：可使用同樣的方法，即進(jìn)行圖形的掃描轉(zhuǎn)換.

使所畫的圖形轉(zhuǎn)換成為逼近理想圖形的由無(wú)數(shù)個(gè)點(diǎn)構(gòu)成的集合。第三頁(yè)，共六十四頁(yè)，2022年，8月28日掃描轉(zhuǎn)換（光柵化）：

1什么叫掃描轉(zhuǎn)換（光柵化）？在光柵顯示器等數(shù)字設(shè)備上確定一個(gè)最佳逼近于圖形的象素集的過(guò)程。

2掃描轉(zhuǎn)換的主要工作：由于理想的圖形是連續(xù)的，而光柵圖像是離散的，因此顯示過(guò)程中不可避免地產(chǎn)生鋸齒等畸變，掃描轉(zhuǎn)換的主要工作就是研究使光柵圖像逼近原始的圖形的算法。用一系列的象素點(diǎn)來(lái)逼近直線第四頁(yè)，共六十四頁(yè)，2022年，8月28日

3學(xué)習(xí)掃描轉(zhuǎn)換的目的：

(1)繪圖函數(shù)具有局限性：

在實(shí)際工作中遇到畫線的工作時(shí)，可以方便地調(diào)用程序設(shè)計(jì)語(yǔ)言中提供的繪圖函數(shù)，不需要自己編寫畫線的程序。但它由局限性，不能滿足用戶特殊繪圖要求，需要開(kāi)發(fā)出滿足需求的繪圖程序。

(2)學(xué)習(xí)目的：掌握將數(shù)學(xué)的、模擬的、線形的圖形變成數(shù)字的離散的圖形的過(guò)程中的設(shè)計(jì)思想和方法，這些思想能夠在科學(xué)研究和產(chǎn)品開(kāi)發(fā)中發(fā)揮作用。第五頁(yè)，共六十四頁(yè)，2022年，8月28日5.1直線的生成三算法要求：

1準(zhǔn)確：掃描點(diǎn)盡可能地逼近理想點(diǎn)。

2快速：改進(jìn)算法盡快提高掃描轉(zhuǎn)換速度。一問(wèn)題的提出：

給定直線兩端點(diǎn)P0(x0,y0)和P1(x1,y1)，在光柵顯示器上畫出該直線。二需要進(jìn)行掃描轉(zhuǎn)換：給出一個(gè)將直線轉(zhuǎn)換為逼近理想直線的點(diǎn)的集合的算法。第六頁(yè)，共六十四頁(yè)，2022年，8月28日

2直線的斜截式方程：

y=kx+bb＝y(tǒng)1－kx1x從起點(diǎn)到終點(diǎn)每次增加1，用y=kx+b計(jì)算y值，再用putpixel(x,int(y+0.5),color)輸出該像素。

3該算法的缺點(diǎn)：畫線效率低，每步都需要一個(gè)浮點(diǎn)乘法運(yùn)算和一個(gè)四舍五入運(yùn)算，需要加以改進(jìn)。

5.2.數(shù)值微分法(DDA算法

DigitalDifferentialAnalyzer)

1直線的微分方程：一數(shù)值微分法：是一種基于直線微分方程來(lái)生成直線的方法。

第七頁(yè)，共六十四頁(yè)，2022年，8月28日二數(shù)值微分法的改進(jìn)算法（關(guān)鍵：找到Pi(Xi,Yi),Pi+1(Xi+1,Yi+1)的關(guān)系）

1推導(dǎo)：直線方程：y=kx+b

直線上的第i、第i+1……個(gè)點(diǎn)為：Pi(Xi,Yi),Pi+1(Xi+1,Yi+1),…

計(jì)算Pi+1時(shí)：x為xi+1,（在第1象限x總是向右前進(jìn)一步），

y為y （畫水平線時(shí)，y的值不變）

yi+1 （畫非水平線時(shí)，y的值變化，需要計(jì)算）其中：yi+1的計(jì)算為：

yi+1=kxi+1+B =k(xi+△x)+B=kxi+k△x+B =kxi+B+k△x //yi=kxi+B =yi+k△x =yi+k //當(dāng)△x的步進(jìn)為1時(shí)故Pi+1點(diǎn)的坐標(biāo)為：

xi+1=xi+1yi+1=round(yi+k) //進(jìn)行取整運(yùn)算第八頁(yè)，共六十四頁(yè)，2022年，8月28日分析：下一點(diǎn)的y坐標(biāo)為當(dāng)前點(diǎn)y坐標(biāo)加上斜率k,省略了浮點(diǎn)乘法。Pi+1點(diǎn)的坐標(biāo)為：

xi+1=xi+1yi+1=round(yi+k)

(xi,yi)

(xi+1,(int)(yi+k))

(xi,(int)(yi))

(xi+1,yi+k)數(shù)值微分法示意圖理想直線上的坐標(biāo)點(diǎn)掃描轉(zhuǎn)換后的像素點(diǎn)第九頁(yè)，共六十四頁(yè)，2022年，8月28日

2算法：

1)計(jì)算斜率k=△y/△x

2)畫第1個(gè)點(diǎn)(x0,y0)

3)計(jì)算下一個(gè)點(diǎn)（x，y）的值P，

x=x+1,y=y+k 小數(shù)部分≥0.5,則y=y+1循環(huán) 小數(shù)部分<0.5,則y=y

畫點(diǎn)（x，y）第十頁(yè)，共六十四頁(yè)，2022年，8月28日voidddaline(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx;floatdx,dy,k,y;dx=x1-x0;dy=y1-y0;k=dy/dx; //計(jì)算斜率

y=y0; //設(shè)定第1點(diǎn)的y值

for(x=x0;x<=x1;x++) //x加1{putpixel(x,(int)(y+0.5),color); //畫點(diǎn)，y值取整

y=y+k; //計(jì)算y的值

}}

3程序：

4分析：

本算法中k值需要使用浮點(diǎn)，每一步都要進(jìn)行取整運(yùn)算，不利于硬件實(shí)現(xiàn)?？梢杂弥悬c(diǎn)畫線法解決。第十一頁(yè)，共六十四頁(yè)，2022年，8月28日

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

中點(diǎn)畫線法示意圖3.2.2中點(diǎn)畫線法：1有直線F(x,y)=ax+by+c=0，假定其斜率在0，1之間.2直線在x方向增加一個(gè)單位，則在y方向上的增量只能在0與1之間。3當(dāng)前點(diǎn)為P（xp，yp）,下一點(diǎn)有兩種選擇:P1（xp+1,yp）或P2（xp+1,yp+1).4Q點(diǎn)是直線與垂直線x=xp+1的交點(diǎn)。M（xp+1，yp+0.5）為P1與P2的中點(diǎn)。若直線上的點(diǎn)Q在M的下方，說(shuō)明直線離P1近，則應(yīng)取P1為下一點(diǎn)。若直線上的點(diǎn)Q在M的上方，說(shuō)明直線離P2近，則應(yīng)取P2為下一點(diǎn)，

問(wèn)題：如何判斷Q在M的什么位置?

一原理:第十二頁(yè)，共六十四頁(yè)，2022年，8月28日二判別式推導(dǎo)：

1直線方程： F(x,y)=ax+by+c=0

直線上的點(diǎn)： F(x,y)=0

直線上方的點(diǎn)： F(x,y)>0

直線下方的點(diǎn)： F(x,y)<0

中點(diǎn)M的坐標(biāo)為：xp+1 yp+0.5

2欲判斷Q點(diǎn)在M的上方還是下方，將M帶入F(x,y)，判斷它的符號(hào)即可。判別式：dk=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c

dk>0

Q在M的下方（M在直線的上方）則：取P1作為下一個(gè)象素，

dk=dk

=0

Q在M的上（M在直線的上）則：同上

dk

<0Q在M的上方（M在直線的下方）則：取P2作為下一個(gè)象素，

對(duì)每一個(gè)象素計(jì)算判別式d，根據(jù)它的符號(hào)判定下一個(gè)象素。d是xp，yp的線形函數(shù)，可以采用增量計(jì)算來(lái)提高運(yùn)算效率。

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十三頁(yè)，共六十四頁(yè)，2022年，8月28日根據(jù)不同情況分析如下：第一種情況：當(dāng)dk≥0時(shí)，取正右方的象素p1，下一步則應(yīng)在p3和p4當(dāng)中選擇，設(shè)它們的中點(diǎn)為M1（xp+2，yp+0.5）,則判斷式d1為：

dk+1=F(M1)=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=axp+2a+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=dk+a下一步的判別式為：dk+1=dk+1+ad的增量為a。

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十四頁(yè)，共六十四頁(yè)，2022年，8月28日第二種情況：當(dāng)d<0時(shí)，取正上方的象素p2，下一步則應(yīng)在p4和p5當(dāng)中選擇，設(shè)它們的中點(diǎn)為M2（xp+2，yp+1.5）,則判斷式d2為：

dk+1=F(M2)=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=axp+2a+b(yp+1.5)+c=a(xp+1)+a+b(yp+0.5)+c+b=dk+a+b

下一步的判別式為：dk+1

=dk+a+bd的增量為a+b。

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十五頁(yè)，共六十四頁(yè)，2022年，8月28日初始值，第一個(gè)象素為起點(diǎn)（x0，y0），相應(yīng)的判別式值為M0，由于起點(diǎn)（x0，y0）在直線上，故F（x0，y0）=0。推導(dǎo)：d0=F(M0)=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+by0+c+a+0.5b=F(x0，y0)+a+0.5b//∵起點(diǎn)必在直線上，∴F(x0，y0)=0=a+0.5b

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十六頁(yè)，共六十四頁(yè)，2022年，8月28日小結(jié)：1）根據(jù)M選擇P1與P2之一：dk=a(xp+1)+b(yp+0.5)+c2）根據(jù)M1選擇P3與P4之一：dk+1=dk+a3）根據(jù)M2選擇P4與P5之一：dk+1=dk+a+b4)d的初始值為：d0=a+0.5b

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

三進(jìn)一步改進(jìn)算法：

注意到初始值中有浮點(diǎn)運(yùn)算，消除浮點(diǎn)可以進(jìn)一步改進(jìn)算法?？疾炫袆e式dk，判別使用的僅僅是dk的符號(hào)，且dk的增量都是整數(shù)，

故用2dk來(lái)代替dk，擺脫小數(shù)（浮點(diǎn)），從而提高速度。

第十七頁(yè)，共六十四頁(yè)，2022年，8月28日改進(jìn)結(jié)果：(中點(diǎn)畫線法的精髓）

d0=2a+b(a=y0-y1,b=x1-x0)dk+1=dk+2a（dk》0）此時(shí)取正右方像素

dk+2a+2b（dk<0）此時(shí)取右上方像素

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

學(xué)習(xí)目標(biāo)：1理解該算法的來(lái)龍去脈（上述結(jié)果是怎么得來(lái)的）。2能夠用上述結(jié)果解題，編程實(shí)現(xiàn)該算法。第十八頁(yè)，共六十四頁(yè)，2022年，8月28日四總結(jié)中點(diǎn)畫線算法：

1基本思想：通過(guò)判斷dk的值來(lái)確定下一個(gè)該點(diǎn)亮的像素

2思路：

(1)先求d0的值(利用中點(diǎn)M求）：d0=2a+b(2)再找到dk+1與dk的關(guān)系：

dk+1=dk+2a（dk》0）此時(shí)取正右方像素

dk+2a+2b（dk<0）此時(shí)取右上方像素

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十九頁(yè)，共六十四頁(yè)，2022年，8月28日五利用推導(dǎo)結(jié)果編程實(shí)現(xiàn)中點(diǎn)畫線算法：voidMidpointLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{inta,b,delta1,delta2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b; //d為d0，d=a+0.5b，2d=2a+b，D=2a+b,D=a+a+b delta1=2*a; //delta1為d1delta2=2*(a+b); //delta2為d2x=x0;y=y0;putpixel(x,y,color);while(x<x1){if(d<0){x++;y++;d+=delta2;

}else{x++;d+=delta1;}putpixel(x,y,color);} //while} //MidpointLine

第二十頁(yè)，共六十四頁(yè)，2022年，8月28日課后作業(yè)題：用中點(diǎn)畫線算法掃描轉(zhuǎn)換從像素點(diǎn)(1,1)到(8,5)線段的像素位置第二十一頁(yè)，共六十四頁(yè)，2022年，8月28日3改進(jìn)的Bresenham算法假定直線段的0≤k≤1基本原理：第二十二頁(yè)，共六十四頁(yè)，2022年，8月28日誤差項(xiàng)的計(jì)算d初=0，每走一步：d=d+k一旦y方向上走了一步，d=d-1第二十三頁(yè)，共六十四頁(yè)，2022年，8月28日算法步驟：1.輸入直線的兩端點(diǎn)P0(x0,y0)和P1(x1,y1)。2.計(jì)算初始值△x、△y、d=0、x=x0、y=y0。3.繪制點(diǎn)(x,y)。4.d更新為d+k，判斷d的符號(hào)。若d>0.5，則(x,y)更新為(x+1,y+1)，同時(shí)將d更新為d-1；否則(x,y)更新為(x+1,y)。5.當(dāng)直線沒(méi)有畫完時(shí)，重復(fù)步驟3和4。否則結(jié)束。第二十四頁(yè)，共六十四頁(yè)，2022年，8月28日改進(jìn)1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e>0)thene=e-1第二十五頁(yè)，共六十四頁(yè)，2022年，8月28日算法步驟為：1.輸入直線的兩端點(diǎn)P0(x0,y0)和P1(x1,y1)。2.計(jì)算初始值△x、△y、e=-0.5、x=x0、y=y0。3.繪制點(diǎn)(x,y)。4.e更新為e+k，判斷e的符號(hào)。若e>0，則(x,y)更新為(x+1,y+1)，同時(shí)將e更新為e-1；否則(x,y)更新為(x+1,y)。5.當(dāng)直線沒(méi)有畫完時(shí)，重復(fù)步驟3和4。否則結(jié)束。第二十六頁(yè)，共六十四頁(yè)，2022年，8月28日改進(jìn)2：用2e△x來(lái)替換ee初=-△x，每走一步有e=e+2△y。if(e>0)thene=e-2△x第二十七頁(yè)，共六十四頁(yè)，2022年，8月28日1/27/202327算法步驟：1.輸入直線的兩端點(diǎn)P0(x0,y0)和P1(x1,y1)。2.計(jì)算初始值△x、△y、e=-△x、x=x0、y=y0。3.繪制點(diǎn)(x,y)。4.e更新為e+2△y，判斷e的符號(hào)。若e>0，則(x,y)更新為(x+1,y+1)，同時(shí)將e更新為e-2△x；否則(x,y)更新為(x+1,y)。5.當(dāng)直線沒(méi)有畫完時(shí)，重復(fù)步驟3和4。否則結(jié)束。第二十八頁(yè)，共六十四頁(yè)，2022年，8月28日三利用推導(dǎo)結(jié)果編程實(shí)現(xiàn)bresenham算法：voidbresenhamline(intx0,inty0,intx1,inty1){intx,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;

while(x<=x1){ putpixel(x,y); x=x+1;

e=e+2*dy;

if(e>0){y=y+1;e=e-2*dx;}}}第二十九頁(yè)，共六十四頁(yè)，2022年，8月28日五中點(diǎn)畫線算法與bresenham算法的比較：

相似處：1求出d0的值2再找到dk+1與dk的關(guān)系.3利用dk的值判斷下一個(gè)該點(diǎn)亮的像素：不同點(diǎn)：1求d0時(shí)：中點(diǎn)畫線法：利用中點(diǎn)M坐標(biāo)來(lái)求，d0＝2a＋bbresenham法：利用始點(diǎn)終點(diǎn)來(lái)求，d0＝2△y-△x2利用dk的值取像素時(shí)：

bresenham法：dk》0時(shí)取右上方像素

dk<0時(shí)取右方像素中點(diǎn)法正相反：dk》0時(shí)取右方像素

dk<0時(shí)取右上方像素第三十頁(yè)，共六十四頁(yè)，2022年，8月28日課后作業(yè)題：用bresenham算法掃描轉(zhuǎn)換從像素點(diǎn)(1,1)到(8,5)線段的像素位置。第三十一頁(yè)，共六十四頁(yè)，2022年，8月28日3.3圓的生成3.3.1八分法畫圓算法思路：（考慮到圓的對(duì)稱性）畫出A點(diǎn)則剩下的7個(gè)點(diǎn)都能畫出，畫出B點(diǎn)則剩下的7個(gè)點(diǎn)都能畫出，因此，只討論8分圓的畫法即可A(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)B第三十二頁(yè)，共六十四頁(yè)，2022年，8月28日二算法原理：利用其函數(shù)方程，直接離散計(jì)算圓的函數(shù)方程為：缺點(diǎn)：計(jì)算量過(guò)大第三十三頁(yè)，共六十四頁(yè)，2022年，8月28日三圓的極坐標(biāo)方程為：第三十四頁(yè)，共六十四頁(yè)，2022年，8月28日可先通過(guò)平移變換，把計(jì)算所得的像素(x1,y1)坐標(biāo)加上一個(gè)位移量(delta_x和delta_y)即得所求像素坐標(biāo)(x2,y2)。即：

x2=x1+delta_xy2=y1+delta_y四中點(diǎn)不在原點(diǎn)的圓：第三十五頁(yè)，共六十四頁(yè)，2022年，8月28日3.3.2中點(diǎn)畫圓算法（關(guān)鍵：找到d的增量）一基本思路：利用中點(diǎn)M來(lái)選擇下一個(gè)要顯示的像素。二分析：

M的坐標(biāo)是（x+1,y-0.5）

F(M)>0點(diǎn)M在圓的外邊,圓離P2點(diǎn)近,取P2F(M)=0點(diǎn)M在圓的上邊,取P2F(M)<0點(diǎn)M在圓的里邊,圓離P1點(diǎn)近,取P1

問(wèn)題：下一次取P3？P4？P5？

M1P1P2M2M3P3P4P5第三十六頁(yè)，共六十四頁(yè)，2022年，8月28日1

構(gòu)造判別式：若d<0點(diǎn)M在圓的里邊，圓離P1點(diǎn)近,則應(yīng)取P1

下一個(gè)中點(diǎn)M2的判別式為：

d=F(xp+2,yp-0.5) =(xp+2)2+(yp-0.5)2-R2 =d+2xp+3

即求出d的增量為：2xp+3若d≥0點(diǎn)M在圓的外邊,圓離P2點(diǎn)近,則應(yīng)取P2

下一個(gè)中點(diǎn)M3的判別式為：

d=F(xp+2,yp-1.5) =(xp+2)2+(yp-1.5)2-R2 =d+2(xp-yp)+5

即求出d的增量為：2(xp-yp)+5總結(jié)求得的d的增量：2xp+3d<02(xp-yp)+5d≥0

2求d的增量：（目的：判斷下一個(gè)該顯示的像素）解決方法：M1P1P2M2M3P3P4P5p第三十七頁(yè)，共六十四頁(yè)，2022年，8月28日3求d的初始值d0：

起始點(diǎn)（即第一個(gè)像素)為（0,R）,

判別式d的初始值為：

d0=F(1,R-0.5) =1+(R-0.5)2-R2 =1.25-R4推導(dǎo)出的結(jié)果:d0＝1.25-R

d+2xp+3d<0d+2(xp-yp)+5d≥0

M1P1P2M2M3P3P4P5d=

5可以利用推導(dǎo)出的結(jié)果，編寫程序。第三十八頁(yè)，共六十四頁(yè)，2022年，8月28日三算法步驟：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)。若d≤0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)x<y時(shí)，重復(fù)步驟3和4。否則結(jié)束。第三十九頁(yè)，共六十四頁(yè)，2022年，8月28日改進(jìn)：用d-0.25代替d算法步驟：1.輸入圓的半徑R。2.計(jì)算初始值d=1-R、x=0、y=R。3.繪制點(diǎn)(x,y)及其在八分圓中的另外七個(gè)對(duì)稱點(diǎn)。4.判斷d的符號(hào)。若d≤0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)x<y時(shí)，重復(fù)步驟3和4。否則結(jié)束。第四十頁(yè)，共六十四頁(yè)，2022年，8月28日四源程序：voidMidpointCircle(r,color)intr,color;{intx,y,d;x=0;y=r;d=1-r;wholecircle(x,y,color);

while(x<y){if(d<0) {d+=2*x+3;x++;}else {d+=2*(x-y)+5; x++;y--;}wholecircle(x,y,color);}}voidWholeCircle(xc,yc,x,y.color)intxc,yc,x,y,color;{putpixel(xc+x,yc+y,color);putpixel(xc-x,yc+y,color);putpixel(xc+x,yc-y,color);putpixel(xc-x,yc-y,color);putpixel(xc+y,yc+x,color);putpixel(xc-y,yc+x,color);putpixel(xc+y,yc-x,color);putpixel(xc-y,yc-x,color);}第四十一頁(yè)，共六十四頁(yè)，2022年，8月28日3.4區(qū)域填充:

區(qū)域填充研究如何用一種顏色或一個(gè)圖案來(lái)充滿一個(gè)二維區(qū)域。

一區(qū)域：一組具有相同的屬性相鄰又相連的象素。二區(qū)域填充：根據(jù)邊或頂點(diǎn)的簡(jiǎn)單描述生成區(qū)域的過(guò)程叫作區(qū)域填充。三區(qū)域填充要做的兩個(gè)工作：

1在什么地方填充，2填充什么內(nèi)容。四區(qū)域填充算法分為兩大類：

1.掃描轉(zhuǎn)換填充算法：按掃描線的順序確定。

2.種子填充算法：假設(shè)在多邊形或區(qū)域的內(nèi)部，至少有一個(gè)象素是已知的，然后設(shè)法找到區(qū)域內(nèi)所有其它象素，并對(duì)它們進(jìn)行填充。

第四十二頁(yè)，共六十四頁(yè)，2022年，8月28日3.4.1種子填充算法一種子填充算法的原理：假設(shè)在多邊形區(qū)域內(nèi)部有一像素已知，由此出發(fā)找到區(qū)域內(nèi)的所有像素。假設(shè)區(qū)域采用邊界定義，即區(qū)域邊界上所有像素均具有某個(gè)特定值，區(qū)域內(nèi)部所有象素均不取這一特定值，而邊界外的像素則可具有與邊界相同的值。第四十三頁(yè)，共六十四頁(yè)，2022年，8月28日

從區(qū)域上一點(diǎn)出發(fā)，可通過(guò)四個(gè)方向，即上、下、左、右移動(dòng)的組合，在不越出區(qū)域的前提下，到達(dá)區(qū)域內(nèi)的任意像素。圖(a)所示的區(qū)域是四連通區(qū)域。

特點(diǎn)：區(qū)域內(nèi)像素由四向連接，而區(qū)域的邊界卻是八連通式的。二幾個(gè)概念：區(qū)域分兩種：四向連通區(qū)域和八向連通區(qū)域1四向連通區(qū)域：第四十四頁(yè)，共六十四頁(yè)，2022年，8月28日區(qū)域內(nèi)每—個(gè)象素，可以通過(guò)左、右、上、下、左上、右上、左下、右下這八個(gè)方向的移動(dòng)的組合來(lái)到達(dá)區(qū)域內(nèi)的任意象素。圖(b)所示的區(qū)域是八連通區(qū)域。

特點(diǎn)：區(qū)域內(nèi)象素由八向連接。如兩個(gè)矩形的連接處為右上連接。但是區(qū)域的邊界是四連通式的。

八向連通區(qū)域：第四十五頁(yè)，共六十四頁(yè)，2022年，8月28日允許從四個(gè)方向?qū)ふ蚁乱幌笏?，稱為四向算法；允許從八個(gè)方向?qū)ふ蚁乱幌笏兀Q為八向算法。八向算法可以填充八向連通區(qū)域，也可以填充四向連通區(qū)域。四向算法只能填充四向連通區(qū)域，而不能填充八向填充區(qū)域。如果圖(b)中的區(qū)域是兩個(gè)分離的區(qū)域，并且每個(gè)區(qū)域需填成不同的顏色，那么，用八向算法會(huì)使兩個(gè)區(qū)域被錯(cuò)誤地填上同一顏色。3四向算法和八向算法：第四十六頁(yè)，共六十四頁(yè)，2022年，8月28日1問(wèn)題點(diǎn)：采用什么數(shù)據(jù)結(jié)構(gòu)？

(1)聯(lián)想迷宮求解問(wèn)題：

相似處：迷宮圖中的每一個(gè)方塊象一個(gè)像素，所有的通道塊象要填充的區(qū)域。不同處：求解迷宮路徑：不是所有的通道塊都被選中區(qū)域填充：與種子像素特性相同的不超過(guò)邊界的所有像素都被選中。本質(zhì)：屬于后進(jìn)先出問(wèn)題。

(2)四向算法采用的數(shù)據(jù)結(jié)構(gòu)：棧結(jié)構(gòu)

四向算法：第四十七頁(yè)，共六十四頁(yè)，2022年，8月28日2四向算法原理：種子像素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：

(1)棧頂像素出棧

(2)將出棧像素置成多邊形色

(3)按右上左下方向逆時(shí)針旋轉(zhuǎn)，順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界而且未置成多邊形色則把該像素入棧。第四十八頁(yè)，共六十四頁(yè)，2022年，8月28日有一個(gè)用邊界表示的區(qū)域，用種子填充算法對(duì)該區(qū)域進(jìn)行填充。

3

8

24

7

9

24

7

9

1

4

3

84

7

9

5

6

4

84

7

9

5

6

84

7

9

7

6

84

7

9

7

84

7

9

8

4

7

9

4

7

9

7

9

9

堆棧中的數(shù)據(jù)：紅色代表出棧數(shù)據(jù)，灰色代表?xiàng)ｍ?/p>

1號(hào)出棧填充,按右上左下順序?qū)ふ椅刺畛湎笏亍?/p>

2號(hào)出棧填充,按右上左下順序找到8，3。

3號(hào)出棧填充,按右上左下順序找到4。

4號(hào)出棧填充,按右上左下順序找到6，5。

5號(hào)出棧填充,6為棧頂。

6號(hào)出棧填充,按右上左下順序找到7。

7號(hào)出棧填充,8為棧頂。

8號(hào)出棧填充,4為棧頂.4號(hào)出棧填充,7為棧頂(4號(hào)重復(fù)填充)7號(hào)出棧填充,9為棧頂(7號(hào)重復(fù)填充)

9號(hào)出棧填充,?？眨Y(jié)束。第四十九頁(yè)，共六十四頁(yè)，2022年，8月28日

3四向算法的缺點(diǎn)：

1把太多的象素壓入堆棧，有些象素甚至?xí)霔６啻?，降低了算法的效率?/p>

2要求很大的存儲(chǔ)空間以實(shí)現(xiàn)棧結(jié)構(gòu).4解決辦法：在任意一個(gè)掃描線與多邊形的相交區(qū)間中，只取一個(gè)種子象素。通過(guò)沿掃描線填充水平象素段，來(lái)代替處理4-鄰接點(diǎn)和8-鄰接點(diǎn)。第五十頁(yè)，共六十四頁(yè)，2022年，8月28日3.4.2掃描線填充算法算法原理：種子象素入棧；當(dāng)棧非空時(shí)作如下四步操作：

1棧頂象素出棧；

2沿掃描線對(duì)出棧象素的左右象素進(jìn)行填充，直至遇到邊界象素為止，即每出棧一個(gè)象素，就對(duì)包含該象素的整個(gè)區(qū)間進(jìn)行填充；

3上述區(qū)間內(nèi)最左、最右的象素分別記為xl，xr（x_left,x_right）;4在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線相鄰的上下兩條掃描線的有關(guān)象素是否全為邊界象素或已填充的象素，若存在非邊界、末填充的象素，則把每一區(qū)間的最右象素取作種子象素入棧。第五十一頁(yè)，共六十四頁(yè)，2022年，8月28日二掃描線填充算法舉例：

要求：用紅色象素●填充，以◆為邊界的藝術(shù)A字。1．種子位置為●，填充一行（紅），檢查上下兩行中未填充區(qū)域，將最右的一個(gè)象素壓入堆棧中，堆棧中為1，2，3，棧頂為3，故下一步填充3號(hào)行。

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆

3◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

◆

◆

◆◆◆◆◆

◆◆◆◆第五十二頁(yè)，共六十四頁(yè)，2022年，8月28日2．填充一行（綠），檢查上下兩行中未填充區(qū)域，將最右的一個(gè)象素壓入堆棧中，堆棧中為1，2，3，4，下一步處理4號(hào)的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆

4◆◆◆◆

3◆◆

◆

◆

◆◆

◆

◆

◆◆◆◆◆

◆◆◆◆

第五十三頁(yè)，共六十四頁(yè)，2022年，8月28日3填充一行（綠），堆棧為1，2，3，新4，下一步處理新4號(hào)的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆●●◆◆◆◆

3◆◆

4◆

◆

◆◆

◆

◆

◆◆◆◆◆

◆◆◆◆第五十四頁(yè)，共六十四頁(yè)，2022年，8月28日4．填充了兩行（蘭色），堆棧為1，2，3，下一步處理3號(hào)的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆●●◆◆◆◆

3◆◆●●◆

◆

◆◆●●◆

◆

◆◆◆◆◆

◆◆◆◆第五十五頁(yè)，共六十四頁(yè)，2022年，8月28日5．填充了三行（綠色），堆棧為1，2，下一步處理2號(hào)的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆●●◆◆◆◆●●◆◆●●◆

◆●●◆◆●●◆

◆●●◆◆◆◆◆

◆◆◆◆

第五十六頁(yè)，共六十四頁(yè)，2022年，8月28日6．填充了三行（綠色），堆棧為1，2，下一步處理2號(hào)的行

◆◆◆◆◆◆

◆

◆

◆

2◆◆●●◆◆◆◆

◆