掃描線(xiàn)填充算法講解

1、掃描線(xiàn)算法（Scan-Line Filling）掃描線(xiàn)算法適合對(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í)際工程中使用的填充算法都是只使用求交的思想，并不直接使用這種求交算法。究其原因，除了算法效率問(wèn)題之外，還存在一個(gè)光柵圖形設(shè)備和矢量之間的轉(zhuǎn)換問(wèn)題。比如某個(gè)點(diǎn)位于非?？拷吔绲呐R界位置，用

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

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

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

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

6、在yi+1 = yi + 1的關(guān)系，將代入上式即可得到：xi+1 xi = -b / a即x = -b / a，是個(gè)常量（直線(xiàn)斜率的倒數(shù)）?！盎顒?dòng)邊表”是掃描線(xiàn)填充算法的核心，整個(gè)算法都是圍繞者這張表進(jìn)行處理的。要完整的定義“活動(dòng)邊表”，需要先定義邊的數(shù)據(jù)結(jié)構(gòu)。每條邊都和掃描線(xiàn)有個(gè)交點(diǎn)，掃描線(xiàn)填充算法只關(guān)注交點(diǎn)的x坐標(biāo)。每當(dāng)處理下一條掃描線(xiàn)時(shí)，根據(jù)x直接計(jì)算出新掃描線(xiàn)與邊的交點(diǎn)x坐標(biāo)，可以避免復(fù)雜的求交計(jì)算。一條邊不會(huì)一直待在“活動(dòng)邊表”中，當(dāng)掃描線(xiàn)與之沒(méi)有交點(diǎn)時(shí)，要將其從“活動(dòng)邊表”中刪除，判斷是否有交點(diǎn)的依據(jù)就是看掃描線(xiàn)y是否大于這條邊兩個(gè)端點(diǎn)的y坐標(biāo)值，為此，需要記錄邊的y坐標(biāo)的最大值。

7、根據(jù)以上分析，邊的數(shù)據(jù)結(jié)構(gòu)可以定義如下：65 typedef struct tagEDGE66 67 double xi;68 double dx;69 int ymax;74 EDGE; 根據(jù)EDGE的定義，掃描線(xiàn)4和掃描線(xiàn)7的“活動(dòng)邊表”就分別如圖（7）和圖(8)所示：圖（7） 掃描線(xiàn)4的活動(dòng)邊表圖（8） 掃描線(xiàn)7的活動(dòng)邊表前面提到過(guò)，掃描線(xiàn)算法的核心就是圍繞“活動(dòng)邊表（AET）”展開(kāi)的，為了方便活性邊表的建立與更新，我們?yōu)槊恳粭l掃描線(xiàn)建立一個(gè)“新邊表（NET）”，存放該掃描線(xiàn)第一次出現(xiàn)的邊。當(dāng)算法處理到某條掃描線(xiàn)時(shí)，就將這條掃描線(xiàn)的“新邊表”中的所有邊逐一插入到“活動(dòng)邊表”中?！靶逻叡怼?/p>

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

9、充的過(guò)程是成對(duì)選擇交點(diǎn)的過(guò)程，錯(cuò)誤的計(jì)算交點(diǎn)個(gè)數(shù)，會(huì)造成填充異常。假設(shè)多邊形按照頂點(diǎn)P1、P2和P3的順序產(chǎn)生兩條相鄰的邊，P2就是所說(shuō)的頂點(diǎn)。多邊形的頂點(diǎn)一般有四種情況，如圖（10）所展示的那樣，分別被稱(chēng)為左頂點(diǎn)、右頂點(diǎn)、上頂點(diǎn)和下頂點(diǎn)：圖（10） 多邊形頂點(diǎn)的四種類(lèi)型左頂點(diǎn)P1、P2和P3的y坐標(biāo)滿(mǎn)足條件 ：y1 < y2 < y3；右頂點(diǎn)P1、P2和P3的y坐標(biāo)滿(mǎn)足條件 ：y1 > y2 > y3；上頂點(diǎn)P1、P2和P3的y坐標(biāo)滿(mǎn)足條件 ：y2 > y1 && y2 > y3；下頂點(diǎn)P1、P2和P3的y坐標(biāo)滿(mǎn)足條件 ：y2 < y

