第4章多邊形

本章我們將討論圖形系統(tǒng)中新的圖元——多邊形，研究有關(guān)多邊形的概念以及多邊形的表示，學(xué)習(xí)如何判斷一個(gè)點(diǎn)是否在多邊形內(nèi)的方法，以及多邊形的各種填充方法，重點(diǎn)講解種子填充算法。

第4章多邊形1.多邊形的定義2.多邊形的掃描轉(zhuǎn)換3.區(qū)域填充(種子填充算法)4.反走樣定義：一系列首尾相連的線段構(gòu)成的圖形。線段--------邊端點(diǎn)--------頂點(diǎn)4.1多邊形的定義一般情況：多邊形是封閉的多邊形分為凸多邊形、凹多邊形二種凸多邊形：連多邊形內(nèi)任意兩點(diǎn)的線段,該線段上的點(diǎn)均在多邊形內(nèi)。計(jì)算機(jī)生成的物體常?？梢杂萌舾啥噙呅蝸砻枋?，有些非多邊形的物體，也可以用多邊形來逼近。比如上一章二次曲線的繪制我們了解了可以用多邊形去逼近圓。在多邊形生成以后，就可以利用光柵顯示系統(tǒng)對(duì)其內(nèi)部區(qū)域進(jìn)行填充。那么多邊形是如何在系統(tǒng)中如何描述的呢？

頂點(diǎn)表示點(diǎn)陣表示

頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；缺點(diǎn)是不能直接用于面著色。點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來刻劃多邊形。便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。缺點(diǎn)是失去了許多重要的幾何信息；多邊形的頂點(diǎn)表示多邊形的點(diǎn)陣表示4.2多邊形的掃描轉(zhuǎn)換在繪圖過程中，僅有線條和多邊形來表示是不夠的，要逼真的顯示一個(gè)實(shí)面圖像至少要解決以下三個(gè)問題：1、面的形狀2、面上各點(diǎn)的色調(diào)(填充)3、各個(gè)面的互相遮擋的問題(消隱)什么是多邊形的掃描轉(zhuǎn)換？從多邊形頂點(diǎn)信息到該多邊形點(diǎn)陣表示的轉(zhuǎn)換——多邊形的掃描轉(zhuǎn)換，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種過程為多邊形的掃描轉(zhuǎn)換(又稱多邊形的填充)。多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換常用幾種方法：逐點(diǎn)判斷法；掃描線算法；邊填充法；柵欄填充法；邊界標(biāo)志法。逐點(diǎn)判斷法(1/7)算法思想：逐個(gè)象素點(diǎn)判別，確定它們是否在多邊形內(nèi)，從而來決定是否進(jìn)行著色。如何判斷點(diǎn)在多邊形的內(nèi)外關(guān)系？1）累計(jì)角度法(轉(zhuǎn)角和法)；2）射線法；3）符號(hào)法；逐點(diǎn)判斷法(2/7)1）累計(jì)角度法（轉(zhuǎn)角和法）步驟1.從某點(diǎn)向多邊形頂點(diǎn)發(fā)出射線，形成有向角2.計(jì)算有向角的和，得出結(jié)論若等于正負(fù)180度表示V在邊界上。該方法適用于：凸多邊形、凹多邊形逐點(diǎn)判斷法(3/7)若夾角和為0，則點(diǎn)p在多邊形外若夾角和為＋360°，則點(diǎn)p在多邊形內(nèi)ABCDEPABCDEP逐點(diǎn)判斷法(4/7)2）射線法ABCDEPABCDEP交點(diǎn)數(shù)=偶數(shù)（包括0）點(diǎn)在多邊形之外交點(diǎn)數(shù)=奇數(shù)點(diǎn)在多邊形之內(nèi)逐點(diǎn)判斷法(5/7)2）射線法步驟：從待判別點(diǎn)發(fā)出射線求交點(diǎn)個(gè)數(shù)kK的奇偶性決定了點(diǎn)與多邊形的內(nèi)外關(guān)系注意：1、若射線恰好交于多邊形R的端點(diǎn)，則如何處理？2、如何決定射線方向？逐點(diǎn)判斷法(6/7)3）符號(hào)比較法（適用于凸多邊形）

A>基礎(chǔ)知識(shí)二點(diǎn)式直線方程的表示及點(diǎn)與直線的關(guān)系多邊形各邊所在方程的表示方法B>步驟1、找多邊形內(nèi)一點(diǎn)M代入直線方程，計(jì)算M相對(duì)于各邊的符號(hào)情況。2、對(duì)待判定定P作同樣的操作3、對(duì)M和P相對(duì)于各邊的符號(hào)情況作比較逐點(diǎn)判斷法(7/7)#defineMAX100Typedefstruct{intPolygonNum;//多邊形頂點(diǎn)個(gè)數(shù)

Pointvertexces[MAX]//多邊形頂點(diǎn)數(shù)組}Polygon//多邊形結(jié)構(gòu)逐點(diǎn)判斷法的算法偽碼描述voidFillPolygonPbyP(Polygon*P,intfillColor){intx,y; for(y=0;y<=1023;y++)for(x=0;x<=767;x++) if(IsInside(P,x,y)) pDC->SetPixel(x,y,fillColor); else

pDC->SetPixel

(x,y,backgroundColor);}//endofFillPolygonPbyP() 假設(shè)整個(gè)屏幕區(qū)域只有一個(gè)多邊形對(duì)整個(gè)屏幕區(qū)域進(jìn)行掃描，假設(shè)屏幕大小為1024*768voidFillPolygonPbyP(Polygon*P,intfillColor){intx,y;for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++) if(IsInside(P,x,y))

pDC->SetPixel(x,y,fillColor); else

pDC->SetPixel(x,y,backgroundColor);}//endofFillPolygonPbyP() 對(duì)整個(gè)多邊形區(qū)域進(jìn)行掃描，比掃描整個(gè)屏幕肯定要節(jié)約時(shí)間，這是改進(jìn)后的偽碼描述逐點(diǎn)判斷的算法的優(yōu)缺點(diǎn)：雖然程序簡(jiǎn)單，但不可取。原因是速度太慢，主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得幾十萬甚至幾百萬個(gè)像素都要一一判別，每次判別又要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)很多時(shí)間。改進(jìn)思想：除邊界外，相鄰像素幾乎都有相同的特征。掃描線算法掃描線算法目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率處理對(duì)象：非自交多邊形（邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)）掃描線算法(1/26)掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對(duì)象素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少了計(jì)算量和提高速度的目的。

開發(fā)和利用相鄰象素之間的連貫性是光柵圖形算法研究的重要內(nèi)容。掃描線算法綜合利用了區(qū)域的連貫性、掃描線連貫性和邊的連貫性等三種形式的連貫性。掃描線算法(2/26)

設(shè)多邊形P的頂點(diǎn)Pi=(xi,yi),i=0,1,…,n，又設(shè)yi0,yi1,…yin是各頂點(diǎn)Pi的坐標(biāo)yi的遞減數(shù)列，即yik≥yik+1,0≤k≤n-1這樣，當(dāng)yik≥yik+1,0≤k≤n-1時(shí)，屏幕上位于y=yik和y=yik+1兩條掃描線之間的長方形區(qū)域被多邊形P的邊分割成若干梯形（三角形可看作其中一底邊長為零的梯形），它們具有下列性質(zhì)：區(qū)域的連貫性y=yiky=yik+1掃描線算法(3/26)區(qū)域的連貫性1）梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線上，腰在多邊形P的邊上或在顯示屏幕的邊界上。2）這些梯形可分為兩類：一類位于多邊形P的內(nèi)部；另一類在多邊形P的外部。3）兩類梯形在長方形區(qū)域{yik,yik+1}內(nèi)相間的排列，即相鄰的兩梯形必有一個(gè)在多邊形P內(nèi)，另一個(gè)在P外。y=yik+1y=yik掃描線算法(4/26)求出掃描線與多邊形的所有交點(diǎn)后，位于多邊形內(nèi)的直線段就不難找到了。設(shè)想我們從掃描線的一端出發(fā)，這時(shí)我們?cè)诙噙呅瓮猓驗(yàn)槎噙呅慰偸窃谟邢薹秶鷥?nèi)的。當(dāng)我們沿直線前進(jìn)到達(dá)第一個(gè)交點(diǎn)時(shí)，就開始進(jìn)入多邊形內(nèi)。由于直線的另一端是在多邊形外，繼續(xù)沿直線前進(jìn)一定會(huì)走出多邊形內(nèi)部，因此一定會(huì)遇到第二個(gè)交點(diǎn)。這時(shí)我們可以看到，第一和第二個(gè)交點(diǎn)給出的直線段就位于多邊形內(nèi)。如果沒有更多的交點(diǎn)，則該掃描線上只有一段直線段位于多邊形內(nèi)。如果繼續(xù)沿掃描線前進(jìn)，遇到第三個(gè)交點(diǎn)后，重新進(jìn)入多邊形內(nèi)。類似前面的分析，一定有第四個(gè)交點(diǎn)。于是第三、第四個(gè)交點(diǎn)給出的直線段就位于多邊形內(nèi)。掃描線的連貫性掃描線算法(5/26)

設(shè)d為一整數(shù)，并且d=e-1,并且

yi0≥d≥yin。設(shè)位于掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,xdj3,…,xdjk

