掃描線填充算法講解

1、掃描線算法(Scan-LineFilling)掃描線算法適合對(duì)矢量圖形進(jìn)行區(qū)域填充，只需要直到多邊形區(qū)域的幾何位置，不需要指定種子點(diǎn)，適合計(jì)算機(jī)自動(dòng)進(jìn)行圖形處理的場(chǎng)合使用，比如電腦游戲和三維CAD軟件的渲染等等。對(duì)矢量多邊形區(qū)域填充，算法核心還是求交。計(jì)算幾何與圖形學(xué)有關(guān)的幾種常用算法一文給出了判斷點(diǎn)與多邊形關(guān)系的算法一一掃描交點(diǎn)的奇偶數(shù)判斷算法，利用此算法可以判斷一個(gè)點(diǎn)是否在多邊形內(nèi)，也就是是否需要填充，但是實(shí)際工程中使用的填充算法都是只使用求交的思想，并不直接使用這種求交算法。究其原因，除了算法效率問題之外，還存在一個(gè)光柵圖形設(shè)備和矢量之間的轉(zhuǎn)換問題。比如某個(gè)點(diǎn)位于非?？拷吔绲呐R界位置，

2、用矢量算法判斷這個(gè)點(diǎn)應(yīng)該是在多邊形內(nèi)，但是光柵化后，這個(gè)點(diǎn)在光柵圖形設(shè)備上看就有可能是在多邊形外邊(矢量點(diǎn)沒有大小概念，光柵圖形設(shè)備的點(diǎn)有大小概念)，因此，適用于矢量圖形的填充算法必須適應(yīng)光柵圖形設(shè)備。2.1掃描線算法的基本思想掃描線填充算法的基本思想是：用水平掃描線從上到下(或從下到上)掃描由多條首尾相連的線段構(gòu)成的多邊形，每根掃描線與多邊形的某些邊產(chǎn)生一系列交點(diǎn)。將這些交點(diǎn)按照x坐標(biāo)排序，將排序后的點(diǎn)兩兩成對(duì)，作為線段的兩個(gè)端點(diǎn)，以所填的顏色畫水平直線。多邊形被掃描完畢后，顏色填充也就完成了。掃描線填充算法也可以歸納為以下4個(gè)步驟：(1)求交，計(jì)算掃描線與多邊形的交點(diǎn)(2)交點(diǎn)排序，對(duì)第2

3、步得到的交點(diǎn)按照x值從小到大進(jìn)行排序；(3)顏色填充，對(duì)排序后的交點(diǎn)兩兩組成一個(gè)水平線段，以畫線段的方式進(jìn)行顏色填充；(4)是否完成多邊形掃描？如果是就結(jié)束算法，如果不是就改變掃描線，然后轉(zhuǎn)第1步繼續(xù)處理；整個(gè)算法的關(guān)鍵是第1步，需要用盡量少的計(jì)算量求出交點(diǎn)，還要考慮交點(diǎn)是線段端點(diǎn)的特殊情況，最后，交點(diǎn)的步進(jìn)計(jì)算最好是整數(shù)，便于光柵設(shè)備輸出顯示。對(duì)于每一條掃描線，如果每次都按照正常的線段求交算法進(jìn)行計(jì)算，則計(jì)算量大，而且效率底下，如圖（6）所示：圖（6）多邊形與掃描線示意圖觀察多邊形與掃描線的交點(diǎn)情況，可以得到以下兩個(gè)特點(diǎn)：（1）每次只有相關(guān)的幾條邊可能與掃描線有交點(diǎn)，不必對(duì)所有的邊進(jìn)行求交計(jì)

