1、3.4 區(qū)域填充區(qū)域填充前面介紹的直線和圓都屬于線劃圖，然而，光柵顯示的一個(gè)重要特點(diǎn)是能進(jìn)行面著色，區(qū)域填充就是在一個(gè)閉合區(qū)域內(nèi)填充某種顏色或圖案。區(qū)域填充一般分兩類：多邊形填充和種子填充。一、多邊形填充1、填充條件多邊形的頂點(diǎn)序列(Pi，i=0，1，n)、填充色。2、多邊形內(nèi)點(diǎn)的判別準(zhǔn)則對(duì)多邊形進(jìn)行填充，關(guān)鍵是找出多邊形內(nèi)的象素。在順序給定多邊形頂點(diǎn)坐標(biāo)的情況下，如何判明一個(gè)象素點(diǎn)是處于多邊形的內(nèi)部還是外部呢？多邊形內(nèi)點(diǎn)的判別準(zhǔn)則和奇異點(diǎn) 從測(cè)試點(diǎn)引出一條伸向無(wú)窮遠(yuǎn)處的射線(假設(shè)是水平向右的射線)，因?yàn)槎噙呅问情]合的，那么：若射線與多邊形邊界的交點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，則該點(diǎn)為內(nèi)點(diǎn)(例：圖中測(cè)試點(diǎn)4

2、引出的射線)；反之，交點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，則該點(diǎn)為外點(diǎn)。(例：測(cè)試點(diǎn)2引出的射線)。3、奇異點(diǎn)的處理：上述的判別準(zhǔn)則，在大多數(shù)情況下是正確的，但當(dāng)水平掃描線正好通過(guò)多邊形頂點(diǎn)時(shí)，要特別注意。例如，圖中過(guò)頂點(diǎn)的射線1、射線6，它們與多邊形的交點(diǎn)個(gè)數(shù)為奇數(shù)，按照判別準(zhǔn)則它們應(yīng)該是內(nèi)點(diǎn)，但實(shí)際上卻是外點(diǎn)。 而圖中過(guò)頂點(diǎn)的射線3、射線5，對(duì)于判別準(zhǔn)則的使用又是正確的。 多邊形內(nèi)點(diǎn)的判別準(zhǔn)則和奇異點(diǎn)綜合以上情況，我們將多邊形的頂點(diǎn)分為兩大類： (1) 局部極值點(diǎn)：如圖中的點(diǎn)P1、P2、P4和P6。對(duì)于這些點(diǎn)來(lái)說(shuō)，進(jìn)入該點(diǎn)的邊線和離開(kāi)該點(diǎn)的邊線位于過(guò)該點(diǎn)掃描線的同一側(cè)。(2)非極值點(diǎn)：如圖中的點(diǎn)P3、P5。對(duì)

3、于這些點(diǎn)來(lái)說(shuō)，進(jìn)入該點(diǎn)的邊線和離開(kāi)該點(diǎn)的邊線位于過(guò)該點(diǎn)掃描線的兩側(cè)。處理奇異點(diǎn)規(guī)則：（1）對(duì)于局部極值點(diǎn)，應(yīng)看成兩個(gè)點(diǎn)；（2）對(duì)于非極值點(diǎn)，應(yīng)看成一個(gè)點(diǎn)。多邊形內(nèi)點(diǎn)的判別準(zhǔn)則和奇異點(diǎn)4、逐點(diǎn)判別算法步驟：(1)求出多邊形的最小包圍盒：從Pi(xi，yi)中求極值，xmin、ymin、xmax、ymax。 (2)對(duì)包圍盒中的每個(gè)象素引水平射線進(jìn)行測(cè)試。 (3)求出該射線與多邊形每條邊的有效交點(diǎn)個(gè)數(shù)。 (4)如果個(gè)數(shù)為奇數(shù)：該點(diǎn)置為填充色。 (5)否則：該點(diǎn)置為背景色。 逐點(diǎn)判別算法雖然簡(jiǎn)單，但不可取，原因是速度慢。它割斷了各象素之間的聯(lián)系，孤立地考慮問(wèn)題，由于要對(duì)每個(gè)象素進(jìn)行多次求交運(yùn)算，求交時(shí)

