計算機圖形學 - 多邊形填充演算法
多邊形是由頂點的有序列表組成，如下圖所示。為了用特定的顏色填充多邊形，需要確定落在多邊形邊界上的畫素以及落在多邊形內部的畫素。在本章中，我們將瞭解如何使用不同的技術填充多邊形。
掃描線演算法
該演算法透過將掃描線與多邊形邊相交來工作，並填充相交對之間的多邊形。以下步驟描述了該演算法的工作方式。
步驟1 - 從給定的多邊形中找出Ymin和Ymax。
步驟2 - 掃描線與從Ymin到Ymax的多邊形的每條邊相交。命名多邊形的每個交點。根據上圖所示，它們被命名為p0、p1、p2、p3。
步驟3 - 按X座標遞增順序對交點進行排序，即(p0, p1)、(p1, p2)和(p2, p3)。
步驟4 - 填充所有位於多邊形內部的座標對，並忽略交替的座標對。
泛洪填充演算法
有時我們會遇到一個物件，我們希望用不同的顏色填充其區域及其邊界。我們可以用指定的內部顏色繪製此類物件，而不是像邊界填充演算法那樣搜尋特定的邊界顏色。
它不依賴於物件的邊界，而是依賴於填充顏色。換句話說，它用填充顏色替換物件的內部顏色。當不再存在原始內部顏色的畫素時，演算法完成。
同樣，該演算法依賴於四連通或八連通方法來填充畫素。但它不是尋找邊界顏色，而是尋找所有屬於內部的相鄰畫素。
邊界填充演算法
邊界填充演算法顧名思義。該演算法選擇物件內部的一個點，並開始填充，直到到達物件的邊界。為了使該演算法有效，邊界顏色和我們填充的顏色應該不同。
在這個演算法中，我們假設整個物件的邊界顏色相同。邊界填充演算法可以透過4連通畫素或8連通畫素來實現。
4連通多邊形
在這種技術中，使用4連通畫素，如下圖所示。我們在當前畫素的上方、下方、右側和左側放置畫素，這個過程將持續到我們找到具有不同顏色的邊界。
演算法
步驟1 - 初始化種子點(seedx, seedy)、fcolor和dcol的值。
步驟2 - 定義多邊形的邊界值。
步驟3 - 檢查當前種子點是否為預設顏色，如果是，則重複步驟4和5，直到到達邊界畫素。
If getpixel(x, y) = dcol then repeat step 4 and 5
步驟4 - 用填充顏色更改種子點的預設顏色。
setPixel(seedx, seedy, fcol)
步驟5 - 遞迴地對四個相鄰點執行此過程。
FloodFill (seedx – 1, seedy, fcol, dcol) FloodFill (seedx + 1, seedy, fcol, dcol) FloodFill (seedx, seedy - 1, fcol, dcol) FloodFill (seedx – 1, seedy + 1, fcol, dcol)
步驟6 - 退出
這種技術存在一個問題。考慮如下所示的情況，我們嘗試填充整個區域。這裡，影像只被部分填充。在這種情況下，不能使用4連通畫素技術。
8連通多邊形
在這種技術中，使用8連通畫素，如下圖所示。我們像在4連通技術中那樣，在當前畫素的上方、下方、右側和左側放置畫素。
除此之外，我們還在對角線上放置畫素，以便覆蓋當前畫素的整個區域。這個過程將持續到我們找到具有不同顏色的邊界。
演算法
步驟1 - 初始化種子點(seedx, seedy)、fcolor和dcol的值。
步驟2 - 定義多邊形的邊界值。
步驟3 - 檢查當前種子點是否為預設顏色，如果是，則重複步驟4和5，直到到達邊界畫素。
If getpixel(x,y) = dcol then repeat step 4 and 5
步驟4 - 用填充顏色更改種子點的預設顏色。
setPixel(seedx, seedy, fcol)
步驟5 - 遞迴地對四個相鄰點執行此過程。
FloodFill (seedx – 1, seedy, fcol, dcol) FloodFill (seedx + 1, seedy, fcol, dcol) FloodFill (seedx, seedy - 1, fcol, dcol) FloodFill (seedx, seedy + 1, fcol, dcol) FloodFill (seedx – 1, seedy + 1, fcol, dcol) FloodFill (seedx + 1, seedy + 1, fcol, dcol) FloodFill (seedx + 1, seedy - 1, fcol, dcol) FloodFill (seedx – 1, seedy - 1, fcol, dcol)
步驟6 - 退出
4連通畫素技術未能填充下圖中標記的區域，而8連通技術則不會出現這種情況。
內外測試
此方法也稱為計數法。在填充物件時，我們經常需要識別特定點是在物件內部還是外部。我們可以透過兩種方法來識別特定點是在物件內部還是外部。
- 奇偶規則
- 非零纏繞數規則
奇偶規則
在這種技術中，我們將計算從任何點(x,y)到無窮大的直線所穿越的邊數。如果交點數為奇數，則點(x,y)為內部點；如果交點數為偶數，則點(x,y)為外部點。以下示例描述了此概念。
從上圖可以看出，從點(x,y)出發，左側的交點數為5，右側的交點數為3。從兩端來看，交點數都是奇數，因此該點被認為在物件內。
非零纏繞數規則
此方法也用於簡單的多邊形，以測試給定點是否為內部點。這可以用大頭針和橡皮筋來簡單理解。將大頭針固定在多邊形的一條邊上，並將橡皮筋系在上面，然後沿著多邊形的邊拉伸橡皮筋。
當多邊形的所有邊都被橡皮筋覆蓋時，檢查已固定在待測點上的大頭針。如果我們在該點找到至少一個纏繞，則認為該點在多邊形內，否則我們可以說該點不在多邊形內。
在另一種替代方法中，給多邊形的所有邊賦予方向。從待測點繪製一條掃描線到最左邊的X方向。
向上方向的所有邊賦值為1，其他所有邊賦值為-1作為方向值。
檢查掃描線經過的邊的方向值，並將它們加起來。
如果這些方向值的總和非零，則待測點為內部點，否則為外部點。
在上圖中，我們將掃描線經過的方向值相加，總和為1 – 1 + 1 = 1；這是一個非零值。因此，該點被稱為內部點。