10、1 && y2 < y3；對(duì)于左頂點(diǎn)和右頂點(diǎn)的情況，如果不做特殊處理會(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修改為ymax 1就可以了。對(duì)于上頂點(diǎn)和下頂點(diǎn)，一種處理方法是將交點(diǎn)計(jì)算做0個(gè)，也就是修正兩條邊的區(qū)間，將交點(diǎn)從兩條邊中排除；另一種處理方法是不做特殊處理，就計(jì)算2個(gè)交點(diǎn)，這樣也能保證交點(diǎn)奇偶個(gè)數(shù)平衡。（2） 水平邊的處理水平邊與掃描線(xiàn)重合，會(huì)產(chǎn)生很多交點(diǎn)，通常的做法是將水

11、平邊直接畫(huà)出（填充），然后在后面的處理中就忽略水平邊，不對(duì)其進(jìn)行求交計(jì)算。（3） 如何避免填充越過(guò)邊界線(xiàn)邊界像素的取舍問(wèn)題也需要特別注意。多邊形的邊界與掃描線(xiàn)會(huì)產(chǎn)生兩個(gè)交點(diǎn)，填充時(shí)如果對(duì)兩個(gè)交點(diǎn)以及之間的區(qū)域都填充，容易造成填充范圍擴(kuò)大，影響最終光柵圖形化顯示的填充效果。為此，人們提出了“左閉右開(kāi)”的原則，簡(jiǎn)單解釋就是，如果掃描線(xiàn)交點(diǎn)是1和9，則實(shí)際填充的區(qū)間是1,9），即不包括x坐標(biāo)是9的那個(gè)點(diǎn)。2.2掃描線(xiàn)算法實(shí)現(xiàn)掃描線(xiàn)算法的整個(gè)過(guò)程都是圍繞“活動(dòng)邊表（AET）”展開(kāi)的，為了正確初始化“活動(dòng)邊表”，需要初始化每條掃描線(xiàn)的“新邊表（NET）”，首先定義“新邊表”的數(shù)據(jù)結(jié)構(gòu)。定義“新邊表”為一

12、個(gè)數(shù)組，數(shù)組的每個(gè)元素存放對(duì)應(yīng)掃描線(xiàn)的所有“新邊”。因此定義“新邊表”如下：510 std:vector< std:list<EDGE> > slNet(ymax - ymin + 1);ymax和ymin是多邊形所有頂點(diǎn)中y坐標(biāo)的最大值和最小值，用于界定掃描線(xiàn)的范圍。slNet 中的第一個(gè)元素對(duì)應(yīng)的是ymin所在的掃描線(xiàn)，以此類(lèi)推，最后一個(gè)元素是ymax所在的掃描線(xiàn)。在開(kāi)始對(duì)每條掃描線(xiàn)處理之前，需要先計(jì)算出多邊形的ymax和ymin并初始化“新邊表”：503 void ScanLinePolygonFill(const Polygon& py, int col

13、or)504 505 assert(py.IsValid();506 507 int ymin = 0;508 int ymax = 0;509 GetPolygonMinMax(py, ymin, ymax);510 std:vector< std:list<EDGE> > slNet(ymax - ymin + 1);511 InitScanLineNewEdgeTable(slNet, py, ymin, ymax);512 /PrintNewEdgeTable(slNet);513 HorizonEdgeFill(py, color); /水平邊直接畫(huà)線(xiàn)填充51

14、4 ProcessScanLineFill(slNet, ymin, ymax, color);515 InitScanLineNewEdgeTable()函數(shù)根據(jù)多邊形的頂點(diǎn)和邊的情況初始化“新邊表”，實(shí)現(xiàn)過(guò)程中體現(xiàn)了對(duì)左頂點(diǎn)和右頂點(diǎn)的區(qū)間修正原則：315 void InitScanLineNewEdgeTable(std:vector< std:list<EDGE> >& slNet, 316 const Polygon& py, int ymin, int ymax)317 318 EDGE e;319 for(int i = 0; i <

15、py.GetPolyCount(); i+)320 321 const Point& ps = py.ptsi;322 const Point& pe = py.pts(i + 1) % py.GetPolyCount();323 const Point& pss = py.pts(i - 1 + py.GetPolyCount() % py.GetPolyCount();324 const Point& pee = py.pts(i + 2) % py.GetPolyCount();325 332 if(pe.y != ps.y) /不處理水平線(xiàn)333 334

16、 e.dx = double(pe.x - ps.x) / double(pe.y - ps.y);335 if(pe.y > ps.y)336 337 e.xi = ps.x;338 if(pee.y >= pe.y)339 e.ymax = pe.y - 1;340 else341 e.ymax = pe.y;342 343 slNetps.y - ymin.push_front(e);344 345 else346 347 e.xi = pe.x;348 if(pss.y >= ps.y)349 e.ymax = ps.y - 1;350 else351 e.ymax

17、= ps.y;352 slNetpe.y - ymin.push_front(e);353 354 355 356 多邊形的定義Polygon和本系列第一篇計(jì)算幾何與圖形學(xué)有關(guān)的幾種常用算法一文中的定義一致，此處就不再重復(fù)說(shuō)明。算法通過(guò)遍歷所有的頂點(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和pe兩個(gè)點(diǎn)是否是左頂點(diǎn)或右頂點(diǎn)，然后根據(jù)判斷結(jié)果對(duì)此邊的ymax進(jìn)行-1修正，算法實(shí)現(xiàn)非常簡(jiǎn)單，注意與掃描線(xiàn)平行的邊是不處理的，因?yàn)樗?/p>

18、平邊直接在HorizonEdgeFill()函數(shù)中填充了。ProcessScanLineFill()函數(shù)開(kāi)始對(duì)每條掃描線(xiàn)進(jìn)行處理，對(duì)每條掃描線(xiàn)的處理有四個(gè)操作，如下代碼所示，四個(gè)操作分別被封裝到四個(gè)函數(shù)中： 467 void ProcessScanLineFill(std:vector< std:list<EDGE> >& slNet, 468 int ymin, int ymax, int color)469 470 std:list<EDGE> aet;471 472 for(int y = ymin; y <= ymax; y+)473

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

20、動(dòng)作，它將aet中的邊交點(diǎn)成對(duì)取出組成填充區(qū)間，然后根據(jù)“左閉右開(kāi)”的原則對(duì)每個(gè)區(qū)間填充，實(shí)現(xiàn)也很簡(jiǎn)單，此處不多解釋。RemoveNonActiveEdgeFromAet()函數(shù)負(fù)責(zé)將對(duì)下一條掃描線(xiàn)來(lái)說(shuō)已經(jīng)不是“活動(dòng)邊”的邊從aet中刪除，刪除的條件就是當(dāng)前掃描線(xiàn)y與邊的ymax相等，如果有多條邊滿(mǎn)足這個(gè)條件，則一并全部刪除：439 bool IsEdgeOutOfActive(EDGE e, int y)440 441 return (e.ymax = y);442 443 444 void RemoveNonActiveEdgeFromAet(std:list<EDGE>&am

21、p; aet, int y)445 446 aet.remove_if(std:bind2nd(std:ptr_fun(IsEdgeOutOfActive), y);447 UpdateAndResortAet()函數(shù)更新邊表中每項(xiàng)的xi值，就是根據(jù)掃描線(xiàn)的連貫性用dx對(duì)其進(jìn)行修正，并且根據(jù)xi從小到大的原則對(duì)更新后的aet表重新排序：449 void UpdateAetEdgeInfo(EDGE& e)450 451 e.xi += e.dx;452 453 454 bool EdgeXiComparator(EDGE& e1, EDGE& e2)455 456 re

22、turn (e1.xi <= e2.xi);457 458 459 void UpdateAndResortAet(std:list<EDGE>& aet)460 461 /更新xi462 for_each(aet.begin(), aet.end(), UpdateAetEdgeInfo);463 /根據(jù)xi從小到大重新排序464 aet.sort(EdgeXiComparator);465 其實(shí)更新完xi后對(duì)aet表的重新排序是可以避免的，只要在維護(hù)aet時(shí)，除了保證xi從小到大的排序外，在xi相同的情況下如果能保證修正量dx也是從小到大有序，就可以避免每次對(duì)ae

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

24、.h> #define FALSE 0 #define TRUE 1 #define NULL 0 union REGS regs; /* 鼠標(biāo)的變量 */ int X_max,Y_max; /* 鼠標(biāo)活動(dòng)范圍最大值 */ int x_Origin, y_Origin,x_Old,y_Old,x_New,y_New;/* 鼠標(biāo)點(diǎn)擊的初始點(diǎn),前一點(diǎn)和當(dāng)前點(diǎn)的坐標(biāo) */ int PointNum=0; /* 判斷鼠標(biāo)是否是第一次按下 */ int LineDrawFlag=FALSE; /* 隨鼠標(biāo)畫(huà)線(xiàn)標(biāo)志 */ int AddFlag=TRUE; /* 邊是否加入邊表標(biāo)志 */ int y

25、_Now; /* 掃描線(xiàn)y的當(dāng)前值 */ int y_Start,y_Over; /* 掃描線(xiàn)的起點(diǎn)與終點(diǎn) */ typedef struct Etable /* 邊表數(shù)據(jù)結(jié)構(gòu) */ int Ymax; /* 一條邊中Y值較大點(diǎn)的Y值 */ float x; /* 一條邊中Y值較小點(diǎn)的X值 */ int y; /* 一條邊中Y值較小點(diǎn)的Y值 */ float dx; /* 一條邊的斜率的倒數(shù) */ struct Etable *next; /* 指向下一條相臨邊的指針 */ ETable; typedef struct AEtable /* 活動(dòng)邊表數(shù)據(jù)結(jié)構(gòu) */ int Ymax; floa

26、t x; float dx; struct AEtable *next; AETable; /* 交換結(jié)點(diǎn)數(shù)據(jù)時(shí)用的臨時(shí)指針,這個(gè)指針我放在相應(yīng)函數(shù)中定義編譯時(shí)會(huì)有警告并 */ AETable *temp; /* 會(huì)在程序退出時(shí)報(bào)錯(cuò),不清楚原因! */ void Initgr() /* 初始化圖形模式 */ int gdriver=DETECT,gmode; registerbgidriver(EGAVGA_driver); initgraph(&gdriver,&gmode,""); X_max=getmaxx(); Y_max=getmaxy(); /*

27、 鼠標(biāo)活動(dòng)范圍最大值 */ ETable *AddtoEtable(int x_Old,int y_Old,int x_New,int y_New,ETable *head) /* 將邊加入邊表 */ ETable *p,*q1; p=head; while(p->next!=NULL) /* 轉(zhuǎn)到邊表最后一個(gè)結(jié)點(diǎn)處 */ p=p->next; q1=(ETable *)malloc(sizeof(ETable); /* 臨時(shí)建立一個(gè)結(jié)點(diǎn)來(lái)加入新邊的信息 */ if(y_New>y_Old) /* 如果當(dāng)前點(diǎn)比前一點(diǎn)高,就把當(dāng)前點(diǎn)的Y值賦予邊的Ymax */ q1->Y

28、max = 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 < q1->Ymax) /* 將邊表中Ymax的最大值存入邊表頭結(jié)點(diǎn),以確定掃描線(xiàn)的終點(diǎn) */ head->Ymax=q1->Ymax; if(head->y >

29、q1->y) /* 將邊表中 Y(它是一條邊中X值較小的點(diǎn)的Y值) 的最大值存入邊表頭結(jié)點(diǎn), */ head->y=q1->y; /* 以確定掃描線(xiàn)的起點(diǎn) */ q1->next=p->next; p->next=q1; if(x_New=x_Origin && y_New=y_Origin) /* 如果畫(huà)回到初始點(diǎn),說(shuō)明多邊形繪制完成,停止加入邊表的工作 */ AddFlag=FALSE; /* 將加入邊表的標(biāo)志置為假 */ return head; /* 返回邊表的頭指針 */ ETable *SortEtable(ETable *hea

30、d) /* 把邊表中的奇異點(diǎn)消除 */ (0)· 回復(fù)· 1樓· 2007-04-26 15:11· 舉報(bào) |個(gè)人企業(yè)舉報(bào)垃圾信息舉報(bào)· 我也說(shuō)一句·· bravejun20 · ETable *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-&

31、gt;y) p->Ymax-; if(q->next=NULL) if(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; return head; /* 返回邊表頭指針 */ AETable *SortAEtable(AETable *head) /* 對(duì)活動(dòng)

32、邊表中的邊按x從小到大排序 */ AETable *p,*q; p=head->next; q=p->next; while(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;

33、p->dx=temp->dx; temp=NULL; q=q->next; p=p->next; return head; /* 返回活動(dòng)邊表的頭指針 */ void AET_Fill(AETable *head,int color) /* 填充活動(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(10

34、00); q=q->next; p=p->next; if(q!=NULL) /* 如果活動(dòng)邊表仍不為空 */ q=q->next; p=p->next; AETable *DeleteAETable(int Ymax,AETable *head) /* 刪除活動(dòng)邊表中Ymax大于掃描線(xiàn)y的邊 */ AETable *p,*q,*m; p=head; q=head->next; while(q!=NULL) if(q->Ymax=Ymax) /* 刪除活動(dòng)邊表中邊的Ymax值與當(dāng)前掃描線(xiàn)Y值相等的所有邊 */ p->next=q->next; f

35、ree(q); q=head->next; p=head; else q=q->next; p=p->next; return head; void PolygonFill(ETable *head1,AETable *head2) /* 填充多邊形 */ ETable *p1,*q1; AETable *p2,*q2; y_Over=head1->Ymax; /* 從邊表的頭結(jié)點(diǎn)獲取掃描線(xiàn)的起始值 */ y_Start=head1->y; /* 從邊表的頭結(jié)點(diǎn)獲取掃描線(xiàn)的終結(jié)值 */ head1=SortEtable(head1); /* 對(duì)邊表 按Y值從小到大

36、排序 */ for( y_Now=y_Start; y_Now<y_Over; y_Now+ ) /* 如果掃描線(xiàn)還在多邊形的范圍內(nèi),做以下工作 */ p1=head1; q1=p1->next; while(q1!=NULL) /* 如果邊表不為空 */ 回復(fù) 收起回復(fù) · 2樓· 2007-04-26 15:11· 舉報(bào) |個(gè)人企業(yè)舉報(bào)垃圾信息舉報(bào)· 我也說(shuō)一句·· bravejun20 ·if(y_Now=q1->y) /* 如果邊表中有與掃描線(xiàn)Y值相等的Y值,則將這些邊加入活動(dòng)邊表 */ p2=he

37、ad2; 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->next; else q1=q1->nex

38、t;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->next;

39、 int MouseInit(int Xp0,int Xp1,int Yp0,int Yp1) /* 初始化鼠標(biāo) */ /* 這里的參數(shù)是鼠標(biāo)活動(dòng)范圍的左上角坐標(biāo)和右下角坐標(biāo) */ int retcode; regs.x.ax=0; int86(0x33,®s,®s); retcode=regs.x.ax; if(retcode=0) return 0; 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=Y

40、p1; int86(0x33,®s,®s); return retcode; int MouseState(int *m_x,int *m_y,int *mstate) /* 獲取鼠標(biāo)狀態(tài)和位置 */ static int x0=10,y0=10,state=0; int xnew,ynew,ch; do if(kbhit() ch=getch(); if(ch=13) *mstate=1; return -1; else return ch; regs.x.ax=3; int86(0x33,®s,®s); xnew=regs.x.cx; ynew=re

41、gs.x.dx; *mstate=regs.x.bx; while(xnew=x0&&ynew=y0&&*mstate=state); state=*mstate; x0=xnew; y0=ynew; *m_x=xnew; *m_y=ynew; return -1; void DrawCursor(int x,int y) /* 在鼠標(biāo)當(dāng)前位置畫(huà)鼠標(biāo)指針 和 跟隨鼠標(biāo)移動(dòng)的直線(xiàn) */ int color; char str50; 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

42、,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); /* 顯示鼠標(biāo)當(dāng)前的坐標(biāo)值 */ setcolor(WHITE); outtextxy(10,20,str); setcolor(color); main() int X,Y,m_state,y,a,b,i,j; AETable *head2; ETable *head1; head1=(ETable *)malloc(sizeof(ETable); /* 開(kāi)辟邊表的一個(gè)頭結(jié)點(diǎn)來(lái)保存掃描線(xiàn)的起始和終結(jié)值 */ head1->Ymax=0; /* 初始化Ymax為零,以便比較得到最大的Ymax */ head1->y=10000; /* 初始化Y為10000,以便比較得到最小的Y */ head1->next=NULL; head2=(AETable *)mallo