4、要做大量的乘除運(yùn)算，從而影響了填充速度。 3.3.1邊相關(guān)掃描線多邊形填充算法邊相關(guān)掃描線多邊形填充算法 邊相關(guān)掃描線填充算法屬于多邊形填充類。它比逐點(diǎn)判別算法速度提高很多，是一種較經(jīng)典的多邊形填充算法。該算法利用了掃描線的相關(guān)性和多邊形邊的相關(guān)性，而不是逐點(diǎn)進(jìn)行處理。一、邊相關(guān)掃描線填充算法描述掃描線的相關(guān)性掃描線的相關(guān)性：某條掃描線上相鄰的象素，幾乎都具有同樣的內(nèi)外性質(zhì)，這種性質(zhì)只有遇到多邊形邊線與該掃描線的交點(diǎn)時(shí)才發(fā)生改變。見(jiàn)下圖(a)。邊的相關(guān)性邊的相關(guān)性：由于相鄰掃描線上的交點(diǎn)是與多邊形的邊線相關(guān)的。對(duì)同一條邊，前一條掃描線yi與該邊的交點(diǎn)為xi，而后一條掃描線yi+1=yi+1與該

5、邊的交點(diǎn)則為xi+1=xi+1/m，利用這種相關(guān)性可以省去大量的求交運(yùn)算。見(jiàn)下圖(b)所示。 邊相關(guān)掃描線填充算法的實(shí)現(xiàn)需要建立兩個(gè)表：邊表（ET）和活動(dòng)邊表（AET）。1、邊表邊表（ET：Edge Table）用來(lái)對(duì)除水平邊外的所有邊進(jìn)行登記，來(lái)建立邊的記錄。邊的記錄定義為： 掃描線 y 對(duì)應(yīng)的ET表第一項(xiàng)：某邊的最大y值（ymax）。注意要進(jìn)行奇異點(diǎn)處理：對(duì)于非極值點(diǎn)應(yīng)該ymax=ymax-1。第二項(xiàng)：某邊的最小的y對(duì)應(yīng)的x值。第三項(xiàng)：某邊斜率的倒數(shù):1/m。第四項(xiàng)：指針。用來(lái)指向同一條掃描線相交的其它邊，如果其它邊不存在，則該項(xiàng)置空。二、邊相關(guān)掃描線填充算法思想1、根據(jù)給出的多邊形頂點(diǎn)坐

6、標(biāo)，建立ET表； 求出頂點(diǎn)坐標(biāo)中最大y值ymax和最小y值ymin。2、初始化AET表指針，使它為空。2、活動(dòng)邊表活動(dòng)邊表（AET：Active Edge Table）ET表建立以后，就可以開(kāi)始掃描轉(zhuǎn)換了。對(duì)不同的掃描線，與之相交的邊線也是不同的，當(dāng)對(duì)某一條掃描線進(jìn)行掃描轉(zhuǎn)換時(shí)，我們只需要考慮與它相交的那些邊線，為此需要建立一個(gè)只與當(dāng)前掃描線相交的邊記錄鏈表，稱之為活動(dòng)邊表。3、使用掃描線的yj值作為循環(huán)變量，使其初值為ymin。對(duì)于循環(huán)變量yj的每一整數(shù)值，重復(fù)作以下事情，直到y(tǒng)j大于ymax，或ET表與AET表都為空為止：(1) 如果ET表中yj桶非空，則將yj桶中的全部記錄合并合并到AE