現(xiàn)在來討論掃描線d，e交點(diǎn)序列之間的關(guān)系。若多邊形P的邊Pr-1Pr與掃描線y=e,y=d都相交，則交點(diǎn)序列中對(duì)應(yīng)元素xer,xdr滿足下列關(guān)系：xer=xdr+1/mr(1)其中mr為邊Pr-1Pr的斜率。

邊的連貫性y=ey=d掃描線算法(6/26)邊的連貫性于是，可利用d的交點(diǎn)序列計(jì)算e的交點(diǎn)序列，即先運(yùn)用遞推關(guān)系式(1)求得與掃描線y=e和y=d都相交的所有多邊形上的交點(diǎn)xer,再求得與掃描線y=d不相交但與掃描線y=e相交的所有邊PqPq+1上的交點(diǎn)xeq。如果P的頂點(diǎn)的坐標(biāo)是整數(shù)，那么xeq=xq或xeq=xq+1,然后把這兩部分按遞增的順序排列，即可得e的交點(diǎn)序列。y=ey=d掃描線算法(7/26)邊的連貫性特別是當(dāng)存在某一個(gè)整數(shù)k,0≤k≤n-1,使得yik>e,d>yik+1成立時(shí)，則由區(qū)域的連貫性可知d的交點(diǎn)序列和e的交點(diǎn)序列之間有以下關(guān)系：

1）兩序列元素的個(gè)數(shù)相等，如上圖所示。2）點(diǎn)(xeir,e)與(xdjr,d)位于多邊形P的同一邊上，于是xeir=xdjr+1/kjr(2)這樣，運(yùn)用遞推關(guān)系式(2)可直接由d的交點(diǎn)序列和e的獲得e的交點(diǎn)序列。以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。掃描線算法(8/26)當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)時(shí)，則稱該交點(diǎn)為奇點(diǎn)。以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。但是如果把每一奇點(diǎn)簡(jiǎn)單地計(jì)為一個(gè)交點(diǎn)或者簡(jiǎn)單地計(jì)為兩個(gè)交點(diǎn)，都可能出現(xiàn)奇數(shù)個(gè)交點(diǎn)。那么如果保證交點(diǎn)數(shù)為偶數(shù)呢？奇點(diǎn)的處理掃描線算法(9/26)奇點(diǎn)的處理若奇點(diǎn)做二個(gè)交點(diǎn)處理，則情況A，交點(diǎn)個(gè)數(shù)是偶數(shù)。若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況B，交點(diǎn)個(gè)數(shù)是偶數(shù)。掃描線算法(10/26)奇點(diǎn)的處理多邊形P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如果(yi-1-yi)(yi+1-yi)≥0，則稱頂點(diǎn)Pi為極值點(diǎn)；否則稱Pi為非極值點(diǎn)。(yi-1和yi+1為相鄰頂點(diǎn)坐標(biāo))規(guī)定：奇點(diǎn)是極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。掃描線算法(11/26)掃描線填充算法填充要注意的是一些與邊界相鄰的點(diǎn)，因?yàn)楦鶕?jù)屏幕像素點(diǎn)的特性，會(huì)發(fā)現(xiàn)有些點(diǎn)在多邊形的邊上，有的相交，在直線中的取整規(guī)則不適合于掃描線算法，這是因?yàn)椋簡(jiǎn)渭兊娜≌?guī)則會(huì)使生成的像素部分位于多邊形之外，而掃描線算法則是對(duì)多邊形內(nèi)部的像素進(jìn)行填充。見下頁圖所示。規(guī)則1取整問題規(guī)則2邊界問題規(guī)則3交點(diǎn)取舍幾條規(guī)則掃描線算法(12/26)掃描線算法(12/26)●規(guī)則：

X為小數(shù)，即交點(diǎn)落于掃描線上兩個(gè)相鄰像素之間(a)交點(diǎn)位于左邊之上，向右取整(b)交點(diǎn)位于右邊之上，向左取整掃描線算法(13/26)基本思想：按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。對(duì)于一條掃描線填充過程可以分為四個(gè)步驟：掃描線算法的基本思想多邊形與若干掃描線圖示求交排序配對(duì)填色掃描線基礎(chǔ)算法的核心是計(jì)算掃描線與多邊形的交點(diǎn)，然后配對(duì)，著色。其實(shí)求解交點(diǎn)這一步工作量是非常大的，所以根據(jù)前面介紹的多邊形邊的連貫性，區(qū)域的連貫性規(guī)則，我們可以構(gòu)造更簡(jiǎn)單的掃描線算法(有的書稱為有序邊表算法)。下面是其的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，改進(jìn)后的掃描線算法就是簡(jiǎn)化了不斷求解交點(diǎn)這么一個(gè)復(fù)雜的工作。掃描線算法(14/26)數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟算法基本思想：首先取d=yin。容易求得掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,…xdjn，這一序列由位于掃描線y=d上的多邊形P的頂點(diǎn)組成。由yin的交點(diǎn)序列開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。掃描線算法(15/26)數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟所有的邊和掃描線求交，效率很低。因?yàn)橐粭l掃描線往往只和少數(shù)幾條邊相交。如何判斷多邊形的一條邊與掃描線是否相交？與當(dāng)前掃描線相交的邊稱為活性邊（activeedge)，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表（AEL,Activeedgetable)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。只需對(duì)當(dāng)前掃描線的活動(dòng)邊表作更新，即可得到下一條掃描線的活動(dòng)邊表。掃描線算法(16/26)

