圖形學實驗報告四 多邊形填充算法

1、貴州大學實驗報告學院：計算機科學與信息學院 專業(yè):計算機科學與技術 班級： 101姓名學號實驗組4實驗時間2013.4.25指導教師吳云成績實驗項目名稱多邊形填充算法實驗目的使學生掌握光柵顯示系統(tǒng)中多邊形的掃描轉換和區(qū)域填充算法。掌握4連通區(qū)域的擴展性。實驗要求實現多邊形的掃描轉換算法和區(qū)域填充算法實驗原理掃描線算法算法原理：利用相鄰像素之間的連貫性，提高算法效率。根據多邊形內部點的連續(xù)性知：一條掃描線與多邊形的交點中，入點和出點之間所有點都是多邊形的內部點。所以，對所有的掃描線填充入點到出點之間所有的點就可填充多邊形。1024681012024681234處理對象：非自交多邊形（邊與邊之間除

2、了頂點外無其它交點）判斷掃描線上的點是否在多邊形之內,根據多邊形區(qū)域連續(xù)性，分為3個步驟： 求出掃描線與多邊形所有邊的交點； 把這些交點的x坐標值以升序排列； 對每一對交點間的區(qū)域進行填充。 第三個步驟是從奇數個交點出發(fā)到偶數個交點。如右圖，對y8的掃描線排序x坐標得到的表是(2,4,9,13)，然后對交點2與4之間、9與13之間的所有象素點進行填充。幾點規(guī)則：邊界上的象素:“左閉右開”，“下閉上開”(將左邊界和下邊界的點算為內部，而將右邊界和上邊界算為外部)頂點：“上開下閉”。幾種特殊情況：1掃描線交于一頂點，共享的兩條邊分另處于掃描線的兩邊，這時交點只取一個，如掃描線y=3，該點被填充一次

3、。2.共享交點的兩條邊處于掃描線的上方，這時交點取二個，如掃描線y=1，該點被填充一次。3共享交點的兩條邊處于掃描線的下方，這時交點取0個，如掃描線y=9，無交點，不填充。4水平邊在算法中不起任何作用，可不考慮?；钚赃叡?提高效率)：為了減少求交的計算量，要利用一條邊與相繼的兩條掃描線的交點的連貫性。在處理一條掃描線時只對活性邊（與它相交的多邊形的邊）進行求交運算。把交點按x增加方向存在一個鏈表（活性邊表）中?；钚赃叄号c當前掃描線相交的邊?；钚赃叡恚ˋEL）：按交點x的增量順序存放在一個鏈表中，該鏈表稱作活性邊表（AEL）。種子填充算法算法原理種子填充算法首先假定區(qū)域由封閉輪廓線圍成，且輪廓線

4、內某點是已知的，然后開始搜索與種子點相鄰且位于輪廓線內的點。如果這相鄰 點不在輪廓線內，則已達到輪廓線的邊界；如果相鄰點在輪廓線之內，則這相鄰點成為新的種子點，繼續(xù)搜索下去。只適用于光柵掃描設備。區(qū)域分類（區(qū)域采用邊界定義，即區(qū)域邊界上與邊界外的象素取相同值，區(qū)域內部的點取不同值）1、四向連通區(qū)域：各象素在水平垂直四個方向是邊通的。即從區(qū)域內任一點出發(fā)，可水平垂直移動到達區(qū)域內任一點。2、八向連通區(qū)域：各象素在水平、垂直、及四個對角線方向都是是邊通的。即從區(qū)域內任一點出發(fā)，可水平、垂直、及四個對角線方向移動到達區(qū)域內任一點。掃描線種子算法測試對象為象素段 ,對區(qū)域內的每一象素段,只保留其最右邊

5、(或左邊)的象素作為種子象素.區(qū)域填充(掃描線算法)：目標：減少遞歸層次適用于內點表示的4連通區(qū)域基本過程：當給定種子點時，首先填充種子點所在的掃描線上的位于給定區(qū)域的一個區(qū)段，然后確定與這一區(qū)段相通的上下兩條掃描線上位于給定區(qū)域內的區(qū)段，并依次保存下來。反復這個過程，直到填充結束。算法步驟：1、填充并確定種子區(qū)段；2、初始化：將種子區(qū)段壓入堆棧；3、出棧：如果堆棧為空，則算法結束；否則取棧頂元素y,xLeft,xRight），以縱坐標為y的掃描線為當前掃描線，xLeft, xRight為搜索區(qū)間；4、填充并確定新的區(qū)段 。掃描線種子填充： public void FillField(int

6、x, int y, Color newColor, uint oldColor, Graphics g) if ("".Equals(txtx.Text) | "".Equals(txty.Text) return; else x = Convert.ToInt32(txtx.Text); y = Convert.ToInt32(txty.Text); int xl, xr; bool spanNeedFill; myStack.Clear(); int ptx = x; int pty = y; myStack.Push(ptx); myStack.P

7、ush(pty); while (myStack.Count != 0) pty = (int)myStack.Pop(); ptx = (int)myStack.Pop(); x = ptx; y = pty; while (bitmap.GetPixel(g, x, y) = oldColor) bitmap.SetPixel(g, x, y, ColorTranslator.ToWin32(newColor); x+; xr = x - 1; x = ptx - 1; while (bitmap.GetPixel(g, x, y) = oldColor) bitmap.SetPixel(

8、g, x, y, ColorTranslator.ToWin32(newColor); x-; xl = x + 1; x = xl; y = y + 1; while (x <= xr) spanNeedFill = false; while (bitmap.GetPixel(g, x, y) = oldColor) spanNeedFill = true; x+; if (spanNeedFill) ptx = x - 1; pty = y; myStack.Push(ptx); myStack.Push(pty); spanNeedFill = false; while (bitm

9、ap.GetPixel(g, x, y) != oldColor && x <= xr) x+; x = xl; y = y - 2; while (x <= xr) spanNeedFill = false; while （bitmap.GetPixel(g, x, y) = oldColor) spanNeedFill = true; x+; if (spanNeedFill) ptx = x - 1; pty = y; myStack.Push(ptx); myStack.Push(pty); spanNeedFill = false; while (bitm

10、ap.GetPixel(g, x, y) != oldColor && x <= xr) x+; 四連通種子填充： public void BoundaryFill4(int x, int y, uint oldColor, Graphics g) if ("".Equals(txtx.Text) | "".Equals(txty.Text) return; else x = Convert.ToInt32(txtx.Text); y = Convert.ToInt32(txty.Text); if (bitmap.GetPixel

11、(g, x, y) != oldColor && bitmap.GetPixel(g, x, y) = ColorTranslator.ToWin32(Color.Yellow) bitmap.SetPixel(g, x, y, ColorTranslator.ToWin32(Color.Red); BoundaryFill4(x, y + 1, oldColor, g); BoundaryFill4(x - 1, y, oldColor, g); BoundaryFill4(x, y - 1, oldColor, g); BoundaryFill4(x + 1, y, oldColor, g); 實驗環(huán)境VS2010(C#) 實驗步驟1、 添加一個C#下的Windows窗體應用程序，實現對于算法的選擇。2、 根據不同算法添加不同窗體，接受圓初始化數據，編寫核心函數。代碼見實驗原理中代碼部分。3、 調試運行。實驗內容在VS2010環(huán)境下利用C#編程實現多邊