7、T表中。(2) 對(duì)AET表鏈中的記錄按x的大小從小到大排序排序。(3) 依次取出AET表各記錄中的xi坐標(biāo)值，兩兩配對(duì)填充填充，即將每對(duì)xi之間的象素填上所要求的顏色。(4) 如果AET表中某記錄的ymax=yj，則刪除刪除該記錄。(5) 對(duì)于仍留在AET表中的每個(gè)記錄，用xi+1/m代替xi進(jìn)行修改修改，這就是該記錄的邊線與下一條掃描線yj+1的交點(diǎn)。(6) 使yj加加1，以便進(jìn)入下一輪循環(huán)。三、邊相關(guān)掃描線填充算法舉例 對(duì)下圖(a)的多邊形利用邊相關(guān)掃描線填充算法進(jìn)行處理：1、首先建立ET表。 注意：在做奇異點(diǎn)處理時(shí)，當(dāng)該邊最大y值對(duì)應(yīng)的頂點(diǎn)為非極值點(diǎn)時(shí)，邊記錄的第一項(xiàng)：ymax=ymax

8、-1。例如：P3P4邊、P3P2邊、P4P5邊，見(jiàn)下圖(b)。2、接著建立AET表。AET表的建立過(guò)程就是有效地進(jìn)行填充的操作，在這個(gè)期間不斷地做以下工作： (a) 多邊形 (b) ET表 (c) AET表1）合并ET表；2）x遞增排序；3）實(shí)施填充；4）刪除ymaxyj的邊；5）修改邊記錄xi=xi+1/m；6）yj+1進(jìn)入下一輪循環(huán)。 四、邊相關(guān)掃描線填充算法實(shí)現(xiàn)1、根據(jù)給定的多邊形頂點(diǎn)坐標(biāo)，建立ET 表。2、AET表初始化，每個(gè)桶置空。3、for(y=ymin;y= ymax;y+) 合并當(dāng)前掃描線y的ET表； 將y桶中每個(gè)記錄按x項(xiàng)升序排列； 在當(dāng)前y值下，將兩兩記錄的x值之間的象素進(jìn)

9、行填充； 刪除y=ymax的邊記錄； 修改邊記錄x=x+1/m； 五、邊相關(guān)掃描線填充算法特點(diǎn)該算法充分利用多邊形的邊相關(guān)性和掃描線的相關(guān)性，使用ET表對(duì)多邊形的非水平邊進(jìn)行登記；用AET表的建立和更新來(lái)支持填充，大大地減少了求交點(diǎn)的計(jì)算量，有效地提高了填充速度。練習(xí)：用邊相關(guān)掃描線填充算法，對(duì)圖中多邊形建立ET、AET表。 作業(yè)：用邊相關(guān)掃描線填充算法做出圖中多邊形的ET表和AET表。 二、種子填充種子填充是將區(qū)域內(nèi)的一點(diǎn)(種子)賦予給定的顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過(guò)程。1、填充條件區(qū)域內(nèi)一點(diǎn)的坐標(biāo)即種子坐標(biāo)、邊界色、填充色。2、連通方式區(qū)域是互相連通著的象素的集合，連通方式可分為四連通和八連通。四連通：從區(qū)域內(nèi)一點(diǎn)出發(fā)，可通過(guò)四個(gè)方向：上、下、左、右到達(dá)該區(qū)域內(nèi)部的任意象素。八連通：區(qū)域內(nèi)部從一個(gè)象素到達(dá)另一個(gè)象素的移動(dòng)路徑，除了上、下、左、右四個(gè)方向外，還允許沿著對(duì)角線方向。注意：（1） 八連通區(qū)域中，既然區(qū)域內(nèi)的兩個(gè)象素可以通過(guò)對(duì)角線相通，那么，區(qū)域邊界上的象素則不能通過(guò)對(duì)角線相連，否則填充就會(huì)溢出到區(qū)域外，因此，八連通區(qū)域的邊界線必須是四連通的，見(jiàn)下圖(a)；（2）而四連通區(qū)域，其邊界象素是四連通和八連通的都可以，見(jiàn)下圖(b)。(a) 八連通區(qū)域四連通邊界(b) 四連