關(guān)注掃描線與其相交的那些邊。算法執(zhí)行時(shí)要求建立一張有效邊表(AET)，AET中的內(nèi)容隨每一條掃描線y值的不同而變化，也即在AET中，只保留與當(dāng)前掃描線相交的所有的邊。而且這些邊按其與該掃描線交點(diǎn)的x坐標(biāo)大小的順序存放，以便于在一對(duì)交點(diǎn)之間填充。當(dāng)從一條掃描線移到下一條掃描線時(shí)，我們利用兩條掃描線間隔為1的特性，可以簡(jiǎn)化邊與掃描線交點(diǎn)的計(jì)算。掃描線算法(17/26)如何計(jì)算下一條掃描線與邊的交點(diǎn)。直線方程：ax+by+c=0當(dāng)前交點(diǎn)坐標(biāo)：(xi,yi)下一交點(diǎn)坐標(biāo)：(xi+1,yi+1)xi+1=

((-byi+1)-c)/a=((-byi-b)-c)/a=xi-b/a活動(dòng)邊表中需要存放的信息：

x：當(dāng)前掃描線與邊的交點(diǎn)

dx＝-b/a：從當(dāng)前掃描線到下一條掃描線之間的x增量

ymax：邊所交的最高掃描線掃描線算法(18/26)增加哪一條邊呢？為了方便邊的活化鏈表的更新，建立另一個(gè)表-邊表，存放在該掃描線第一次出現(xiàn)的邊。存放的信息：

x：掃描線與該邊的初始交點(diǎn)

dx：x的增量

ymax：該邊的最大y值掃描線算法(19/26)

即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表EL（EdgeList）和邊的活化鏈表AEL（ActiveEdgeList）兩部分組成。表結(jié)構(gòu)EL和AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成：

ymax

邊的上端點(diǎn)的y坐標(biāo)；

x在EL中表示邊的下端點(diǎn)的x坐標(biāo)，在AEL中則表示邊與掃描線的交點(diǎn)的坐標(biāo)；

Δx邊的斜率的倒數(shù)；

next指向下一條邊的指針。掃描線算法(20/26)

邊的分類表EL是按邊的下端點(diǎn)的y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)的值等于i的邊歸入第i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按x值（x值相等時(shí)，按Δx的值）遞增的順序排列成行。掃描線算法(21/26)已知多邊形P=(P1P2P3P4P5P6P1)；其各邊坐標(biāo)分別為[（2，2）（5，1）（11，3）（11，8）（5，5）（2，7）]建立其邊表和邊的活性邊表掃描線算法(22/26)各掃描線的新邊表掃描線算法(23/26)活動(dòng)邊表的例子(a)掃描線y=1的活性邊表；(b)掃描線y=2的活性邊表5-32533p1p2p2p32-32833p1p2p2p3掃描線算法(23/26)活動(dòng)邊表的例子(c)掃描線y=3的活性邊表；(d)掃描線y=4的活性邊表2071133p6p1p2p32071108p6p1p3p4掃描線算法(23/26)活動(dòng)邊表的例子(e)掃描線y=6的活性邊表；(f)掃描線y=7的活性邊表掃描線算法(24/26)算法實(shí)現(xiàn)步驟這樣，當(dāng)建立了邊的分類表EL后，掃描線算法可按下列步驟進(jìn)行：（1）取掃描線縱坐標(biāo)y的初始值為EL中非空元素的最小序號(hào)。（2）將邊的活化鏈表AEL設(shè)置為空。（3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。掃描線算法(25/26)1）如邊分類表EL中的第y類元素非空，則將屬于該類的所有邊從EL中取出并插入邊的活化鏈表中，AEL中的各邊按照x值（當(dāng)x值相等時(shí)，按Δx值）遞增方向排序。2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對(duì)，即1，2邊為一對(duì)，3，4邊為一對(duì)，依次類推。每一對(duì)邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對(duì)這些區(qū)段上的點(diǎn)（象素）按多邊形屬性著色。3）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。4）將邊的活化鏈表AEL剩下的每一條邊的x域累加Δx，即x:=x+Δx。5）將當(dāng)前的掃描線的縱坐標(biāo)值y累加1，即y=y+1。算法實(shí)現(xiàn)步驟掃描線算法(26/26)特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。缺點(diǎn)：對(duì)各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。存在問題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？掃描線算法總結(jié)

