多邊形的掃描轉(zhuǎn)換及區(qū)域填充

多邊形的掃描轉(zhuǎn)換及區(qū)域填充第1頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-2內(nèi)容基本概念

掃描轉(zhuǎn)換矩形掃描轉(zhuǎn)換多邊形區(qū)域填充光柵圖形的反走樣第2頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-3基本概念多邊形有兩種重要的表示方法頂點(diǎn)表示用多邊形的頂點(diǎn)序列來表示多邊形。這種表示直觀、幾何意義強(qiáng)、占內(nèi)存少，易于進(jìn)行幾何變換，但由于它沒有明確指出哪些象素在多邊形內(nèi)，故不能直接用于面著色點(diǎn)陣表示用位于多邊形內(nèi)的象素集合來刻畫多邊形。這種表示丟失了許多幾何信息，但便于幀緩沖器表示圖形，是面著色所需要的圖形表示形式。第3頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-4基本概念多邊形的掃描轉(zhuǎn)換把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個象素，并給幀緩沖器內(nèi)的各個對應(yīng)象素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。 區(qū)域填充（演示）

是指先將在點(diǎn)陣表示的多邊形區(qū)域內(nèi)的一點(diǎn)（稱為種子點(diǎn)）賦予指定的顏色和灰度，然后將這種顏色和灰度擴(kuò)展到整個區(qū)域內(nèi)的過程。第4頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-5掃描轉(zhuǎn)換矩形問題：矩形是簡單的多邊形，那么為什么要單獨(dú)處理矩形？應(yīng)用非常多，特別是窗口系統(tǒng)比一般多邊形可簡化計算共享邊界如何處理？左閉右開下閉上開屬于誰？第5頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-6掃描轉(zhuǎn)換矩形方法voidFillRectangle(Rectangle*rect,intcolor) {intx,y; for(y=rect->ymin;y<=rect->ymax;y++) for(x=rect->xmin;x<=rect->xmax;x++) PutPixel(x,y,color); }/*endofFillRectangle() */第6頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-7掃描轉(zhuǎn)換多邊形凸多邊形任意兩頂點(diǎn)間的連線均在多邊形內(nèi)凹多邊形任意兩頂點(diǎn)間的連線有不在多邊形內(nèi)的部分含內(nèi)環(huán)的多邊形多邊形內(nèi)再套有多邊形，多邊形內(nèi)的多邊形也叫內(nèi)環(huán)，內(nèi)環(huán)之間不能相交第7頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-8掃描轉(zhuǎn)換多邊形幾種方法逐點(diǎn)判斷算法逐個判斷繪圖窗口內(nèi)的像素，確定它們是否在多邊形區(qū)域內(nèi)部，從而求出位于多邊形區(qū)域內(nèi)的像素的集合。掃描線算法（要求重點(diǎn)掌握）利用相鄰像素之間的連貫性，避免逐點(diǎn)判斷和反復(fù)求交運(yùn)算。邊緣填充算法利用求余運(yùn)算，來達(dá)到填充的目的。第8頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-9逐點(diǎn)判斷算法voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;

for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++) if(IsInside(P,x,y)) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP() */#defineMAX100Typedefstruct{intPolygonNum;//多邊形頂點(diǎn)個數(shù)

Pointvertexces[MAX]//多邊形頂點(diǎn)數(shù)組

}Polygon//多邊形結(jié)構(gòu)第9頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-10逐點(diǎn)判斷算法逐個判斷繪圖窗口內(nèi)的像素如何判斷點(diǎn)在多邊形的內(nèi)外關(guān)系？射線法弧長法第10頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-11點(diǎn)關(guān)于多邊形內(nèi)外關(guān)系的判斷射線法（演示）如果從一點(diǎn)發(fā)出的射線與多邊形邊界的交點(diǎn)個數(shù)為奇數(shù)，則該點(diǎn)位于多邊形之內(nèi)，否則位于多邊形之外。(a)p1p2p3p4p1(b)p2p3(c)p1p2p3p4(d)p5p1p2p3p4p0p1p2p3p4U0U1U2U3第11頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-12點(diǎn)關(guān)于多邊形內(nèi)外關(guān)系的判斷弧長法（累計角度法)步驟從v點(diǎn)向多邊形P各頂點(diǎn)發(fā)出射線，形成有向角計算有向角的和，得出結(jié)論（演示）第12頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-13逐點(diǎn)判斷算法-小結(jié)逐點(diǎn)判斷的算法雖然程序簡單，但不可取。原因是速度太慢，效率低。主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得幾十萬甚至幾百萬個象素都要一一判別，每次判別又要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)很多時間。第13頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-14掃描線算法處理對象非自交多邊形（邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)）第14頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-15掃描線算法掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對象素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少計算量和提高速度的目的。開發(fā)和利用相鄰象素之間的連貫性是光柵圖形算法研究的重要內(nèi)容。掃描轉(zhuǎn)換算法綜合利用了區(qū)域的連貫性、掃描線的連貫性和邊的連貫性等三種形式的連貫性。第15頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-16掃描線算法基本思想對于一個給定的多邊形，用一組水平或垂直的掃描線進(jìn)行掃描，分別求出每條掃描線與多邊形的交點(diǎn)，這些交點(diǎn)將掃描線分割為相間排列的落在多邊形內(nèi)和多邊形外的線段，將落在多邊形內(nèi)的所有線段上的每個像素點(diǎn)賦以給定的多邊形填充色。利用相鄰象素之間的連貫性填充每一條掃描線位于多邊形內(nèi)部的區(qū)段。第16頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-17區(qū)域的連貫性設(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。屏幕上位于y=yik和y=yik+1兩條掃描線之間的長方形區(qū)域被多邊形P的邊分割成若干梯形（三角形可看作其中一底邊長為零的梯形），它們具有下列性質(zhì)：第17頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-18區(qū)域的連貫性梯形的兩底邊分別在y=yik和y=yik+1（yik≥yik+1)兩條掃描線上，腰在多邊形P的邊上或在顯示屏幕的邊界上。這些梯形可分為兩類：一類位于多邊形P的內(nèi)部；另一類在多邊形P的外部。兩類梯形在長方形區(qū)域{yik,yik+1}內(nèi)相間的排列，即相鄰的兩梯形必有一個在多邊形P內(nèi)，另一個在P外。第18頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-19區(qū)域的連貫性結(jié)論：根據(jù)這些性質(zhì)，實(shí)際上只需知道該長方形區(qū)域內(nèi)任一梯形內(nèi)一點(diǎn)關(guān)于多邊形P的內(nèi)外關(guān)系后，即可確定區(qū)域內(nèi)所有梯形關(guān)于P的內(nèi)外關(guān)系。第19頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-20掃描線的連貫性設(shè)e為一整數(shù)，yi0≥e≥yin。若掃描線y=e與多邊形P的Pi-1Pi相交，則記其交點(diǎn)的橫坐標(biāo)為xei。以上交點(diǎn)的橫坐標(biāo)遞增排序得到的序列稱為交點(diǎn)序列。交點(diǎn)序列具有如下性質(zhì)：第20頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-21掃描線的連貫性（1）交點(diǎn)個數(shù)為偶數(shù)。（2）交點(diǎn)之間的區(qū)段按交替的順序依次出現(xiàn)在多邊形內(nèi)部和外部。以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。第21頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-22邊的連貫性由掃描線y=e和多邊形的所有交點(diǎn)遞推出掃描線y=d=e+1與多邊形各邊的交點(diǎn)。邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。掃描線

y=e(x1,e)(x1+1/m,e+1)

y=d=e+1利用邊的連貫性求交點(diǎn)q0q3q1q2=xy第22頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-23奇點(diǎn)的處理當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)時，則稱該交點(diǎn)為奇點(diǎn)。以上所述多邊形的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形P的邊界的交點(diǎn)個數(shù)都是偶數(shù)。但是如果把每一奇點(diǎn)簡單地計為一個交點(diǎn)或者簡單地計為兩個交點(diǎn)，都可能出現(xiàn)奇數(shù)個交點(diǎn)。那么如何保證交點(diǎn)數(shù)為偶數(shù)呢？

y=eq0q3q1q2=第23頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-24奇點(diǎn)的處理若奇點(diǎn)做一個交點(diǎn)處理，則情況A，交點(diǎn)個數(shù)不是偶數(shù)。若奇點(diǎn)做兩個交點(diǎn)處理，則情況B，交點(diǎn)個數(shù)不是偶數(shù)。第24頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-25奇點(diǎn)的處理多邊形P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。如果(yi-1-yi)(yi+1-yi)≥0，則稱頂點(diǎn)Pi為極值點(diǎn)；否則稱Pi為非極值點(diǎn)。規(guī)定：奇點(diǎn)是極值點(diǎn)時，該點(diǎn)按兩個交點(diǎn)計算，否則按一個交點(diǎn)計算。奇點(diǎn)的預(yù)處理：第25頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-26交點(diǎn)取整規(guī)則要求：使生成的像素全部位于多邊形之內(nèi)由直線的掃描轉(zhuǎn)換算法（如中點(diǎn)算法或DDA算法）求出的表示邊的像素雖然和交點(diǎn)最靠近，卻無法保證這些像素都落在多邊形區(qū)域的內(nèi)部．第26頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-27交點(diǎn)取整規(guī)則假設(shè)某非水平邊與掃描線y＝e相交，交點(diǎn)的橫坐標(biāo)記為x，則有如下幾種規(guī)則：（1）x為小數(shù)，即交點(diǎn)(x，e)落于掃描線y＝e上兩個相鄰像素之間X為小數(shù)第27頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-28交點(diǎn)取整規(guī)則（2）交點(diǎn)(x，e)正好落于像素點(diǎn)上邊界上象素的取舍問題，避免填充擴(kuò)大化。按照前面所介紹的對多邊形區(qū)域邊界的處理方法，若(x，e)位于多邊形左邊上，見圖(a)，則將它看作屬于多邊形；若(x，e)在多邊形右邊上，見圖(b)．則它不屬于多邊形。左閉右開的原則（x，e）落于像素上的情形第28頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-29交點(diǎn)取整規(guī)則（3）落在像素點(diǎn)上交點(diǎn)(x，e)為多邊形的頂點(diǎn)掃描線與多邊形的頂點(diǎn)相交時，交點(diǎn)的取舍，保證交點(diǎn)正確配對。處理方法：將多邊形的每條邊看成是下端閉上端開第29頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-30掃描線算法-數(shù)據(jù)結(jié)構(gòu)

為了提高效率，在處理一條掃描線時，僅對與它相交的多邊形的邊進(jìn)行求交運(yùn)算?；钚赃叄╝ctiveedge)與當(dāng)前掃描線相交的邊；活性邊表（AET--Activeedgetable)將活性邊按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個鏈表中，它記錄了多邊形邊沿掃描線的交點(diǎn)序列。每條掃描線對應(yīng)一個活性邊表。只需對當(dāng)前掃描線的活性邊表作更新，即可得到下一條掃描線的活性邊表。第30頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-31掃描線算法-數(shù)據(jù)結(jié)構(gòu)(掃描線6的活性邊表)AET(掃描線7的活性邊表)AET第31頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-32掃描線算法-數(shù)據(jù)結(jié)構(gòu)如何計算下一條掃描線與邊的交點(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=(-b(yi+1)-c)/a=xi-b/axi+1=xi+Δx（Δx=-b/a為常數(shù)

)活動邊表中需要存放的信息x：當(dāng)前掃描線與邊的交點(diǎn)Δx＝-b/a：從當(dāng)前掃描線到下一條掃描線之間的x增量ymax：邊所交的最高掃描線，即邊的上端點(diǎn)的y坐標(biāo)；第32頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-33掃描線算法-數(shù)據(jù)結(jié)構(gòu)為了方便邊的活性邊表（AET）的更新，建立另一個表，即邊表（ET----EdgeTable）邊表中需要存放的信息x：掃描線與該邊的初始交點(diǎn)，即邊的下端點(diǎn)的x坐標(biāo)Δx：x的增量ymax：該邊的最大y值，即邊的上端點(diǎn)的y坐標(biāo)；邊表ET是按邊的下端點(diǎn)的y坐標(biāo)對非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)的值等于i的邊歸入第i類。同一類中，各邊按x值（x值相等時，按Δx的值）遞增的順序排列成行。第33頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-34掃描線算法-數(shù)據(jù)結(jié)構(gòu)P6P1ET第34頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-35掃描線算法-數(shù)據(jù)結(jié)構(gòu)小結(jié)：算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊表ET（EdgeTable）和活性邊表AET（ActiveEdgeList）兩部分組成。邊表ET和活性邊表AET中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個域組成：x：在ET中表示邊的下端點(diǎn)的x坐標(biāo)，在AET中則表示邊與掃描線的交點(diǎn)的坐標(biāo)；Δx：邊的斜率的倒數(shù)；ymax：邊的上端點(diǎn)的y坐標(biāo)；next：指向下一條邊的指針。第35頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-36掃描線算法-算法實(shí)現(xiàn)步驟1.建立ET；2.將掃描線縱坐標(biāo)y的初值置為ET中非空元素的最小序號（如前圖所示，y=1）；3.置AET為空；4.執(zhí)行下列步驟直至ET和AET都為空：如果ET中的第y類非空，則將其中的所有邊取出并插入AET中；如果有新的邊插入AET，則對AET中各邊排序；對AET中的邊兩兩配對，將每對邊中x坐標(biāo)按規(guī)則取整，獲得有效的填充區(qū)段，再填充；將當(dāng)前掃描線縱坐標(biāo)y值遞增1，即y=y+1；對AET中滿足y=ymax邊刪去（因?yàn)槊織l邊被看作下閉上開的）；對AET中剩下的每一條邊的x遞增Δx，即x=x+Δx。第36頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-37掃描線算法-算法實(shí)現(xiàn)步驟voidpolyfill(polygon,color)intcolor;多邊形polygon;{for(各條掃描線i)

{初始化邊表頭指針ET[i]；

把ymin=i的邊放進(jìn)邊表ET[i];

}

y=最低掃描線號；

初始化活性邊表AET為空；

for(各條掃描線i)

{把邊表ET[i]中的邊結(jié)點(diǎn)用插入排序法插入AET表，使之按x坐標(biāo)遞增順序排列；

遍歷AET表，把配對交點(diǎn)區(qū)間(左閉右開)上的象素(x,y)，用putpixel(x,y,color)改寫象素顏色值；

遍歷AET表，把ymax=i的結(jié)點(diǎn)從AET表中刪除，并把ymax>i結(jié)點(diǎn)的x值遞增Δx；

}}/*polyfill*/第37頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-38多邊形掃描線算法分析100246810122468P3P2P1P4P5P6e3e4e2e1e5e6^^^^-2.579^1.511^01311^029^1.575-2.573012345677ETymaxx△xe1e2e6e5e3e4第38頁，課件共62頁，創(chuàng)作于2023年2月100246810122468P3P2P1P4P5P6e3e4e2e1e5e6^^^^-2.579^1.511^01311^029^1.575-2.573012345677ETymaxx△xe1e2e6e5e3e4

(11.5,10)->(13,10)AET=空y=1AET=-2.573空1.575(7,1)->(7,1)y=2AET=-2.54.53空1.58.55(4.5,2)->(8.5,2)y=3AET=029空1.5105(2,3)->(10,3)y=4AET=029空1.511.55(2,4)->(11.5,4)y=5AET=029空13(2,5)->(13,5)y=6AET=029空01311(2,6)->(13,6)y=7AET=029-2.579(2,7)->(7,7)1.5711空01311(7,7)->(13,7)y=8AET=029-2.54.59(2,8)->(4.5,8)1.58.51101311(8.5,8)->(13,8)空y=9AET=空y=10AET=1.511.51101311空y=11AET=空11011101.511130(10,9)->(13,9)第39頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-40掃描線算法與逐點(diǎn)判斷法的比較掃描線算法的數(shù)據(jù)結(jié)構(gòu)和算法本身都比逐點(diǎn)判斷法復(fù)雜得多。掃描線算法利用邊的連貫性以加速交點(diǎn)的計算，利用ET以排除盲目求交。掃描線算法利用掃描線的連貫性以避免逐點(diǎn)判別，所以速度要比逐點(diǎn)判斷算法快得多。第40頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-41區(qū)域填充區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形,它是相互連通的一組像素的集合。區(qū)域填充

是對區(qū)域重新著色的過程。是指先將區(qū)域的一點(diǎn)（稱為種子點(diǎn)）賦予指定的顏色，然后將該顏色擴(kuò)展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的。

第41頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-42區(qū)域填充區(qū)域的表示形式1.內(nèi)點(diǎn)表示枚舉出給定區(qū)域內(nèi)所有像素內(nèi)部的所有像素著同一個顏色邊界像素著與內(nèi)部像素不同的顏色2.邊界表示枚舉出給定區(qū)域所有邊界上像素邊界上的所有像素著同一顏色內(nèi)部像素著與邊界像素不同的顏色區(qū)域的內(nèi)點(diǎn)表示和邊界表示第42頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-43區(qū)域填充區(qū)域填充要求區(qū)域是連通的區(qū)域的連通形式4連通8連通第43頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-44區(qū)域填充4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對邊界有要求對邊界的要求第44頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-45種子填充算法-內(nèi)點(diǎn)表示區(qū)域設(shè)G為一內(nèi)點(diǎn)表示的區(qū)域，(x,y)為區(qū)域內(nèi)一點(diǎn)，old_color為G的原色?，F(xiàn)取(x,y)為種子點(diǎn)對區(qū)域G進(jìn)行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個區(qū)域G都置為同樣的顏色。步驟：種子象素入棧，當(dāng)棧非空時，執(zhí)行如下三步操作（1）棧頂象素出棧（2）將出棧象素置成多邊形色（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個象素，若其中某個象素不在邊界上且未置成多邊形色，則把該象素入棧。 第45頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-46種子填充算法-內(nèi)點(diǎn)表示區(qū)域例：多邊形由P0P1P2P3P4構(gòu)成：P0(1,5)、P1(5,5)、P2(7,3)、P3(7,1)、P4(1,1)設(shè)種子點(diǎn)為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)第46頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-47種子填充算法-內(nèi)點(diǎn)表示區(qū)域遞歸算法可實(shí)現(xiàn)如下voidFloodFill4(intx,inty,intoldColor,intnewColor){intcolor;color=GetPixel（x，y）;if（color==oldColor）{PutPixel(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);}

第47頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-48種子填充算法-邊界表示區(qū)域步驟：種子象素入棧，當(dāng)棧非空時，執(zhí)行如下三步操作（1）棧頂象素出棧（2）將出棧象素置成多邊形色（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個象素，若其中某個象素不在邊界上且未置成多邊形色，則把該象素入棧。 填充填充第48頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-49種子填充算法-邊界表示區(qū)域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor; color=GetPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { PutPixel(x,y,newColor); BoundaryFill4(x,y+1,oldColor,newColor); BoundaryFill4(x,y-1,oldColor,newColor); BoundaryFill4(x-1,y,oldColor,newColor); BoundaryFill4(x+1,y,oldColor,newColor); }}遞歸算法可實(shí)現(xiàn)如下第49頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-50種子填充算法-邊界表示區(qū)域0123454321(3,2)(2,2)(3,3)(4,2)(3,1)(2,1)(4,1)(4,2)(2,2)(1,2)(2,3)(3,3)第50頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-51種子填充算法

該算法也可以填充有孔區(qū)域。缺點(diǎn)有些像素會入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時費(fèi)內(nèi)存。改進(jìn)算法:減少遞歸次數(shù)，提高效率。解決方法：用掃描線填充算法第51頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及區(qū)域填充第五章-52掃描線填充算法目標(biāo)減少遞歸層次適用范圍內(nèi)點(diǎn)表示的4連通區(qū)域算法思想在任意不間斷區(qū)間中只取一個種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復(fù)進(jìn)行這個過程，直到所保存的個區(qū)段都填充完畢。第52頁，課件共62頁，創(chuàng)作于2023年2月多邊形的掃描轉(zhuǎn)換及