實(shí)驗(yàn)六 掃描線填充算法

1、實(shí)驗(yàn)六掃描線填充算法一、實(shí)驗(yàn)?zāi)康木帉懚噙呅蔚膾呙杈€填充算法程序，加深對(duì)掃描線算法的理解，驗(yàn)證算法的正確性。二、實(shí)驗(yàn)任務(wù)（2學(xué)時(shí)）編寫多邊形的掃描線填充算法程序，利用數(shù)組實(shí)現(xiàn)AET，考慮與鏈表實(shí)現(xiàn)程序的不同。三、實(shí)驗(yàn)內(nèi)容1、算法對(duì)一條掃描線的填充一般分為以下4個(gè)步驟：（1）求交：計(jì)算掃描線與多邊形各邊的交點(diǎn)；（2）排序：把掃描線上所有交點(diǎn)按遞增順序進(jìn)行排序；（3）配對(duì)：將第一個(gè)交點(diǎn)與第二個(gè)交點(diǎn)，第三個(gè)交點(diǎn)與第四個(gè)交點(diǎn)等等進(jìn)行配對(duì)，每 對(duì)交點(diǎn)代表掃描線與多邊形的一個(gè)相交區(qū)間。（4）著色：把區(qū)間內(nèi)的像素置為填充色。2、成員函數(shù)的關(guān)系主程序名為fill_area（count, x, y），其中參數(shù)x,

2、 y是兩個(gè)一維數(shù)組，存放多邊形頂點(diǎn)（共 count個(gè)）的x和y坐標(biāo)。它調(diào)用8個(gè)子程序，彼此之間的調(diào)用關(guān)系圖1所示為：fill_areasort_on_bigger_srput_in_sides_listfor掃描線update_first_aiid_lastpieces s_x_intersectionssort_on_xswapdraw_linesupdate_sides_list圖1 fill_area的程序結(jié)構(gòu)3、算法的程序設(shè)計(jì)步驟1：創(chuàng)建“S_L_Fill”工程文件；步驟 2：創(chuàng)建類 class： EACH_ENTRY”。在工作區(qū) “S_L_Fill classes”單擊右鍵-3 ne

3、w class” -3選擇類型“Generic Class”名 稱為 “EACH_ENTRY”，添加成員變量(添加至 “class EACH_ENTRY public:” 之內(nèi))： int y_top;float x_int;int delta_y;float x_change_per_scan;步驟3：包含頭文件，同時(shí)初始化定義多邊形頂點(diǎn)數(shù)目。在class CS_L_FillView : public Cview”之前添加代碼#include EACH_ENTRY.h及“#define MAX_POINT 9”。#define MAX_POINT 9#include EACH_ENTRYh步

4、驟4：在類“class CS_L_FillView”中添加成員變量(鼠標(biāo)雙擊工作區(qū)“CS_L_FillView”， 代碼添加至“class CS_L_FillView : public Cview protected: public:之后”)：EACH_ENTRY sidesMAX_POINT;int xMAX_POINT,yMAX_POINT;int side_count,first_s,last_s,scan,bottomscan,x_int_count;步驟5：利用構(gòu)造函數(shù)“CS_L_FillView:CS_L_FillView(”初始化頂點(diǎn)坐標(biāo)(鼠標(biāo)雙擊 工作區(qū)“CS_L_FillVi

5、ew”，代碼添加至“CS_L_FillView ()之內(nèi)”)：x0=200;y0=100;x1=240;y1=160;x=220;y =340;x3=330;y3=100;x4=400;y4=180;x5=300;y5=400;x6=170;y6=380;x7=120;y7=440;x8=100;y8=220;步驟6:在“ class CS_L_FillView”下添加實(shí)現(xiàn)不同功能的成員函數(shù)。在工作區(qū) “CS_L_FillView”上單擊鼠標(biāo)右鍵，選擇“Add Member Function”，分別完成以下成員函數(shù) 的添加：void put_in_sides_list(int entry,in

6、t x1,int y1,int x2,int y2,int next_y)函數(shù)說明：put_in_sides_list子程序的主要功能是將一條邊存入活性邊表之內(nèi)。操作步 驟是：對(duì)該邊判別是否左頂點(diǎn)或右頂點(diǎn)，如果將入邊之終點(diǎn)刪去，按Hy_top的大小在活性 邊表中找到該點(diǎn)的合適位置，y值較大者，排在活性邊表的靠前位置。void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y)/ entry 為易 U除水平邊之后的 第entry條邊，x1, y1,為起點(diǎn)，x2, y2為終點(diǎn)，next_y為終點(diǎn)相鄰的下一個(gè)頂點(diǎn)y坐

7、標(biāo) int maxy;float x2_temp,x_change_temp;x_change_temp=(float)(x2-x1)/(float)(y2-y1);/計(jì)算 1/kx2_temp=float(x2);if(y2y1)&(y2next_y)/x2,y2 是左頂點(diǎn)，則(x2-1/m,y2-1)終點(diǎn)下縮y2-;x2_temp-=x_change_temp;elseif(y2next_y) /x2,y2 是右頂點(diǎn)，則(x2+1/m,y2+1)終點(diǎn)上縮y2+;x2_temp+=x_change_temp;maxy=(y1y2)?y1:y2;while(entry1)&(maxysides

8、entry-2.y_top)sidesentry-1=sidesentry-2;entry-;/ sides為邊數(shù)組，邊的y_top值越小，在數(shù)組中越靠后sidesentry-1.y_top=maxy;sidesentry-1.delta_y=abs(y2-y1)+1;if(y1y2)/ x2,y2為右頂點(diǎn)，掃描線與起點(diǎn)先求交sidesentry-1.x_int=float(x1);else/ x2,y2左頂點(diǎn)，掃描線與終點(diǎn)先求交sidesentry-1.x_int=x2_temp;sidesentry-1.x_change_per_scan=x_change_temp;void sort_o

9、n_bigger_y(int n,CDC* pDC)函數(shù)說明：sort_on_bigger_y子程序的主要功能是按照輸入的多邊形，建立起活性邊表。 操作步驟是：對(duì)每條邊加以判斷：如非水平邊則調(diào)用put_in_side_list子程序放入活性邊來; 如是水平邊則直接畫出。void sort_on_bigger_y(int n,CDC* pDC)/按照輸入的多邊形建立活性鏈表int k,x1,y1;side_count=0;/全局變量，記錄所有非水平邊數(shù)目y1=yn-1;x1=xn-1;/(Pn-1,P0)為第一條邊，開始建表bottomscan=yn-1;for(k=0;kn;k+)/sides

