【文章內容簡介】 形的掃描轉換過程可以分為四個步驟： （ 1）求交：計算掃描線與多邊形各邊的交點；（ 2）排序：把所有交點按 x 值遞增順序排序； （ 3）配對：第一個與第二個，第三個與第四個等等；每對交點代表掃描線與多邊形的一個相交區(qū)間 。（ 4）著色：把相交區(qū)間內的象素置成多邊形顏色，把相交區(qū)間外的象素置成背景色。 p1,p3,p4,p5 屬于局部極值點，要把他們兩次存入交點表中。如掃描線 y=7 上的交點中，有交點 (2,7,13)，按常規(guī)方法填充不正確，而要把頂點 (7,7)兩次存入交點表中 (2,7,7,13)。 p2， p6 為非極值點，則不用如上處理。 為了提高效率，在處理一條掃描線時，僅對與它相交的多邊形的邊進行求交運算。把與當前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點 x 坐標遞增的順序存放在一個鏈表中，稱此鏈表為活性邊表 (AET)。 對每一條掃描線都建立一個與它相交的多邊形的活性邊表（ AET）。每個 AET 的一個節(jié)點代表一條活性邊，它包含三項內容 x坐標； x該邊與當前掃描線交點到下一條掃描線交點的 x 增量；。 每條掃描線的活性邊表 中的活性邊節(jié)點按照各活性邊與掃描線交點的 x 值遞增排序連接在一起。 當掃描線 y 移動到下一條掃描線 y=y+1 時，活性邊表需要更新，即刪去不與新掃 描線相交的多邊形邊，同時增加與新掃描線相交的多邊形邊，并根據增量法重新計算掃描線與各邊的交點 x。 當多邊形新邊表 ET 構成后，按下列步驟進行： ①對每一條掃描線 i，初始化 ET表的表頭指針 ET[i]；②將 ymax=i的邊放入 ET[i]中； ③使 y=多邊形最低的掃描線號；④初始化活性邊表 AET 為空；⑤循環(huán)，直到 AET和 ET 為空。 ET 中對應 y 值的新邊節(jié)點插入到 AET AET表，將兩兩配對的交點之間填充給定顏色值。 AET表，將 ymax=y的邊節(jié)點從 AET 表中刪除，并將 ymaxy的各邊節(jié)點的 x 值遞增Δ x y增加 1。 三、程序源代碼 includedefineWINDOW_HEIGHT480defineNULL0includeincludeincludeincludetypedefstructtEdge/*typedef 是 將 結 構 定 義 成 數 據 類 型*/{intymax。/*邊所交的最高掃描線號 */floatx。/*當前掃描線與邊的交點的 x 值 */floatdx。/*從當前掃描線到下一條掃描線之間的 x 增量*/structtEdge*next。}Edge。 typedefstructpoint{intx,y。}POINT。/*將結點插入邊表的主體函數 */ voidInsertEdge(Edge*list,Edge*edge)/*活性邊 edge 插入活性邊表 list中 */{Edge*p,*q=list。p=qnext。/*記住 q原來所指之結點*/while(p!=NULL)/*按 x值非遞減順序增加邊表 */{ if(edgexx)/*要插入的邊的 x較大不應該在當前插入 */ p=NULL。 else/*要插入的邊的 x較小應該在當前插入 */ {q=p。 p=pnext。 }}edgenext=qnext。/*使欲插入之結點 edge 指向 q 原來所指之結點 */qnext=edge。/*使 q指向插入之結點 */} intyNext(intk,intt,POINT*pts)/*對于多邊形中的某個頂點序號 k(0,1...6)，返回下一頂點的縱坐標 ,如果這 2個頂點所在邊是水平的，則順延，即返回第 (k+2)個頂點的縱坐標 ),t是頂點個數 +1,pts指向多邊形頂點結構體的指針 */ {intj。if((k+1)(t1))/*當前頂點為最后一個頂點，則下一個頂點為第 0 個頂點 */ j=0。else j=k+1。/*當前頂點不是最后一個頂點，下一個頂點為數組下標加一 */while(pts[k].y==pts[j].y)/*掃描線掃過平行頂點，需分情況找到當前頂點下下個頂點 */if((j+1)(t1)) j=0。 else j++。return(pts[j].y)。/*返回下一個頂點的 y值 */} /*計算增量，修改 AET*//*生成邊表結點，并插入到邊表中的主體函數*/voidMakeEdgeRec(POINTlower,POINTupper,intyComp,Edge*edge,Edge*edges[])/*把邊結點 edge,放到 數組 edges[] 中*/{edgedx=(float)()/()。edgex=。if(=。/*縮短上層頂點 *//*奇點，應該把這點當作兩個點而分開，所以把 y 的最大值減一，向下移動*/elseedgeymax=。/* 不 是 奇 點 ， 不 需 改 變 y 值*/insertEdge(edges[],edge)。/*插入一個邊緣掃描線，插入到列表 */} /* 創(chuàng) 建 邊 表 的 主 體 函 數*/voidBuildEdgeList(intt,POINT*pts,Edge*edges[])/*建立新邊表 ,t:多邊形頂點個數 +1,edges[]:指向活性邊結點的指針數組*/{Edge*edge。POINTv1,v2。inti,yPrev=pts[t2].y。/*當前頂點的前 一 個頂 點 的 y 值， 在當 前 頂點 不是 奇點 時 使用 該參 數*/=pts[t1].x。=pts[t1].y。for(i=0。inext。/*查找當前掃描線對應的 y桶 */while(p)/*y桶不空 */ {q=pnext。/*找到最后一個邊結點，插入 */ InsertEdge(active,p)。/*把更新后的邊表重新插入邊表中保存*/ p=q。 }} /* 填充一對交點的主體函數*/voidFillScan(intscan,Edge*active,intcolor)/*填充掃描線 :填充掃描線上 , 且在下一結點到再下一結點之間的點*/{Edge*p1,*p2。inti。p1=activenext。while(p1){ p2=p1next。 for(i=p1x。ix。i++) putpixel((int)i,sca