版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領
文檔簡介
第3章基本光柵圖形算法本章內(nèi)容3.1用Java語言繪圖13.2直線的掃描轉(zhuǎn)換23.3圓的掃描轉(zhuǎn)換33.4多邊形的掃描轉(zhuǎn)換43.5區(qū)域填充53.6字符的生成63.7光柵圖形的反走樣算法73.1用Java語言繪圖3.1.1用Java小程序繪圖關(guān)鍵方法init()
——由瀏覽器或applet瀏覽器來調(diào)用，通知小程序即將被裝入系統(tǒng)，即初始化。繪圖函數(shù)
——paint(Graphics)：繪制構(gòu)件，當調(diào)整小程序瀏覽窗口大小，縮放瀏覽窗口，移動窗口或重載等需要重繪窗口時都會調(diào)用該方法。 ——update()：刷新屏幕，并調(diào)用paint()方法。 ——repaint()：調(diào)用update()方法。簡單的繪圖操作
Graphics.drawLine(int
startX,int
startY,int
endX,int
endY)：畫一條起點為(startX,startY)，終點為(endX,endY)的直線段。
Graphics.clearRect(int
x,int
y,int
width,intheight)：將左上角為(x,y)，寬為width，高為height的區(qū)域用背景色填充。
Graphics.setColor(Color)：設置當前的繪圖顏色
Graphics.getColor()：返回當前的繪圖顏色
setBackground(Color)和setForeground(Color)：設置諸如面板和框架等組件的背景色
getBackground（）和getForeground（）：獲得當前組件的顏色3.1.1用Java小程序繪圖創(chuàng)建Color對象的構(gòu)造函數(shù)
——Color（int，int，int） 使用三個表示所需顏色的RGB值的整數(shù)值。 ——Color（float，float，float） 使用三個表示所需顏色的RGB值的浮點數(shù)值。3.1.1用Java小程序繪圖black(0,0,0)gray(128,128,128)red(255,0,0)blue(0,0,255)green(0,255,0)white(255,255,255)cyan(0,255,255)lightGray(255,200,0)yellow(255,255,0)darkGray(64,64,64)magenta(255,0,255)Color類中的標準顏色表importjava.awt.*;//引入圖形軟件包awtimportjava.applet.Applet;//使用java.applet.Applet類publicclasslineextendsApplet{int
startX,startY,endX,endY;Colorcolor;publicvoidinit()//初始化
{ startX=50;//設置直線的起點和終點位置
startY=50;
endX=100;
endY=150; color=Color.blue;//初始化顏色為藍色
} 3.1.1用Java小程序繪圖例：畫一條起點為（50，50），終點為（150，150）的直線。publicvoidpaint(Graphicsg){g.setColor(color);//設置顏色
drawLine(g,startX,startY,endX,endY);//調(diào)用繪制直線的函數(shù)
}voiddrawLine(Graphics
g,intx1,inty1,intx2,inty2)//繪制直線的函數(shù)
{ g.drawLine(x1,y1,x2,y2);//畫一條起點為（x1,y1）終點為（x2,y2）的直線
}}3.1.1用Java小程序繪圖將以上代碼保存為名為line.java的文件，該文件編譯生成名為line.class的類文件。該類文件必須嵌入到Web頁中才可運行。通過下面的代碼將line.class的類文件放到Web頁中：<HTML><appletcode="line.class"width=500height=400></applet></HTML>將代碼保存為名為line的html文件。該文件可用Java自帶的appletviewer瀏覽器運行，也可直接在瀏覽器中運行l(wèi)ine.htm。3.1.1用Java小程序繪圖3.1.2用Java應用程序繪圖應用程序（application）能獨立運行,由一個或多個類構(gòu)成。其中包含main（）函數(shù)的類為程序的入口類。Java應用程序中，可把圖形繪制在面板中，然后將該面板加入到窗口程序中顯示圖形。面板是繼承JPanel類而來，其中與繪圖相關(guān)的是paintComponent(Graphics)函數(shù)?？赏ㄟ^覆蓋面板的paintComponent()函數(shù)，將所有的圖形操作代碼放在該函數(shù)中實現(xiàn)圖形的繪制。窗口是繼承JFrame類而來，其中的show（）函數(shù)使整個窗口可見。3.1.2用Java應用程序繪圖例：畫一條起點為（50，50），終點為（150，150）的直線。importjavax.swing.*;//引入swing包importjava.awt.*;//引入圖形軟件包awtclassSetPixelextendsJPanel{Colorcolor;
int
startX,startY,endX,endY;publicSetPixel()//構(gòu)造函數(shù)（初始化）
{color=Color.blue;//藍色
startX=50;//設置直線的起點和終點位置
startY=50;先用下面的SetPixel類將生成一個面板，并在上面畫一條起點為（50，50），終點為（150，150）的直線，直線的顏色為藍色。
endX=150;
endY=150;} publicvoidpaintComponent(Graphicsg){ g.setColor(color);//設置顏色
drawLine(g,startX,startY,endX,endY);//調(diào)用繪制直線的函數(shù)
}voiddrawLine(Graphics
g,intx1,inty1,intx2,inty2)//繪制直線的函數(shù)
{g.drawLine(x1,y1,x2,y2);//畫一條起點為(x1,y1)終點為(x2,y2)的直線
}}3.1.2用Java應用程序繪圖3.1.2用Java應用程序繪圖publicclassPixelWindowextendsJFrame{publicPixelWindow(){super("PixelColor"); //設置窗口標題
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
//設置窗口關(guān)閉模式
setBounds(newRectangle(100,100,300,300));
//設置窗口在屏幕上的顯示位置和大小
SetPixelset=newSetPixel();//生成SetPixel類對象（一個面板對象）
add(set);//將面板加入到窗口中
} publicstaticvoidmain(String[]args){PixelWindow
setPixel=newPixelWindow();//生成PixelWindow對象
setPixel.show();//設置JFrame窗口可見
}}再用PixelWindow類生成運行窗口顯示SetPixel類對象，主函數(shù)在此類中。3.2直線的掃描轉(zhuǎn)換對直線進行光柵化時，只能在顯示器所給定的有限個像素組成的點陣中，選擇能最好地逼近于該直線的一組像素，并對這些像素進行寫操作。這就是通常所說的用顯示器繪制直線，即直線的掃描轉(zhuǎn)換。直線掃描轉(zhuǎn)換的主要工作：快速找出像素點陣中距直線最近的網(wǎng)格點，用這些網(wǎng)格點對應的像素表示該直線。數(shù)學上的理想直線沒有寬度，是由無數(shù)個點構(gòu)成的集合。3.2直線的掃描轉(zhuǎn)換像素和坐標的對應關(guān)系(a)(b)3.2.1基本增量算法基本思想設直線滿足，由于直線的斜率小于等于1，所以，該直線的掃描轉(zhuǎn)換可從最左端開始，每次遞增一個單位，對每個，相應的有，則所以，每增加一個單位，只需加上一個，這樣就去掉了乘法運算，提高了算法效率。在該算法中，直線上的所有點的和值可由前一點的值加一個基本增量得到，所以該算法稱為基本增量算法。3.2.1基本增量算法注：上述討論只適合的情況，當時，只需將和的角色互換，即每次增加一個單位，每次增加?；驹隽克惴ㄒ步袛?shù)字微分分析器算法（DigitalDifferentialAnalyzer，DDA）。DDA是用數(shù)值方法求解微分方程的一種設備，即根據(jù)和的一階導數(shù)，在和方向上漸進地以小步長移動，由此產(chǎn)生連續(xù)的像素坐標。3.2.1基本增量算法參數(shù)直線段的情況
設起點和終點坐標分別為（，）和（，），令， ,則直線的參數(shù)方程是–
令，將參數(shù)區(qū)間[0，1]分為等份，即每次的增量為。3.2.1基本增量算法第步時于是有(3.1)(3.2)公式（3.2）是一個迭代公式，第步的坐標是由第步的結(jié)果加上一個增量得到。該算法在或變化比較大的方向增量為,而另一方向上的增量的絕對值小于等于1。3.2.1基本增量算法下圖中，用公式（3.2）求得的直線上的點用空心圓表示，但顯示時要用像素來表示，即采用舍入的辦法得到最靠近空心圓點的像素，用這些像素（下圖中的實心圓點）來表示直線。圖中實心圓點表示用DDA方法生成的直線3.2.1基本增量算法DDA算法的程序?qū)崿F(xiàn)voiddda(Graphicsg,intx1,intx2,inty1,inty2){intk;floatx,y,dx,dy;k=Math.abs(x2-x1);if(Math.abs(y2-y1)>k)k=Math.abs(y2-y1);
dx=(float)(x2-x1)/k;
dy=(float)(y2-y1)/k;x=(float)x1;y=(float)y1;for(inti=0;i<k;i++){g.drawLine((int)(x+.5f),(int)(y+.5f),(int)(x+.5f),(int)(y+.5f)); x=x+dx; y=y+dy;}}3.2.1基本增量算法實例設給定直線的起點坐標為(0，0)，終點坐標為(9，6)，則上述DDA算法畫出的直線如下圖所示。DDA方法所畫直線圖DDA算法缺點：需要進行浮點數(shù)運算，產(chǎn)生一個像素要做兩次加法和兩次取整運算，運行效率低且取整運算不利于硬件實現(xiàn)。3.2.2Bresenham算法基本思想設直線的起點坐標為，斜率為。下面就的情況來說明該算法。取為像素所在點的橫坐標（整數(shù)），令，直線上相鄰兩點的坐標滿足關(guān)系(3.3)一般來說，不一定是整數(shù)，所以也不一定是整數(shù)，因此要用靠近該點最近的網(wǎng)格點來近似。由于取整計算量較大，為了提高效率，Bresenham算法用下面的方法來避免使用取整運算。3.2.2Bresenham算法設圖3.4中已得到第個顯示的點，B點是直線與第列網(wǎng)格線的交點，則第個顯示的點只能從C或D點中去選。設A為CD邊的中點，令誤差項(3.4)當B在A的下面時，，此時應取C點作為；當B在A的上面時，，則應取D點作為。BACD圖3.4的幾何意義3.2.2Bresenham算法通過遞推的方式，高效地計算點序列和，由圖3.4可得
(3.5)由式（3.3）～（3.5）可得=(3.6)注：3.2.2Bresenham算法式（3.5）和（3.6）是根據(jù)圖3.4所示的情況推出的，容易驗證，式（3.5）和（3.6）對圖3.5所示的兩種情況也成立。CBADBACD圖3.5的幾何意義的其他兩種情況3.2.2Bresenham算法算法的程序?qū)崿F(xiàn)由式（3.3）和（3.4）可得假設直線段起始點的坐標分量和均為整數(shù)，則有m=(double)dy/(double)dx；e=m–0.5；for(i=0;i<dx;i++){
g.drawLine(x,y,x,y);
if(e>=0){y=y+1；e=e–1;}x=x+1；e=e+m;}該算法在計算直線斜率和誤差項時用到了小數(shù)與除法，可改用整數(shù)來避免除法，以提高算法的效率和減少算法的復雜性。由于算法中只用到誤差項的符號，因此可進行如下替換：。改進后的算法程序3.2.2Bresenham算法voidbresenham(Graphicsg,int
xs,int
ys,int
xe,intye) {int
dx=xe-xs;
int
dy=ye-ys;
inte=2*dy-dx;
intx=xs;
inty=ys;
for(inti=0;i<dx;i++){
g.drawLine(x,y,x,y);//畫點（x,y）
if(e>=0){y=y+1;e=e-2*dx;}x=x+1;e=e+2*dy;} }3.3圓的掃描轉(zhuǎn)換3.3.1正負法基本思想設圓的半徑為R，則圓的方程為對于圓上的點，；對于圓內(nèi)的點，；對于圓外的點，。以順時針繪制左圖中第一象限內(nèi)四分之一圓弧AB為例說明該方法。假定圓心和起點均精確地落在像素上。設起點A為，則有。(0,0)ABPiPi+1Pi-1弧AB上點的取法3.3.1正負法確定當前點后，可通過的值來決定下一個點：若，說明點在圓內(nèi)，則下一步應向圓外走，即取若，說明點在圓外，則下一步應向圓內(nèi)走，即取若，說明點在圓上，則下一步可以向圓內(nèi)走，也可以向圓外走，這里規(guī)定取。這樣用于表示圓弧的點均在理想圓弧附近且時正時負，因此稱為正負法。由于這種方法每走完一步，都要比較當前位置的函數(shù)值，以決定下一步的走向，因而也稱為逐點比較法。3.3.1正負法的遞推公式。由上可知。如果的值已算出，計算時可分為兩種情況：當時，(3.9)當時，(3.10)由式（3.9）和式(3.10)知，3.3.1正負法算法的程序?qū)崿F(xiàn)voidpnarc(Graphics
g,intradius){int
x,y,f;x=0;y=0+radius;f=0;while(y>0){
g.drawLine(x,y,x,y); if(f>0){ f=f-2*y+1; y--; }else{ f=f+2*x+1;x++; }}
if(y==0)g.drawLine(x,y,x,y);}3.3.2Bresenham算法xy45°AB(-x,-y)(-y,-x)(-x,y)(x,y)(x,-y)(-y,x)(y,x)(y,-x)圖3.87個對稱點圖3.9Pi-1的兩個侯選點xHiLiPi-1yD(Hi)>0D(Li)<0AB僅討論圖3.8中弧AB的畫法，而要顯示一個整圓，只需在顯示AB上任一點的同時顯示圓上該點的其它七個對稱點即可。從A點開始向右下方逐點尋找顯示弧AB要用的點，若圖3.9中的點是已選中的一個表示圓弧上的點，則下一個點應為 或，選還是選取決于哪一個點更接近于弧AB。3.3.2Bresenham算法設R為弧AB的半徑，記點P到原點的距離的平方與圓的半徑的平方之差為D(P)，即
假定為圓弧上的點，則，。令當時，，比距圓弧近，應取來顯示弧AB
；當時，，應取來顯示弧AB
；當時，可在兩者中任取一點，這里規(guī)定取。Bresenham算法在候選的兩個像素中，總是選離圓弧最近的像素為圓弧的一個近似點，因此，它比正負法決定的像素更合理。3.3.2Bresenham算法設點坐標為，則和點的坐標分別為和,和的坐標分別為和。已知，，，。則(3.12)(3.13)(3.14)的遞推公式3.3.2Bresenham算法當時，點被選中，這時，由式（3.13）和（3.14）可得當時，點被選中，這時，由式（3.13）和（3.14）可得(3.15)(3.16)式（3.12），（3.15）和（3.16）組成計算的遞推公式。3.3.2Bresenham算法算法的程序?qū)崿F(xiàn)voidbresenham_arc(Graphics
g,intradius){int
x,y,d;x=0;y=radius;d=3-2*radius;while(x<y){
g.drawLine(x,y,x,y);
if(d<0)d=d+4*x+6; else{d=d+4*(x-y)+10;y--;}x++;}
if(x==y)g.drawLine(x,y,x,y);}3.3.3圓的多邊形迫近法基本思想按一定方式計算給定圓弧軌跡上的一系列頂點，然后用連接相鄰點的一系列直線段來逼近圓弧。用正多邊形迫近圓弧法設圓弧所在圓的半徑為R，圓弧的起始角和終止角分別為和，把圓弧分割成份，則相鄰兩個頂點之間的夾角為。設頂點序列的第個點為，為該點的幅角。則下一個頂點的坐標為或表示為矩陣形式3.3.3圓的多邊形迫近法橢圓弧的生成設橢圓的中心在原點，長短軸分別為a和b，且平行于坐標柚，則該橢圓的參數(shù)方程為，設頂點序列的第i個頂點為,則下一個頂點的坐標應滿足
,
由此可得其中3.4多邊形的掃描轉(zhuǎn)換3.4.1多邊形的掃描轉(zhuǎn)換多邊形的表示方法：頂點表示和點陣表示。頂點表示是用多邊形的頂點序列來描述多邊形，如可用P0P1P2P3P4P0的點序列來表示圖3.11中的多邊形。該表示幾何意義強、占內(nèi)存少、幾何變換方便；但不能直觀地說明哪些像素在多邊形內(nèi)，故不能直接用于面著色。圖3.11多邊形的頂點表示P1P0P2P3P4圖3.12多邊形的點陣表示3.4.1多邊形的掃描轉(zhuǎn)換點陣表示用位于多邊形內(nèi)的像素的集合來描述多邊形。如圖3.11的多邊形可表示成圖3.12的標有·號的像素的集合，該方法雖然沒有多邊形的幾何信息，但便于用幀緩存表示圖形，可直接用于面著色。多邊形的掃描轉(zhuǎn)換就是把多邊形的頂點表示轉(zhuǎn)換為點陣表示，即從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個像素，并為幀緩存內(nèi)的各個對應元素設置相應的灰度或顏色。3.4.2掃描線算法基本思想掃描線算法按掃描線的順序計算出掃描線與多邊形的相交區(qū)間，然后用要求的顏色填充這些區(qū)間內(nèi)的像素。該算法利用了掃描線的連續(xù)性和邊的連續(xù)性，避免對像素的逐點判斷和反復求交運算，減少了計算量，提高了算法速度。先求出掃描線與多邊形邊的交點，利用掃描線的連續(xù)性求出多邊形與掃描線相交的連續(xù)區(qū)域，然后利用多邊形邊的連續(xù)性，求出下一條掃描線與多邊形的交點，對所有掃描線由上到下依次處理。3.4.2掃描線算法1掃描線的連續(xù)性設多邊形P的頂點，將各頂點的縱坐標按遞減順序排列,即設當前掃描線，，與多邊形P的邊的交點記為。設為與P的邊界各交點橫坐標的遞增序列，該序列稱為交點序列。(3.21)3.4.2掃描線算法交點序列具有以下性質(zhì)：交點個數(shù)l是偶數(shù)；掃描線上的區(qū)間 l–1位于多邊形P內(nèi)（圖3.13中的實線段部分），其余區(qū)間都在P外（圖3.13中的虛線段部分），兩類區(qū)間沿掃描線相間排列。這些性質(zhì)就稱為掃描線的連續(xù)性。P0P1P2P3P4P5P6P7P8xe0xe2xe3xe7xe6xe4圖3.13掃描線的連續(xù)性圖中----表示在多邊形外的區(qū)間──表示在多邊形內(nèi)的區(qū)間根據(jù)掃描線的連續(xù)性，只需求出掃描線與多邊形P的邊界的所有交點，就可確定掃描線位于多邊形P內(nèi)的區(qū)間。3.4.2掃描線算法2邊的連續(xù)性設當前掃描線的下一條掃描線為，，且,設位于掃描線上的交點序列為
（3.22）若,
成立，則掃描線與掃描線和多邊形P相同的邊相交，由掃描線的連續(xù)性知，兩序列（3.21）和（3.22）的點滿足以下關(guān)系：（1）兩序列元素的個數(shù)相等，即。（2）點（）與（）位于多邊形P的同一邊上（見圖3.14），所以可由下式計算
(3.23)以上性質(zhì)稱為邊的連續(xù)性。3.4.2掃描線算法圖3.14邊的連續(xù)性P0P1P2P3P4P5P6P7P8xe0xe2xe3xe7xe6xe4xd0xd6xd43.4.2掃描線算法3奇點的處理上述三種形式的連續(xù)性都基于一個幾何事實：每一條掃描線與多邊形P的邊界的交點個數(shù)都是偶數(shù)（包括零）。但是當掃描線與多邊形P的邊界的交點恰好是P的頂點時（該交點稱為奇點）：如果把每一奇點簡單地計為一個交點，則交點個數(shù)可能出現(xiàn)奇數(shù)（如圖3.15中的掃描線的情況）；若將每一奇點都簡單地計為兩個交點，同樣會導致反常的結(jié)果（如圖3.15中掃描線的情況）。因此，必須按不同的情況區(qū)別對待奇點。3.4.2掃描線算法設多邊形P的頂點為這些頂點可分為兩類：極值點和非極值點。如果，則稱頂點為極值點（如圖3.15中的）；否則稱為非極值點（如圖3.15中的）。P0P1P2P3P4P5P6P7圖3.15一個多邊形與若干條掃描線P83.4.2掃描線算法為使每一條掃描線與多邊形P的邊界的交點個數(shù)始終為偶數(shù)，規(guī)定當奇點是多邊形P的極值點時，該點按兩個交點計算，否則按一個交點計算。圖3.16非極值點的處理（a）（b）實際計算中，可如下處理非極值點：若是非極值點，則將,兩邊中位于掃描線上方的那條邊在處截去一個單位長，這樣就能保證掃描線只和，中的一邊相交，只有一個交點。3.4.2掃描線算法4算法的實現(xiàn)步驟與數(shù)據(jù)結(jié)構(gòu)對于每一條掃描線，多邊形的填充過程可分為以下4步：計算掃描線與多邊形各邊的交點，設交點個數(shù)為n。把所有的交點按x值遞增的順序進行排列。將排序后的第1個與第2個交點，第3個與第4個交點，……第n-1個與第n個交點配對，每對交點就代表掃描線與多邊形的一個相交區(qū)間。把相交區(qū)間內(nèi)的像素置成多邊形的顏色，相交區(qū)間外的像素置成背景色。12343.4.2掃描線算法活性邊表與當前掃描線相交的邊稱為活性邊。把活性邊與掃描線的交點按x坐標遞增的順序放在一個鏈表中，該鏈表就稱為活性邊表（ActiveEdgeList,AEL
）。設多邊形某一條邊的方程為，當前掃描線與該邊的交點坐標為，則下一條掃描線與該邊的交點不需要重新計算，只要加一個增量即可。因為此時有其中為常數(shù)，并規(guī)定時，。3.4.2掃描線算法使用增量計算時，還要知道一條邊何時不再與下一條掃描線相交，以及時地把該邊從活性邊表中刪除，因此需要記錄下與該邊相交的最高掃描線號。綜上，AEL中的節(jié)點應由如下四個域組成：
:邊的上端點的y坐標，即與該邊相交的最高掃描線號。x:邊與掃描線的交點的x坐標。
:從當前掃描線到下一條掃描線間的x坐標的增量，即邊的斜率的倒數(shù)。Next:指向下一條邊的指針。3.4.2掃描線算法新邊表為方便活性邊表的建立與更新，還要為每一條掃描線建立一個新邊表（NewEdgeList,
NEL
），存放在該掃描線上第一次出現(xiàn)的邊。也就是說，如果某邊的較低端點為，則該邊就放在掃描線的新邊表中。注意：水平邊不放到任何掃描線的NEL中，即水平邊不參加分類。NEL中的節(jié)點結(jié)構(gòu)與AEL相同，只是x在這里不再表示邊與掃描線的交點，而是表示該邊較低端點的x坐標值。3.4.2掃描線算法具體例子圖3.18和3.19是圖3.17中多邊形的新邊表NEL和活性邊表AEL。在圖3.17中表示邊，各頂點為[P0P1…P6]=[(2,5)(2,10)(9,6)(16,9)(16,4)(12,2)(7,2)]
其中，是非極值點，在分類前已對邊作了預處理，即分別在處把它們截去一個單位長，這樣保證掃描線只和兩邊中的一邊相交，求得一個交點，是水平邊，不參加分類。3.4.2掃描線算法圖3.17多邊形P0P1…P6P051015P1P2P3P4P5P6P0e0e2e3e5e1e4e63.4.2掃描線算法圖3.18新邊表NEL123456e5e0e11002e3e2△xxymaxnext109e4901699574212e6AELAELe0e4e1e3e2xymax△xnexte5圖3.19活性邊表AEL55421410021059149016AEL在y=3掃描線上的狀態(tài)AEL在y=8掃描線上的狀態(tài)3.4.2掃描線算法3.4.3邊緣填充算法基本思想假設某像素的顏色是，對該像素做偶數(shù)次求補運算后，其顏色還是；做奇數(shù)次求補運算后，其顏色變?yōu)椤Ｔ诠鈻艌D形中，如某區(qū)域已著上值為M的某種顏色，則上述求補運算的結(jié)果是：對區(qū)域作偶數(shù)次求補運算后，該區(qū)域的顏色不變；作奇數(shù)次求補運算后，該區(qū)域的顏色則變成值為的顏色。3.4.3邊緣填充算法具體步驟對多邊形P的每一非水平邊（i=0,1,…,n）上的各像素進行向右求補運算，當相對于所有邊的求補運算都完成后，多邊形的掃描轉(zhuǎn)換也隨之完成。圖3.20a為給定的多邊形；b為對區(qū)域賦初值；c、d、e和f表示逐邊向右求補。(a)(b)(c)(d)(f)(e)圖3.20邊緣填充算法的過程3.4.4邊界標志算法基本思想首先用一種特殊的顏色在幀緩存中將多邊形的邊界（水平邊的部分邊界除外）勾畫出來，然后再把位于多邊形內(nèi)的各個區(qū)段著上所需的顏色。具體步驟步驟1：以值為boundary_color
的特殊顏色勾畫多邊形P的邊界。設多邊形的頂點為均為整數(shù)，置。下面的算法可保證每一條掃描線上著上這種特殊顏色的點的個數(shù)是偶數(shù)（包括零）。3.4.4邊界標志算法intred=Color.red.getRGB();publicImageboundary(){Imageimage;//定義Image對象for(i=0;i<7;i++){dy=p[i+1].y-p[i].y;
dx=(p[i+1].x-p[i].x)/dy;
if(dy>0)x=p[i].x;elsex=p[i+1].x;
ymax=(Math.max(p[i].y,p[i+1].y));
ymin=(Math.min(p[i].y,p[i+1].y));for(y=ymin+1;y<=ymax;y++){x=(int)(x+dx+.5);
if(pixels[y*w+x]==red)pixels[y*w+x+1]=red;elsepixels[y*w+x]=red;}}
ImageProducer
ip=newMemoryImageSource(w,h,pixels,0,w);image=createImage(ip);returnimage;}3.4.4邊界標志算法步驟2：逐條處理掃描線對多邊形著色。設in_flag是一布爾變量。對每一條掃描線從左到右進行搜索，若當前像素位于多邊形P內(nèi)，則in_flag=true，需填上值為polygon_color的顏色；若該像素在多邊形P外，則需填上值為background_color的顏色：//maxx、maxy、minx、miny是獲得的多邊形最小矩形包圍盒邊界值publicImageinterior(){Imageimage;
int
maxx=150,minx=20,maxy=120,miny=20,l;
int
in_flag；//多邊形內(nèi)部標志變量for(y=miny-1;y<=maxy;y++){in_flag=0;for(x=minx-1;x<maxx;x++){l=pixels2[y*w+x];if(l==red){if(in_flag==0)in_flag=1;elsein_flag=0;}
if(in_flag==1)pixels2[y*w+x]=red;}}
ImageProducer
ip=newMemoryImageSource(w,h,pixels,0,w);image=createImage(ip);returnimage;}3.4.4邊界標志算法3.4.4邊界標志算法具體例子
邊界標志算法的過程(a)
勾畫邊界(b)
在y=1的掃描線上轉(zhuǎn)換(c)
在y=2的掃描線上轉(zhuǎn)換(d)
掃描轉(zhuǎn)換完畢3.5區(qū)域填充區(qū)域填充是指先將區(qū)域內(nèi)的一點（常稱種子點）賦予給定顏色，然后將這種顏色擴展到整個區(qū)域內(nèi)的過程。3.5.1區(qū)域的表示和類型1內(nèi)點表示把位于給定區(qū)域內(nèi)的所有像素一一列舉出來的方法稱為內(nèi)點表示法。它將區(qū)域內(nèi)的所有像素填充成同一種顏色（常稱為原色），而區(qū)域邊界上的像素則不能填這種顏色。如圖3.22，有·的方格表示內(nèi)點，在內(nèi)點處像素填原色。圖3.22內(nèi)點表示的區(qū)域圖3.23邊界表示的區(qū)域2邊界表示法3.5.1區(qū)域的表示和類型把位于給定區(qū)域邊界上的像素一一列舉出來的方法稱為邊界表示法。它將區(qū)域邊界上的像素都著上同一種顏色（常稱為邊界色），而區(qū)域內(nèi)的像素則不能著這種顏色。如圖3.23，有×的方格表示邊界點，在邊界點處像素填邊界色。3.5.1區(qū)域的表示和類型3區(qū)域的連通性四連通的區(qū)域是指從該區(qū)域內(nèi)一點出發(fā)，通過上、下、左、右四種運動（如圖3.24）的組合，在不越出區(qū)域的前提下，可到達區(qū)域內(nèi)的任一點。八連通的區(qū)域是指從該區(qū)域內(nèi)一點出發(fā)，通過沿水平方向、垂直方向和對角線方向的八種運動（如圖3.25）的組合，在不越出區(qū)域的前提下，可到達區(qū)域內(nèi)的任一點。圖3.24四個方向的運動圖3.25八個方向的運動3.5.1區(qū)域的表示和類型圖3.26內(nèi)點表示的八連通區(qū)域圖3.27邊界表示的八連通區(qū)域3.5.1區(qū)域的表示和類型用于八連通區(qū)域的填充算法可用于四連通區(qū)域的填充，但用于四連通區(qū)域的填充算法并不適用于八連通區(qū)域的填充。四連通區(qū)域也可理解成八連通區(qū)域，但兩者的邊界不盡相同。若將圖3.28中標有·號的像素組成的區(qū)域作為四連通區(qū)域，則其邊界由圖中標有△號的像素組成。若將該區(qū)域作為八連通區(qū)域，則其邊界由圖中標有△號和×號的兩種像素組成。圖3.28四連通區(qū)域與八連通區(qū)域的不同邊界3.5.2遞歸算法基本思想設（x,y）是內(nèi)點表示的一區(qū)域G內(nèi)的一點，old_color是G的原色。先?。▁,y）點為種子點，測試其顏色，若等于old_color，說明是區(qū)域內(nèi)一點，則將其置為新的顏色new_color，否則說明該點不在區(qū)域G內(nèi)，則停止填充；然后將該點周圍的四個點（四連通）或八個點（八連通）作為新的種子點進行同樣的處理，通過這種擴散完成對整個區(qū)域的填充。顯然，這一過程是用遞歸實現(xiàn)的。3.5.2遞歸算法publicvoidflood_fill_8(int[]pixels,int
x,int
y,int
old_color,int
new_color){if(x<w&&x>0&&y<h&&y>0){if(pixels[w*y+x]==old_color){
pixels[w*y+x]=new_color; flood_fill_8(pixels,x,y+1,old_color,new_color); flood_fill_8(pixels,x,y-1,old_color,new_color); flood_fill_8(pixels,x-1,y,old_color,new_color); flood_fill_8(pixels,x+1,y,old_color,new_color); flood_fill_8(pixels,x+1,y+1,old_color,new_color); flood_fill_8(pixels,x+1,y-1,old_color,new_color); flood_fill_8(pixels,x-1,y+1,old_color,new_color); flood_fill_8(pixels,x-1,y-1,old_color,new_color);}}}算法實現(xiàn)3.5.3掃描線種子填充算法基本思想從給定的種子點開始，先填充種子點所在掃描線上的位于給定區(qū)域內(nèi)的一個區(qū)間，然后確定與這一區(qū)間相鄰的上下兩條掃描線上需要填充的區(qū)間，從這些區(qū)間上各取一個種子點并依次保存下來，作為下次填充的種子點，反復進行這個過程，直到所保存的各區(qū)間都填充完畢。3.5.3掃描線種子填充算法算法實現(xiàn)①將堆棧置空，并將給定的種子點（x,y）壓入堆棧。②若堆棧為空，算法結(jié)束；否則取棧頂元素（x,y）作為種子點。③從種子點（x,y）出發(fā)，沿縱坐標為y的當前掃描線向左右兩個方向用新的顏色逐個像素地填充，直到邊界。設區(qū)間兩邊界的橫坐標分別為和。④以區(qū)間為搜索范圍，檢查與當前掃描線相鄰的上下兩條掃描線上的像素，若存在非邊界、未填充的像素，則把相應小區(qū)間中最右邊的點作為種子點壓入堆棧，轉(zhuǎn)入②。3.5.3掃描線種子填充算法程序publicvoidscan(int[]pixels,Point
point,int
old_color,int
new_color){int
x,y,savex,xright,xleft;Pointp;Stackstack=newStack();//設置堆棧對象
stack.push(point);//壓棧
boolean
span_need_fill;while(!stack.empty()){p=(Point)(stack.pop());//出棧，從堆棧中取一像素作為種子像素
x=p.x;y=p.y;
savex=x;//保存橫坐標x的值
while(pixels[y*w+x]!=boundary_color){
pixels[y*w+x]=new_color;x++;}//從種子像素開始向右填充到邊界 xright=x-1;//保存線段的右端點x=savex-1;while(pixels[y*w+x]!=boundary_color){
pixels[y*w+x]=new_color;x--;}//從種子像素開始向左填充到邊界，以上兩步完成區(qū)間填充xleft=x+1;//保存線段的左端點x=xleft;y=y+1;while(x<=xright){//在上一條掃描線上檢查是否需要填充
span_need_fill=false;while(pixels[w*y+x]==old_color&&x<=xright){//待填充的線段
span_need_fill=true;x++;}//待填充的線段處理完3.5.3掃描線種子填充算法if(span_need_fill){//如果區(qū)間需要填充，則將其右端點作為 //種子點壓進堆棧p=newPoint(x-1,y);
stack.push(p);//進棧
span_need_fill=false;}//繼續(xù)向右檢查以防有遺漏
while(pixels[y*w+x]!=old_color&&x<=xright)x++;}//在上一條掃描線上檢查完x=xleft;y=y-2;//形成下一條掃描線的y值
//在下一條掃描線上從左向右地檢查位于區(qū)間[xleft,xright]上的像素
3.5.3掃描線種子填充算法while(x<=xright){
span_need_fill=false;while(pixels[w*y+x]==old_color){
span_need_fill=true; x++;} if(span_need_fill){ p=newPoint(x-1,y);
stack.push(p);
span_need_fill=false; }
while(pixels[y*w+x]!=old_color&&x<=xright)x++;}}}3.5.3掃描線種子填充算法3.5.3掃描線種子填充算法(a)
1212(b)12123(c)(d)算法執(zhí)行過程示例3.6字符的生成3.6.1點陣式字符點陣式字符是將字符形狀表示為一個矩形點陣，由點陣中點的不同值來表達字符的形狀。常用的點陣大小有7×9、8×8
溫馨提示
- 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 勤雜工合同范例
- 合伙種葡萄合同范本
- 合伙開店股合同范例
- 醫(yī)療勞動合同范本
- 合同范本 模板
- 合伙經(jīng)營酒吧合同范本
- 鄉(xiāng)鎮(zhèn)山林承租合同范本
- 半價打包餐飲服務合同范本
- ppp項目政府合同范本
- 雙方合作開發(fā)合同范例
- 通達信公式函數(shù)說明大全
- 體育初中學生學情分析總結(jié)報告
- MOOC 中國文化概論-武漢大學 中國大學慕課答案
- 高三心理健康輔導講座省公開課一等獎全國示范課微課金獎
- 《工程建設標準強制性條文電力工程部分2023年版》
- 壺口瀑布公開課省公開課一等獎全國示范課微課金獎課件
- 2024年度年福建省考評員考試題庫附答案(基礎題)
- 基于PLC智能家居控制系統(tǒng)設計
- 醫(yī)院內(nèi)控評價工作報告
- (2024年)神經(jīng)內(nèi)科科室應急全新預案x
- 《起重機械安全評估規(guī)范》編制說明（征求意見稿）
評論
0/150
提交評論