10、數(shù)組存放所有非水平邊，并且按照y值的由大到小順序if(y1!=yk&(k+1)SelectObject(&myPen);pDC-MoveTo(short)x1,(short)y1);pDC-LineTo(short)xk,(short)yk);if(yk當(dāng)前掃描線scan，last_s下移while(sideslast_s+1.y_top=scan)&(last_s+1)y_top;a-y_top=b-y_top;b-y_top=i_temp;/y_top 交換f_temp=a-x_int;a-x_int=b-x_int;b-x_int=f_temp;/x_int 交換 i_temp=a-de

11、lta_y;a-delta_y=b-delta_y;b-delta_y=i_temp;/delta_y 交換 f_temp=a-x_change_per_scan;a-x_change_per_scan=b-x_change_per_scan;b-x_change_per_scan=f_temp;/x_change_per_scan 交換void sort_on_x(int entry,int first_s)函數(shù)說明：sort_on_x子程序主要功能是將一條邊sidesretry在活性表邊的first到entry 之間按照x_int大小，遞增排序。操作步驟是:檢查位于entry的邊的x_in

12、t是否小于位置entry-1 的邊的x_int，如是，調(diào)用swap子程序交換兩條邊的彼此位置。void sort_on_x(int entry,int first_s)int ent1=entry;int ent2=entry;while(1)ent1-;if(sidesent2.x_int 0的邊)按照x_int的大小排序。操作步驟是：從first 到last，對(duì)每一根delta_y 0的邊，調(diào)用sort_on_x子程序排入活性邊表中合適位置。void process_x_intersections(int scan,int first_s,int last_s)int k;x_int_co

13、unt=0;/該值表示掃描線與圖形交點(diǎn)的個(gè)數(shù)for(k=first_s+1;k0)x_int_count+; /first_s+1 到 last 之間的邊數(shù)目為交點(diǎn)數(shù)目 x_int_count sort_on_x(k,first_s);/與同一掃描線相交的所有邊按照x_int遞增排序void draw_lines(int scan,int x_int_count,int index,CDC* pDC)函數(shù)說明：draw_lines子程序的主要功能是在一條掃描線位于多邊形內(nèi)的部分，填上指 定的色彩。操作步驟是：在活性邊表的激活邊范圍內(nèi)，依次取出delta _y!=0兩邊的x_int， 作為兩個(gè)端

14、點(diǎn)(x1, scan)， (x2, scan)，畫一條水平線。void draw_lines(int scan,int x_int_count,int index,CDC* pDC)/填上指定顏色int k,x1,x2;int x=index;/ index 為主函數(shù)中的 first_sCPen myPen(PS_SOLID,2,RGB(255,0,0);pDC-SelectObject(&myPen);for(k=0;kMoveTo(short)x1,(short)scan);pDC-LineTo(short)x2,(short)scan);x+;/此行功能是越過不在圖形內(nèi)的線段，直接跳到下

15、一線段。void update_sides_list()函數(shù)說明：update_sides_list子程序的主要功能是刷新活性邊表內(nèi)激活邊的值：delta_y=delta_y-1 ； x_int=x_int_x_chang_per_scan。void update_sides_list()int k;for(k=first_s;k0)sidesk.delta_y-;sidesk.x_int-=sidesk.x_change_per_scan;void fill_area(int count,int x,int y,CDC* pDC)函數(shù)說明：對(duì)含有count個(gè)頂點(diǎn)，其坐標(biāo)值存放在x和y數(shù)組中的

16、多邊形區(qū)域利用掃描 線算法填充。void fill_area(int count,int x,int y,CDC* pDC)/主程序sort_on_bigger_y(count,pDC);first_s=0;last_s=1;for(scan=sides0.y_top;scan=bottomscan;scan-)update_first_and_last(MAX_POINT,scan);process_x_intersections(scan,first_s,last_s);draw_lines（scan,x_int_count,first_s,pDC）;update_sides_list（）;步驟7：在OnDraw （）中添加代碼：fill_area（MAX_POINT,x, y, pDC）;步驟8：編譯、調(diào)試，查看運(yùn)行結(jié)果。四、思考總結(jié)1、程序?qū)Χ噙呅蔚奶厥忭旤c(diǎn)如何處理？2、程序中的“first_s”和“l(fā)ast_s”是真正的指針變量嗎？3、總結(jié)各子程序的具體功能，理解其中的各個(gè)變量的涵義和作用。4、與采用鏈表的數(shù)據(jù)結(jié)構(gòu)相比，本實(shí)驗(yàn)程序有何優(yōu)點(diǎn)和缺點(diǎn)？5、本實(shí)驗(yàn)程序中掃描線的掃描次序（按照y值）是遞增還是遞減進(jìn)行?6、修改頂點(diǎn)參數(shù)（個(gè)數(shù)及坐標(biāo)），觀察、分析實(shí)驗(yàn)結(jié)果。（1）五角星（注意修改“ MAX_POINT”為“10”）：