基本思想：光柵圖形中，如果某區(qū)域已著上值為M的顏色值做偶數(shù)次求余運(yùn)算，該區(qū)域顏色不變；而做奇數(shù)次求余運(yùn)算，則該區(qū)域顏色變?yōu)橹禐樾碌念伾?。這一規(guī)律應(yīng)用于多邊形掃描轉(zhuǎn)換，就為邊填充算法。邊填充算法邊填充算法實(shí)例邊填充算法小結(jié)適合用于具有幀緩存的圖形系統(tǒng)。按任意順序處理多邊形的邊后，再按掃描線順序讀出幀緩存的內(nèi)容，送入顯示設(shè)備。優(yōu)點(diǎn)：算法簡(jiǎn)單，易于實(shí)現(xiàn)；缺點(diǎn)：對(duì)于復(fù)雜圖形，每一象素可能被訪問多次，輸入/輸出的量比掃描線算法大得多。改進(jìn)：引入柵欄，見柵欄填充算法引入柵欄，以減少填充算法訪問象素的次數(shù)。柵欄：與掃描線垂直的直線，通常過一頂點(diǎn)，且把多邊形分為左右二半。柵欄填充算法基本思想：掃描線與多邊形的邊求交，將交點(diǎn)與柵欄之間的象素取補(bǔ)。柵欄填充算法優(yōu)缺點(diǎn)：減少了象素重復(fù)訪問數(shù)目，但不徹底。引入邊標(biāo)志：以克服象素被重復(fù)訪問的缺點(diǎn)。邊界標(biāo)志算法算法思想：1.輪廓線：對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過的象素作一個(gè)邊界標(biāo)志。2.填充：對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問該掃描線上的象素。邊界標(biāo)志算法實(shí)現(xiàn)細(xì)節(jié)：取一個(gè)布爾變量inside來指示當(dāng)前點(diǎn)的狀態(tài)，Inside的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。若inside為真，則點(diǎn)在多邊形內(nèi)，著色。若inside為假，則點(diǎn)在多邊形外，著背景色

邊界標(biāo)志算法:算法描述voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對(duì)多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；

inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個(gè)象素x){if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}邊界標(biāo)志算法小結(jié)處理每一條掃描線時(shí)，象素點(diǎn)只被訪問一次；用軟件實(shí)現(xiàn)時(shí)，邊界標(biāo)志算法與掃描線算法的執(zhí)行速度幾乎相同；課后思考題：如何處理邊界的交點(diǎn)個(gè)數(shù)使其成為偶數(shù)？用硬件實(shí)現(xiàn)時(shí)，它的執(zhí)行速度比掃描線算法快一至兩個(gè)數(shù)量級(jí)，這是由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)；上一節(jié)我們講述了多邊形的掃描轉(zhuǎn)換，在實(shí)際應(yīng)用中，我們可能會(huì)遇到任意的區(qū)域，如下圖所示。4.3區(qū)域填充(種子填充算法)⒈

掃描線填色(Scan-LineFilling)算法。這類算法建立在多邊形邊界的矢量形式數(shù)據(jù)之上，可用于程序填色，也可用于交互填色。⒉種子填色(SeedFilling)算法。這類算法建立在任意封閉邊界的圖像形式數(shù)據(jù)之上，并還需提供填色，而難以用于程序填色。區(qū)域內(nèi)一點(diǎn)的坐標(biāo)。所以，它一般只能用于人機(jī)交互種子填充算法思想前面介紹的掃描線，邊填充算法等都是直接考慮多邊形的邊，最后進(jìn)行著色，因?yàn)槎噙呅蔚倪吺侵本€，是規(guī)則的，所以計(jì)算起來也比較容易，但是對(duì)于任何不規(guī)則區(qū)域，考慮到邊的不規(guī)則性，使用掃描線類填充算法更麻煩。種子填充算法思想是只考慮邊界的顏色結(jié)構(gòu)，從被填充區(qū)域內(nèi)部任意一點(diǎn)出發(fā)，通過判斷周邊像素是不是邊界而進(jìn)行填充，直到填充完畢。區(qū)域填充的概念4連通：從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過上、下、左、右四個(gè)方向到達(dá)區(qū)域內(nèi)的任意象素；8連通：從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過上、下、左、右、左上、左下、右上、右下八個(gè)方向到達(dá)區(qū)域內(nèi)的任意象素；區(qū)域連通方式：4-connected8-connected區(qū)域連通方式對(duì)填充結(jié)果的影響4連通區(qū)域邊界4方向填充算法的填充結(jié)果4連通區(qū)域邊界8方向填充算法的填充結(jié)果簡(jiǎn)單的種子填充算法

