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.有序邊表法（掃描線算法）舉例:

?

轉載于:https://www.cnblogs.com/dongzhiwu/p/8349954.html

總結

以上是生活随笔為你收集整理的多边形填充算法-有序边表法（扫描线算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。