4、算；（2）相鄰的掃描線與同一直線段的交點(diǎn)存在步進(jìn)關(guān)系，這個(gè)關(guān)系與直線段所在直線的斜率有關(guān)；第一個(gè)特點(diǎn)是顯而易見的，為了減少計(jì)算量，掃描線算法需要維護(hù)一張由活動(dòng)邊'組成的表，稱為活動(dòng)邊表（AET）例如掃描線4的活動(dòng)邊表”由P1P2和P3P4兩條邊組成，而掃描線7的活動(dòng)邊表”由P1P2、P6P1、P5P6和P4P5四條邊組成。第二個(gè)特點(diǎn)可以進(jìn)一步證明，假設(shè)當(dāng)前掃描線與多邊形的某一條邊的交點(diǎn)已經(jīng)通過直線段求交算法計(jì)算出來，得到交點(diǎn)的坐標(biāo)為（x,y）,則下一條掃描線與這條邊的交點(diǎn)不需要再求交計(jì)算，通過步進(jìn)關(guān)系可以直接得到新交點(diǎn)坐標(biāo)為（x+0y+1）。前面提到過，步進(jìn)關(guān)系以是個(gè)常量，與直線的斜率

5、有關(guān)，下面就來推導(dǎo)這個(gè)Axo假設(shè)多邊形某條邊所在的直線方程是：ax+by+c=0,掃描線yi和下一條掃描線yi+i與該邊的兩個(gè)交點(diǎn)分別是（xi,yi）和（xi+i,yi+i）,則可得到以下兩個(gè)等式：axi+byi+c=0（等式1）axi+i+byi+i+c=0（等式2）由等式i可以得到等式3:xi=-（byi+c）/a（等式3）同樣，由等式2可以得到等式4:xi+i=-（byi+i+c）/a（等式4）由等式4-等式3可得到xi+ixi=-b（yi+i-yi）/a由于掃描線存在yi+i=yi+i的關(guān)系，將代入上式即可得到：xi+i-xi=-b/a即&=-b/a,是個(gè)常量（直線斜率的倒數(shù)）

6、?；顒?dòng)邊表”是掃描線填充算法的核心，整個(gè)算法都是圍繞者這張表進(jìn)行處理的。要完整的定義活動(dòng)邊表”，需要先定義邊的數(shù)據(jù)結(jié)構(gòu)。每條邊都和掃描線有個(gè)交點(diǎn)，掃描線填充算法只關(guān)注交點(diǎn)的x坐標(biāo)。每當(dāng)處理下一條掃描線時(shí)，根據(jù)五直接計(jì)算出新掃描線與邊的交點(diǎn)x坐標(biāo)，可以避免復(fù)雜的求交計(jì)算。一條邊不會(huì)一直待在活動(dòng)邊表”中，當(dāng)掃描線與之沒有交點(diǎn)時(shí)，要將其從活動(dòng)邊表”中刪除，判斷是否有交點(diǎn)的依據(jù)就是看掃描線y是否大于這條邊兩個(gè)端點(diǎn)的y坐標(biāo)值，為此，需要記錄邊的y坐標(biāo)的最大值。根據(jù)以上分析，邊的數(shù)據(jù)結(jié)構(gòu)可以定義如下：65 typedefstructtagEDGE66 67 doublexi;68 doubledx;69

7、intymax;74EDGE根據(jù)EDGE的定義，掃描線4和掃描線7的活動(dòng)邊表”就分別如圖（7）和圖（8）所示：4A1.20.2君1LD工0£圖（7）掃描線4的活動(dòng)邊表-1.&0.28A4.58AL505班)11.40810圖（8）掃描線7的活動(dòng)邊表前面提到過，掃描線算法的核心就是圍繞活動(dòng)邊表（AET）”展開的，為了方便活性邊表的建立與更新，我們?yōu)槊恳粭l掃描線建立一個(gè)新邊表（NET）”，存放該掃描線第一次出現(xiàn)的邊。當(dāng)算法處理到某條掃描線時(shí)，就將這條掃描線的新邊表”中的所有邊逐一插入到活動(dòng)邊表”中。新邊表”通常在算法開始時(shí)建立，建立新邊表”的規(guī)則就是：如果某條邊的較低端點(diǎn)（y坐標(biāo)

8、較小的那個(gè)點(diǎn)）的y坐標(biāo)與掃描線y相等，則該邊就是掃描線y的新邊，應(yīng)該加入掃描線y的新邊表”。上例中各掃描線的新邊表”如下圖所示：P3P4P2Ps圖（9）各掃描線的新邊表討論完活動(dòng)邊表（AET）”和新邊表（NET）”，就可以開始算法的具體實(shí)現(xiàn)了,但是在進(jìn)一步詳細(xì)介紹實(shí)現(xiàn)算法之前，還有以下幾個(gè)關(guān)鍵的細(xì)節(jié)問題需要明確：（1）多邊形頂點(diǎn)處理在對(duì)多邊形的邊進(jìn)行求交的過程中，在兩條邊相連的頂點(diǎn)處會(huì)出現(xiàn)一些特殊情況，因?yàn)榇藭r(shí)兩條邊會(huì)和掃描線各求的一個(gè)交點(diǎn)，也就是說，在頂點(diǎn)位置會(huì)出現(xiàn)兩個(gè)交點(diǎn)。當(dāng)出現(xiàn)這種情況的時(shí)候，會(huì)對(duì)填充產(chǎn)生影響，因?yàn)樘畛涞倪^程是成對(duì)選擇交點(diǎn)的過程，錯(cuò)誤的計(jì)算交點(diǎn)個(gè)數(shù)，會(huì)造成填充異常。假設(shè)多

9、邊形按照頂點(diǎn)P1、P2和P3的順序產(chǎn)生兩條相鄰的邊，P2就是所說的頂點(diǎn)。多邊形的頂點(diǎn)一般有四種情況，如圖（10）所展示的那樣，分別被稱為左頂點(diǎn)、右頂點(diǎn)、上頂點(diǎn)和下頂點(diǎn)：（d）左頂左FlCd）下頂點(diǎn)左頂點(diǎn)一一P1、右頂點(diǎn)P1、上頂點(diǎn)P1、下頂點(diǎn)P1、圖（10）多邊形頂點(diǎn)的四種類型P2和P3的y坐標(biāo)滿足條件：y1<y2<y3;P2和P3的y坐標(biāo)滿足條件：y1>y2>y3;P2和P3的y坐標(biāo)滿足條件：y2>y1&&y2>y3;P2和P3的y坐標(biāo)滿足條件：y2<y1&&y2<y3;對(duì)于左頂點(diǎn)和右頂點(diǎn)的情況，如果不做特殊處理

10、會(huì)導(dǎo)致奇偶奇數(shù)錯(cuò)誤，常采用的修正方法是修改以頂點(diǎn)為終點(diǎn)的那條邊的區(qū)間，將頂點(diǎn)排除在區(qū)間之外，也就是刪除這條邊的終點(diǎn)，這樣在計(jì)算交點(diǎn)時(shí)，就可以少計(jì)算一個(gè)交點(diǎn)，平衡和交點(diǎn)奇偶個(gè)數(shù)。結(jié)合前文定義的邊”數(shù)據(jù)結(jié)構(gòu)：EDGE,只要將該邊的ymax修改為ymaxT就可以了。對(duì)于上頂點(diǎn)和下頂點(diǎn)，一種處理方法是將交點(diǎn)計(jì)算做0個(gè)，也就是修正兩條邊的區(qū)間，將交點(diǎn)從兩條邊中排除；另一種處理方法是不做特殊處理，就計(jì)算2個(gè)交點(diǎn)，這樣也能保證交點(diǎn)奇偶個(gè)數(shù)平衡。(2)水平邊的處理水平邊與掃描線重合，會(huì)產(chǎn)生很多交點(diǎn)，通常的做法是將水平邊直接畫出(填充)，然后在后面的處理中就忽略水平邊，不對(duì)其進(jìn)行求交計(jì)算。(3)如何避免填充越過

11、邊界線邊界像素的取舍問題也需要特別注意。多邊形的邊界與掃描線會(huì)產(chǎn)生兩個(gè)交點(diǎn)，填充時(shí)如果對(duì)兩個(gè)交點(diǎn)以及之間的區(qū)域都填充，容易造成填充范圍擴(kuò)大，影響最終光柵圖形化顯示的填充效果。為此，人們提出了左閉右開”的原則，簡(jiǎn)單解釋就是，如果掃描線交點(diǎn)是1和9,則實(shí)際填充的區(qū)間是1,9),即不包括x坐標(biāo)是9的那個(gè)點(diǎn)。2.2掃描線算法實(shí)現(xiàn)掃描線算法的整個(gè)過程都是圍繞活動(dòng)邊表(AET)”展開的，為了正確初始化活動(dòng)邊表”，需要初始化每條掃描線的新邊表(NET)”，首先定義新邊表”的數(shù)據(jù)結(jié)構(gòu)。定義新邊表”為一個(gè)數(shù)組，數(shù)組的每個(gè)元素存放對(duì)應(yīng)掃描線的所有新邊”。因此定義新邊表”如下：510std:vector<st

12、d:list<EDGE>>sINet(ymax-ymin+1);ymax和ymin是多邊形所有頂點(diǎn)中y坐標(biāo)的最大值和最小值，用于界定掃描線的范圍。slNet中的第一個(gè)元素對(duì)應(yīng)的是ymin所在的掃描線，以此類推，最后一個(gè)元素是ymax所在的掃描線。在開始對(duì)每條掃描線處理之前，需要先計(jì)算出多邊形的ymax和ymin并初始化新邊表”：503voidScanLinePolygonFill(constPolygon&py,intcolor)504505assert(py.IsValid();506507intymin=0;508intymax=0;509GetPolygonMi

13、nMax(py,ymin,ymax);510std:vector<std:list<EDGE>>sINet(ymax-ymin+1);511InitScanLineNewEdgeTable(slNet,py,ymin,ymax);512/PrintNewEdgeTable(slNet);513HorizonEdgeFill(py,color);/水平邊直接畫線填充514ProcessScanLineFill(slNet,ymin,ymax,color);515InitScanLineNewEdgeTable。函數(shù)根據(jù)多邊形的頂點(diǎn)和邊的情況初始化新邊表”，實(shí)現(xiàn)過程中體現(xiàn)了

14、對(duì)左頂點(diǎn)和右頂點(diǎn)的區(qū)間修正原則：315voidInitScanLineNewEdgeTable(std:vector<std:list<EDGE>>&slNet,319for(inti=0;i<py.GetPolyCount();i+)320321constPoint&ps=py.ptsi;322constPoint&pe=py.pts(i+1)%py.GetPolyCount();323constPoint&pss=py.pts(i-1+py.GetPolyCount()316constPolygon&py,intymin

15、,intymax)317318EDGEe;%py.GetPolyCount();324constPoint&pee=py.pts(i+2)%py.GetPolyCount();325332if(pe.y!=ps.y)/不處理水平線333334e.dx=double(pe.x-ps.x)/double(pe.y-ps.y);335if(pe.y>ps.y)336337e.xi=ps.x;338if(pee.y>=pe.y)339e.ymax=pe.y-1;340else341e.ymax=pe.y;342343slNetps.y-ymin.push_front(e);3443

16、45else346347e.xi=pe.x;348if(pss.y>=ps.y)349e.ymax=ps.y-1;350else351e.ymax=ps.y;352slNetpe.y-ymin.push_front(e);353一354355多邊形的定義Polygon和本系列第一篇計(jì)算幾何與圖形學(xué)有關(guān)的幾種常用算法一文中的定義一致，此處就不再重復(fù)說明。算法通過遍歷所有的頂點(diǎn)獲得邊的信息，然后根據(jù)與此邊有關(guān)的前后兩個(gè)頂點(diǎn)的情況確定此邊的ymax是否需要-1修正。ps和pe分別是當(dāng)前處理邊的起點(diǎn)和終點(diǎn)，pss是起點(diǎn)的前一個(gè)相鄰點(diǎn)，pee是終點(diǎn)的后一個(gè)相鄰點(diǎn)，pss和pee用于輔助判斷ps和p

17、e兩個(gè)點(diǎn)是否是左頂點(diǎn)或右頂點(diǎn)，然后根據(jù)判斷結(jié)果對(duì)此邊的ymax進(jìn)行-1修正，算法實(shí)現(xiàn)非常簡(jiǎn)單，注意與掃描線平行的邊是不處理的，因?yàn)樗竭呏苯釉贖orizonEdgeFill()函數(shù)中填充了。ProcessScanLineFill()函數(shù)開始對(duì)每條掃描線進(jìn)行處理，對(duì)每條掃描線的處理有四個(gè)操作，如下代碼所示，四個(gè)操作分別被封裝到四個(gè)函數(shù)中：467voidProcessScanLineFill(std:vector<std二list<EDGE>>&slNet,468intymin,intymax,intcolor)469470std:list<EDGE>a

18、et;471472for(inty=ymin;y<=ymax;y+)473474InsertNetListToAet(slNety-ymin,aet);475FillAetScanLine(aet,y,color);476/刪除非活動(dòng)邊477RemoveNonActiveEdgeFromAet(aet,y);478/更新活動(dòng)邊表中每項(xiàng)的xi值，并根據(jù)xi重新排序479UpdateAndResortAet(aet);480)481)InsertNetListToAet()函數(shù)負(fù)責(zé)將掃描線對(duì)應(yīng)的所有新邊插入到aet中，插入操作到保證aet還是有序表，應(yīng)用了插入排序的思想，實(shí)現(xiàn)簡(jiǎn)單，此處不多解

19、釋。FillAetScanLine()函數(shù)執(zhí)行具體的填充動(dòng)作，它將aet中的邊交點(diǎn)成對(duì)取出組成填充區(qū)間，然后根據(jù)左閉右開”的原則對(duì)每個(gè)區(qū)間填充，實(shí)現(xiàn)也很簡(jiǎn)單，此處不多解釋。RemoveNonActiveEdgeFromAet。函數(shù)負(fù)責(zé)將對(duì)下一條掃描線來說已經(jīng)不是活動(dòng)邊”的邊從aet中刪除，刪除的條件就是當(dāng)前掃描線y與邊的ymax相等，如果有多條邊滿足這個(gè)條件，則一并全部刪除：439boolIsEdgeOutOfActive(EDGEe,inty)440441return(e.ymax=y);442)443444voidRemoveNonActiveEdgeFromAet(std二list<

20、;EDGm&aet,inty)445446aet.remove_if(std二bind2nd(std二ptr_fun(IsEdgeOutOfActive),y);447)UpdateAndResortAet()函數(shù)更新邊表中每項(xiàng)的xi值，就是根據(jù)掃描線的連貫性用dx對(duì)其進(jìn)行修正，并且根據(jù)xi從小到大的原則對(duì)更新后的aet表重新排序:449voidUpdateAetEdgeInfo(EDGESe)450451e.xi+=e.dx;452)453454boolEdgeXiComparator(EDGEkel,EDGE&e2)455456return(el.xi<=e2.xi)

21、;457)458459voidUpdateAndResortAet(std:list<EDGE>&aet)460461/更新xi462for_each(aet.begin(),aet.end(),UpdateAetEdgeInfo);463/根據(jù)xi從小到大重新排序464aet.sort(EdgeXiComparator);465)其實(shí)更新完xi后對(duì)aet表的重新排序是可以避免的，只要在維護(hù)aet時(shí)，除了保證xi從小到大的排序外，在xi相同的情況下如果能保證修正量dx也是從小到大有序，就可以避免每次對(duì)aet進(jìn)行重新排序。算法實(shí)現(xiàn)也很簡(jiǎn)單，只需要對(duì)InsertNetListT

22、oAet()函數(shù)稍作修改即可，有興趣的朋友可以自行修改。至此，掃描線算法就介紹完了，算法的思想看似復(fù)雜，實(shí)際上并不難，從具體算法的實(shí)現(xiàn)就可以看出來，整個(gè)算法實(shí)現(xiàn)不足百行代碼。第二種講解下面這個(gè)程序能對(duì)任意多邊形填充，用鼠標(biāo)畫一個(gè)封閉多邊形，畫回到起始點(diǎn)說明畫圖完畢！然后點(diǎn)右鍵填充！我用的是掃描線算法，不過在對(duì)邊界點(diǎn)的填充上有點(diǎn)問題，希望高手幫忙！#include<dos.h>#include<graphics.h>#include<conio.h>#include<stdio.h>#defineFALSE0#defineTRUE1#defineN

23、ULL0unionREGSregs;/*鼠標(biāo)的變量*/intX_max,Y_max;/*鼠標(biāo)活動(dòng)范圍最大值*/鼠標(biāo)點(diǎn)擊的初始點(diǎn)，前intx_Origin,y_Origin,x_Old,y_Old,x_New,y_New;/*一點(diǎn)和當(dāng)前點(diǎn)的坐標(biāo)*/intPointNum=0;/*判斷鼠標(biāo)是否是第一次按下*/intLineDrawFlag=FALSE;/*隨鼠標(biāo)畫線標(biāo)志*/intAddFlag=TRUE;/*邊是否加入邊表標(biāo)志*/inty_Now;/*掃描線y的當(dāng)前值*/inty_Start,y_Over;/*掃描線的起點(diǎn)與終點(diǎn)*/typedefstructEtable/*邊表數(shù)據(jù)結(jié)構(gòu)*/(int

24、Ymax;/*一條邊中Y值較大點(diǎn)的Y值*/floatx;/*一條邊中Y值較小點(diǎn)的X值*/inty;/*一條邊中Y值較小點(diǎn)的Y值*/floatdx;/*一條邊的斜率的倒數(shù)*/structEtable*next;/*指向下一條相臨邊的指針*/ETable;typedefstructAEtable/*活動(dòng)邊表數(shù)據(jù)結(jié)構(gòu)*/(intYmax;floatx;floatdx;structAEtable*next;AETable;/*交換結(jié)點(diǎn)數(shù)據(jù)時(shí)用的臨時(shí)指針，這個(gè)指針我放在相應(yīng)函數(shù)中定義編譯時(shí)會(huì)有警告并*/AETable*temp;/*會(huì)在程序退出時(shí)報(bào)錯(cuò)，不清楚原因!*/voidInitgr()/*初始化圖

25、形模式*/(intgdriver=DETECT,gmode;registerbgidriver(EGAVGA_driver);initgraph(&gdriver,&gmode,"");X_max=getmaxx();Y_max=getmaxy();/*鼠標(biāo)活動(dòng)范圍最大值*/ETable*AddtoEtable(intx_Old,inty_Old,intx_New,inty_New,ETable*head)/*將邊加入邊表*/ETable*p,*q1;p=head;while(p->next!=NULL)/*轉(zhuǎn)到邊表最后一個(gè)結(jié)點(diǎn)處*/p=p->n

26、ext;q1=(ETable*)malloczeof(ETable);/*臨時(shí)建立一個(gè)結(jié)點(diǎn)來加入新邊的信息*/if(y_New>y_Old)/*如果當(dāng)前點(diǎn)比前一點(diǎn)高，就把當(dāng)前點(diǎn)的Y值賦予邊的Ymax*/q1->Ymax=y_New;q1->x=x_Old;q1->y=y_Old;else/*如果當(dāng)然點(diǎn)比前一點(diǎn)低，就把前一點(diǎn)的Y值賦予邊的Ymax*/q1->Ymax=y_Old;q1->x=x_New;q1->y=y_New;q1->dx=(float)(x_New-x_Old)/(y_New-y_Old);if(head->Ymax<

27、q1->Ymax)/*將邊表中Ymax的最大值存入邊表頭結(jié)點(diǎn)，以確定掃描線的終點(diǎn)*/head->Ymax=q1->Ymax;if(head->y>q1->y)/*將邊表中Y(它是一條邊中X值較小的點(diǎn)的Y值)的最大值存入邊表頭結(jié)點(diǎn)/head->y=q1->y;/*以確定掃描線的起點(diǎn)*/q1->next=p->next;p->next=q1;if(x_New=x_Origin&&y_New=y_Origin)/*如果畫回到初始點(diǎn)，說明多邊形繪制完成，停止加入邊表的工作*/AddFlag=FALSE;/*將加入邊表的標(biāo)

28、志置為假*/returnhead;/*返回邊表的頭指針*/)ETable*SortEtable(ETable*head)/*把邊表中的奇異點(diǎn)消除*/(0)1樓2007-04-2615:11,bravejun20ETable*p,*q;p=head->next;q=p->next;while(q!=NULL)/*如果一條邊的Ymax(y)與下一條邊的y(Ymax)相等,Ymax減一，以達(dá)到消除奇異點(diǎn)的目的*/if(p->y=q->Ymax)q->Ymax-;if(p->Ymax=q->y)p->Ymax-;if(q->next=NULL)if

29、(q->y=head->next->Ymax)/*處理最后一條邊與加入的第一條邊的情況*/head->next->Ymax-;if(q->Ymax=head->next->y)q->Ymax-;p=p->next;q=q->next;p=head->next;q=p->next;returnhead;/*返回邊表頭指針*/AETable*SortAEtable(AETable*head)/*對(duì)活動(dòng)邊表中的邊按x從小到大排序*/AETable*p,*q;p=head->next;q=p->next;whil

30、e(q!=NULL)/*對(duì)活動(dòng)邊表中的邊按X從小到大排序*/if(p->x>q->x)(temp->Ymax=q->Ymax;temp->x=q->x;temp->dx=q->dx;q->Ymax=p->Ymax;q->x=p->x;q->dx=p->dx;p->Ymax=temp->Ymax;p->x=temp->x;p->dx=temp->dx;temp=NULL;)q=q->next;p=p->next;)returnhead;/*返回活動(dòng)邊表的頭指針

31、*/)voidAET_Fill(AETable*head,intcolor)/*填充活動(dòng)邊表中的奇數(shù)邊到偶數(shù)邊問的像素*/(AETable*p,*q;p=head->next;q=p->next;setcolor(color);while(q!=NULL)/*如果活動(dòng)邊表中有邊要填充*/(line(p->x,y_Now+1,q->x,y_Now+1);delay(1000);q=q->next;p=p->next;if(q!=NULL)/*如果活動(dòng)邊表仍不為空*/q=q->next;p=p->next;)AETable*DeleteAETable

32、(intYmax,AETable*head)/*刪除活動(dòng)邊表中Ymax大于掃描線y的邊*/AETable*p,*q,*m;p=head;q=head->next;while(q!=NULL)if(q->Ymax=Ymax)/*刪除活動(dòng)邊表中邊的Ymaxfi與當(dāng)前掃描線Y值相等的所有邊*/p->next=q->next;free(q);q=head->next;p=head;)elseq=q->next;p=p->next;)returnhead;)填充多邊形*/voidPolygonFill(ETable*head1,AETable*head2)/*E

33、Tablebravejun20if(y_Now=q1->y)/*如果邊表中有與掃描線Y值相等的Y值，則將這些邊加入活動(dòng)邊表*/p2=head2;p1,*q1;AETable*p2,*q2;y_Over=head1->Ymax;/*從邊表的頭結(jié)點(diǎn)獲取掃描線的起始值*/y_Start=head1->y;/*從邊表的頭結(jié)點(diǎn)獲取掃描線的終結(jié)值*/head1=SortEtable(head1);/*對(duì)邊表按Y值從小到大排序*/for(y_Now=y_Start;y_Now<y_Over;y_Now+)/*如果掃描線還在多邊形的范圍內(nèi)，做以下工作*/p1=head1;q1=p1-&

34、gt;next;while(q1!=NULL)/*如果邊表不為空*/回復(fù) 2樓2007-04-2615:11 K|while(p2->next!=NULL)p2=p2->next;q2=(AETable*)malloc(sizeof(AETable);q2->Ymax=q1->Ymax;q2->x=q1->x;q2->dx=q1->dx;q2->next=p2->next;p2->next=q2;p1->next=q1->next;free(q1);/*將邊表中已經(jīng)加入活動(dòng)邊表的邊刪除*/p1=head1;q1=p1

35、->next;)elseq1=q1->next;p1=p1->next;)head2=SortAEtable(head2);/*對(duì)活動(dòng)邊表中的邊按X從小到大排序*/AET_Fill(head2,RED);/*填充活動(dòng)邊表中從奇數(shù)邊到偶數(shù)邊問的像素點(diǎn)*/head2=DeleteAETable(y_Now,head2);/*刪除活動(dòng)邊表中已經(jīng)填充完畢了的邊*/p2=head2->next;while(p2!=NULL)p2->x=(float)(p2->x+p2->dx);/*將活動(dòng)邊表中的邊的X值增加dx,即:x=x+dx;*/p2=p2->nex

36、t;)intMouseInit(intXp0,intXp1,intYp0,intYp1)/*初始化鼠標(biāo)*/*這里的參數(shù)是鼠標(biāo)活動(dòng)范圍的左上角坐標(biāo)和右下角坐標(biāo)*/intretcode;regs.x.ax=0;int86(0x33,?s,?s);retcode=regs.x.ax;if(retcode=0)return0;regs.x.ax=7;regs.x.cx=Xp0;regs.x.dx=Xp1;int86(0x33,?s,?s);regs.x.ax=3;regs.x.cx=Yp0;regs.x.dx=Yp1;int86(0x33,?s,?s);returnretcode;)intMouseS

37、tate(int*m_x,int*m_y,int*mstate)/*獲取鼠標(biāo)狀態(tài)和位置*/staticintx0=10,y0=10,state=0;intxnew,ynew,ch;doif(kbhit()ch=getch();if(ch=13)*mstate=1;return-1;)elsereturnch;)regs.x.ax=3;int86(0x33,?s,?s);xnew=regs.x.cx;ynew=regs.x.dx;*mstate=regs.x.bx;while(xnew=x0&&ynew=y0&&*mstate=state);state=*msta

38、te;x0=xnew;y0=ynew;*m_x=xnew;*m_y=ynew;return-1;voidDrawCursor(intx,inty)/*在鼠標(biāo)當(dāng)前位置畫鼠標(biāo)指針和跟隨鼠標(biāo)移動(dòng)的直線*/intcolor;charstr50;line(x-6,y,x-2,y);line(x,y-6,x,y-3);line(x+2,y,x+6,y);line(x,y+3,x,y+6);if(LineDrawFlag=TRUE)line(x_New,y_New,x,y);color=getcolor();setcolor(getbkcolor();outtextxy(10,20,str);sprintf(str,"(%d,%d)",x,y);/bravejun20顯示鼠標(biāo)當(dāng)前的坐標(biāo)值*/setcolor(WHITE);outtextxy(10,20,str);setcolor(color);main()intX,Y,m_state,y,a,b,i,j;AETable*head2;ETable*head1;head1=(ETable*)malloc(sizeof(ETable);/*開辟邊表的一個(gè)頭結(jié)點(diǎn)來保存掃描線的起始和終結(jié)值*/head1->Ymax=0;/*初始化Ymax為零，以便比較得到最大的Ymax*/hea