（4連通邊界）種子像素入棧當(dāng)棧非空時(shí)，重復(fù)以下步驟：棧頂像素出棧將出棧象素置成填充色按右、上、左、下順序檢查與出棧象素相鄰的四象素，若其中某象素不在邊界上且未被置成填充色，則將其入棧，若其中某個(gè)像素值與填充色相同，說明該像素已填充過或者該像素就是邊界上的像素(當(dāng)填充色與邊界色相同時(shí))，這時(shí)像素不入棧。填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799缺點(diǎn)？假設(shè)如上多邊形，取種子點(diǎn)(3,3),按上，下，左，右這樣的方向搜索，最后像素被選中并填充的次序如圖中箭頭所示，不同的方向搜索，得到不同的結(jié)果。簡(jiǎn)單種子填充算法遞歸描述遞歸算法可實(shí)現(xiàn)如下voidFloodFill4(intx,inty,intoldColor,intnewColor){if(GetPixel(x,y)==oldColor){pDC->setpixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);}}/*endofFloodFill4() */

簡(jiǎn)單遞歸算法存在的問題

當(dāng)區(qū)域內(nèi)部某些像素的顏色為fill_color時(shí)，上述邊界填充算法可能無法正確工作。解決方法:首先建立一個(gè)與幀緩沖區(qū)對(duì)應(yīng)的臨時(shí)緩沖區(qū)，幀緩沖區(qū)中顏色為boundary_color的像素在臨時(shí)緩沖區(qū)中用0來表示，顏色不為boundary_color的像素在臨時(shí)緩沖區(qū)中用1來表示，再用上述算法在臨時(shí)緩沖區(qū)中用2進(jìn)行填充，最后在幀緩沖區(qū)中將對(duì)應(yīng)于臨時(shí)緩沖區(qū)中為2的像素填充為fill_color。該算法也可以填充有孔區(qū)域。優(yōu)缺點(diǎn)：(1)遞歸執(zhí)行，算法簡(jiǎn)單；(2)有些象素會(huì)入棧多次，棧結(jié)構(gòu)占空間較大，效率不高；(3)區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存;改進(jìn)算法方向，減少遞歸次數(shù)，提高效率。簡(jiǎn)單種子填充算法小結(jié)簡(jiǎn)單種子填充算法VC源碼建立程序的基礎(chǔ)是在前面畫直線，畫圓，畫橢圓，畫拋物線的基礎(chǔ)之上。建立在第二章第三章的基礎(chǔ)之上。比如我們使用邊界的顏色，便是我們繪制圖形的顏色。程序?qū)崿F(xiàn)達(dá)到鼠標(biāo)捕捉種子點(diǎn)，然后填充，實(shí)現(xiàn)填充任意直線和曲線圍成的區(qū)域。首先用類向?qū)г赩IEW類中建立一個(gè)鼠標(biāo)按下事件ON_WM_LBUTTONDOWN，這是MFC中的一個(gè)消息處理事件。加入代碼：簡(jiǎn)單種子填充算法VC源碼voidCDddView::OnLButtonDown(UINTnFlags,CPointpoint){

fillpoint=point; CView::OnLButtonDown(nFlags,point);}//黃色所表示的為加入的代碼，注意在類的聲明中(該類h頭文件)加入變量聲明(我們使用了MFC中定義的CPoint類)：public:CPointfillpoint;簡(jiǎn)單種子填充算法VC源碼除了建立一個(gè)鼠標(biāo)捕捉的功能外，我們還要加一個(gè)形參形式的真正的遞歸算法，在類頭文件中加入：afx_msgvoidOnFillapp(intx,inty,COLORREFfillcolor);

這樣的函數(shù)聲明，可以在protect:下面，也可以在public:下面。在類執(zhí)行文件cpp下面，加入如下函數(shù)代碼：簡(jiǎn)單種子填充算法VC源碼voidCDddView::OnFillapp(intx,inty,COLORREFfillcolor){COLORREFcurrent;current=pDC->GetPixel(x,y);if(current==color&¤t==fillcolor) return; if(current!=color&¤t!=fillcolor){pDC->SetPixel(x,y,fillcolor); CDddView::OnFillapp(x,y+1,fillcolor); CDddView::OnFillapp(x-1,y,fillcolor); CDddView::OnFillapp(x+1,y,fillcolor); CDddView::OnFillapp(x,y-1,fillcolor);} }//注意我這view類為CdddView類，所以函數(shù)名為CDddView::OnFillapp簡(jiǎn)單種子填充算法VC源碼做了前面二步準(zhǔn)備工作后，我們使用類向?qū)Ы⒁粋€(gè)菜單映射(種子填充)，在view類添加一個(gè)成員函數(shù)，添加如下代碼。voidCDddView::OnFill(){

pDC=GetDC();

//pDC已經(jīng)聲明為該類成員變量

intx=fillpoint.x; inty=fillpoint.y; CDddView::OnFillapp(x,y,fillcolor);}改進(jìn)種子填充算法VC源碼//選擇填充時(shí)候菜單映射的代碼voidCMyView::OnSeedfill(){

MessageBox("請(qǐng)選擇一封閉圖形中的一點(diǎn)");//設(shè)置bFill為bool型類成員變量

bFill=TRUE;}//bFill需要聲明成BOOL型類成員變量，初始值為FALSE改進(jìn)種子填充算法VC源碼voidCMyView::OnLButtonUp(UINTnFlags,CPointpoint){//如果程序里面加入了鼠標(biāo)交互的話，考慮改進(jìn)一下代碼

if(bFill) { bFill=FALSE; fillpoint=point; Fill(); } CView::OnLButtonUp(nFlags,point);}//fillpoint需要聲明成類成員變量改進(jìn)種子填充算法VC源碼voidCMyView::push(intx,inty){ xstack[top]=x; ystack[top]=y; top++;}voidCMyView::pop(int&x,int&y){ top--; x=xstack[top]; y=ystack[top];}//定義的是出棧入棧操作，形參形式，被調(diào)用在類的成員變量中要定義xstack和ystack，還有變量top可這樣定義：intxstack[100000];intystack[100000];inttop；在類構(gòu)造函數(shù)中賦值，top=0;改進(jìn)種子填充算法VC源碼voidCMyView::Fill(){ CDC*pDC=GetDC(); COLORREFColor;//定義變量//獲取繪圖區(qū)域背景色，這樣的話，封閉區(qū)域可以是任意顏色結(jié)構(gòu)，區(qū)分前面的種子填充算法COLORREFFilledColor=pDC->GetPixel(fillpoint.x,fillpoint.y);push(fillpoint.x,fillpoint.y); intX,Y;改進(jìn)種子填充算法VC源碼while(0<top&&top<5000000)// {

pop(X,Y); pDC->SetPixel(X,Y,fillcolor);//獲取周邊點(diǎn)的顏色值

Color=pDC->GetPixel(X,Y+1); if(Color==FilledColor) { push(X,Y+1); }改進(jìn)種子填充算法VC源碼Color=pDC->GetPixel(X+1,Y); if(Color==FilledColor) { push(X+1,Y); }

Color=pDC->GetPixel(X,Y-1); if(Color==FilledColor) { push(X,Y-1); }改進(jìn)種子填充算法VC源碼Color=pDC->GetPixel(X-1,Y); if(Color==FilledColor) { push(X-1,Y); } } //最后結(jié)束設(shè)置一下top值，避免死循環(huán)

top=0;}//這個(gè)函數(shù)需要手動(dòng)添加，在類頭文件中要加入

afx_msgvoidFill();改進(jìn)種子填充算法點(diǎn)評(píng)改進(jìn)的種子填充算法可以很好的實(shí)現(xiàn)任意區(qū)域的填充，速度執(zhí)行較快，不會(huì)像簡(jiǎn)單的種子填充算法，在VC中編譯執(zhí)行會(huì)出現(xiàn)跳出情況（當(dāng)封閉區(qū)域較大時(shí)），而且封閉的邊可以使用不同的顏色結(jié)構(gòu)，這點(diǎn)從算法中判斷是否非背景色看出來。區(qū)域填充圖案

前面介紹的區(qū)域填充算法，把區(qū)域內(nèi)部的像素全部置成同一種顏色。但在實(shí)際應(yīng)用中，有時(shí)需要用一種圖案來填充平面區(qū)域。這可以通過對(duì)前述掃描線算法中寫像素的部分稍作修改來實(shí)現(xiàn)：在確定了區(qū)域內(nèi)一像素之后，不是馬上往該像素填色，而是先查詢圖案位圖的對(duì)應(yīng)位置。若是以透明方式填充圖案，則當(dāng)圖案位圖對(duì)應(yīng)位置為1時(shí)，用前景色寫像素，否則，不改變?cè)撓袼氐闹怠６粢圆煌该鞣绞教畛鋱D案，則視圖案位圖對(duì)應(yīng)位置為1或0來決定是用前景色還是背景色去寫像素。進(jìn)行圖案填充時(shí)，在不考慮圖案旋轉(zhuǎn)的情況下，必須確定區(qū)域與圖案之間的位置關(guān)系。這可以通過把圖案原點(diǎn)與圖形區(qū)某點(diǎn)對(duì)齊的辦法來實(shí)現(xiàn)。對(duì)齊方式有兩種。一種方式是把圖案原點(diǎn)與填充區(qū)域邊界或內(nèi)部的某點(diǎn)對(duì)齊。用第一種方式填充的圖案，將隨著區(qū)域的移動(dòng)而跟著移動(dòng)，看起來很自然。對(duì)于多邊形，可取區(qū)域邊界上最左邊的頂點(diǎn)。而對(duì)于圓和橢圓這樣的具有光滑邊界的區(qū)域，則最好取區(qū)域內(nèi)部某一點(diǎn)(如中心)對(duì)應(yīng)圖案原點(diǎn)。

第二種對(duì)齊方式是整除取余方式。假定圖案是一個(gè)M×N位圖，用M×N數(shù)組存放。M、N一般比需要填充的區(qū)域的尺寸小得多。

從算法復(fù)雜性看，第二種對(duì)齊方式比較簡(jiǎn)單，并且在相鄰區(qū)域用同一圖案填充時(shí)，可以達(dá)到無縫連接的效果。但是它有一個(gè)潛在的毛病，即當(dāng)區(qū)域移動(dòng)時(shí)，圖案不會(huì)跟著移動(dòng)。其結(jié)果是區(qū)域內(nèi)的圖案變了。多邊形掃描轉(zhuǎn)換與區(qū)域填充方法聯(lián)系聯(lián)系：都是光柵圖形面著色，用于真實(shí)感圖形顯示?？上嗷マD(zhuǎn)換。多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充問題：當(dāng)給定多邊形內(nèi)一點(diǎn)為種子點(diǎn)，并用Bresenham或DDA算法將多邊形的邊界表示成八連通區(qū)域后，則多邊形的掃描轉(zhuǎn)換轉(zhuǎn)化為區(qū)域填充。區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換：若已知給定多邊形的頂點(diǎn)，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。多邊形掃描轉(zhuǎn)換與區(qū)域填充方法區(qū)別1.基本思想不同；前者是頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陣表示，后者只改變區(qū)域內(nèi)填充顏色，沒有改變表示方法。2.對(duì)邊界的要求不同前者只要求掃描線與多邊形邊界交點(diǎn)個(gè)數(shù)為偶數(shù)。后者：區(qū)域封閉，防止填充越界。3.基本的條件不同前者：從邊界頂點(diǎn)信息出發(fā)。后者：區(qū)域內(nèi)種子點(diǎn)。用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(aliasing)4.4反走樣走樣原因：1）光柵圖形的象素是離散的，是有面積的，而非數(shù)學(xué)中面積為零的點(diǎn)。2）線段、多邊形的邊界等都是連續(xù)的。因此，用離散的象素表示連續(xù)的線段或多邊形的邊界時(shí)光滑的線段就成了階梯狀或鋸齒狀。光柵圖形的走樣現(xiàn)象階梯狀邊界；圖形細(xì)節(jié)失真；狹小圖形遺失：動(dòng)畫序列中時(shí)隱時(shí)現(xiàn)，產(chǎn)生閃爍。走樣現(xiàn)象舉例不光滑(階梯狀）的圖形邊界例子：PaintBrush走樣現(xiàn)象舉例圖形細(xì)節(jié)失真走樣現(xiàn)象舉例狹小圖形的遺失與動(dòng)態(tài)圖形的閃爍反走樣概念及方法用于減少或消除走樣現(xiàn)象的技術(shù)稱為反走樣(antialiasing)提高分辨率區(qū)域采樣加權(quán)區(qū)域取樣提高分辨率把顯示器分辨率提高一倍，直線經(jīng)過兩倍的象素，鋸齒也增加一倍，但同時(shí)每個(gè)階梯的寬度也減小了一倍，所以顯示出的直線段看起來就平直光滑了一些。提高分辨率方法簡(jiǎn)單，但代價(jià)非常大。顯示器的水平、豎直分辯率各提高一倍，則顯示器的點(diǎn)距減少一倍，幀緩存容量則增加到原來的4倍，而掃描轉(zhuǎn)換同樣大小的圖元卻要花4倍時(shí)間。而且它也只能減輕而不能消除鋸齒問題另一種方法（軟件方法）：用較高的分辨率的顯示模式下計(jì)算，（對(duì)各自像素計(jì)算，再求（非）加權(quán)平均的顏色值），在較低的分辨率模式下顯示。只能減輕而不能消除鋸齒問題。軟件方法1把每個(gè)像素分為四個(gè)子像素，掃描轉(zhuǎn)換算法求得各子像素的灰度值，然后對(duì)四像素的灰度值簡(jiǎn)單平均，作為該像素的灰度值。軟件方法2設(shè)分辨率為m

n,把顯示窗口分為(2m+1)

(2n+1)個(gè)子像素，對(duì)每個(gè)子像素進(jìn)行