圖形學(xué)實驗報告四 多邊形填充算法

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

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

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

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

5、(或左邊)的象素作為種子象素.區(qū)域填充(掃描線算法)：目標：減少遞歸層次適用于內(nèi)點表示的4連通區(qū)域基本過程：當給定種子點時，首先填充種子點所在的掃描線上的位于給定區(qū)域的一個區(qū)段，然后確定與這一區(qū)段相通的上下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個過程，直到填充結(jié)束。算法步驟：1、填充并確定種子區(qū)段；2、初始化：將種子區(qū)段壓入堆棧；3、出棧：如果堆棧為空，則算法結(jié)束；否則取棧頂元素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窗體應(yīng)用程序，實現(xiàn)對于算法的選擇。2、 根據(jù)不同算法添加不同窗體，接受圓初始化數(shù)據(jù)，編寫核心函數(shù)。代碼見實驗原理中代碼部分。3、 調(diào)試運行。實驗內(nèi)容在VS2010環(huán)境下利用C#編程實現(xiàn)多邊