多邊形填充算法-有序邊表法（掃描線算法）
1.算法的基本思想（掃描線連貫性原理）：
對於一個給定的多邊形，用一組水平(垂直)的掃描線進行掃描，對每一條掃描線都可求出與多邊形邊的交點，這些交點將掃描線分割成落在多邊形內部的線段和落在多邊形外部的線段；而且兩者相間排列。因而，將落在多邊形內部的線段上的全部象素點賦以給定的色彩值。
算法中不須要檢驗每個象素點，而只考慮與多邊形邊相交的交點分割後的掃描線段。
2.算法求解：
對於每一條掃描線的處理 ：
- 1）求交點：首先求出掃描線與多邊形各邊的交點；
- 2）交點排序：將這些交點按X座標遞增順序排序；
- 3）交點匹配：即從左到右肯定落在多邊形內部的那些線段；
- 4）區間填充：填充落在多邊形內部的線段。
3.求交點的方法
- 最簡單的辦法：將多邊形的全部邊放在一個表中，在處理每條掃描線時，從表中順序取出全部的邊，分別求這些邊與掃描線的交點。
- 不使用該方法的緣由：將作一些無益的求交點動做，由於掃描線並不必定與多邊形的邊相交，掃描線只與部分甚至較少的邊相交；所以，在進行掃描線與多邊形邊求交點時， 應只求那些與掃描線相交的邊的交點。
- 肯定與掃描線相交的邊：用邊表來肯定哪些邊是下一條掃描線求交計算時應該加入運算的。
4.邊表（ET）：ET的意義在於爲掃描線提供待加入的新邊信息。
- 創建邊的分類表ET(Edge Table)，每一個結點結構以下： （Ymax ，ΔX ，X Ymin， ）
- Ymax：邊的最大Y值；
- ΔX：從當前掃描線到下一條掃描線之間的X增量（dX/ dY)；
- X Ymin：邊的下端點的X座標；
- next：指針，指向下一條邊。
- 邊的分類表能夠這樣創建：先按下端點的縱座標(y值)對全部邊做桶分類，再將同一組中的邊按下端點X座標遞增的順序進行排序, X座標還相同的按ΔX遞增的順序進行排序。
5.活性邊表AET
- 把與當前掃描線相交的邊稱活化邊AEL(Active Edge List) 。組成的表稱爲活性表AET，其數據域組成以下：
- Ymax ：存放邊的上端點Y座標；
- X ： 邊與當前掃描線交點的X座標；
- ΔX ，next指針 ：同邊表。
- 該數據表示了一條掃描線與某條邊的交點，將這些交點連接起來，就能夠直接獲得要求的全部交點。 在填充過程當中，爲每一條掃描線創建相應的活化鏈表， 它表示了該掃描線要求交點的那些邊，在實用中每一 條邊的活化鏈表的信息與上一條邊的活化鏈表的信息有繼承性，再結合EL表使得創建十分方便。
- 處理掃描線步驟爲：
- (1)對於掃描線Y=yc，若對應的ET中非空，則將其全部的邊從ET 中取出而且插入到邊的活化半表中，並對AET中各邊按X遞增排序；
- (2)若相對於當前掃描線的活化邊表AET非空，則將AET中的邊兩兩依次配對，即第1，2邊爲一對，第3，4 邊爲一對，依次類推，每一對邊與當前掃描線的交點所構成的區段位於多邊形內，依次將這些區段上的點進行着色；
- (3)將當前的掃描線的縱座標Y累加1，即Y=Y+1；
- (4)將邊的活化鏈表AET中知足Y=ymax的邊刪去；
- (5)將邊的活化鏈表AET中剩下的每一條邊的X域累加ΔX，即X=X+ΔX；
- 重複執行(1)。
6.有序邊表法（掃描線算法）舉例:
