多边形填充算法-有序边表法（扫描线算法）

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.有序边表法（扫描线算法）举例: