活性边表(Active Edge Table, AET)

在上一节中，我们讲解了如何生成根据多边形生成ET

这一节我们讲解活性边和活性边表。

首先，什么是活性边？

活性边

与当前扫描线相交的边称为活性边(active edge)，

把这些活性边按与扫描线交点x坐标递增的顺序存入一个链表中，这个链表就是活性边表(Active Edge Table)。它记录了多边形边沿扫描线的交点序列。

所以活性边表示一个链表，链表的节点是与当前扫描线相交的边（即活性边）。

那么活性边这个结构体包含哪些字段呢？（这里为了和前面的边表中字段的顺序保持一致）

• $y_{max}$ymax​: 该边所交的最高扫描线的坐标值$y_{max}$ymax​
• x: 当前扫描线与该活性边的交点的横坐标
• $\Delta x$Δx: 从当前扫描线到下一条扫描线间x的增量，即当前活性边的斜率的倒数，1/m

形象展示：

$y_{max}$ymax​	x	1/m

我们需要知道一条边何时不再与下一条扫描线相交，以便及时将这样的边从活性边表中删除，避免下一步进行无谓的计算。$y_{max}$ymax​是该边所交的最高扫描线的坐标值，通过这个值就可以知道何时才能“抛弃”该边。

一旦生成了ET, 扫描线算法就按照下列步骤进行处理：

1. 将y置为边表ET中最小的y坐标值，即第一个非空的桶的y值。
2. 将AET初始化为空。
3. 重复以下运算，直到AET和ET都为空：
   3.1 从ET的y桶中选择那些$y_{min} = y$ymin​=y的边加入到AET中（进入边）。（此时AET中就有边了）
   3.2 除去AET中那些$y = y_{max}$y=ymax​的项（即与下一条扫描线不再相交的边），根据x坐标值进行排序（这很容易实现，因为ET是已排好序的）。
   3.3 在扫描线y上，根据AET中的x坐标，两两成对地构成跨段，并对其中的像素以所希望的颜色进行填充。
   3.4 y坐标增加1（即移到下一条扫描线的位置）
   3.5 对于每一条留在AET中的非垂直的边，根据新的y值修改x坐标。

总计一下：
首先从边表中的桶非空的最低的扫描线开始做，然后把这些边加入活性边表来处理。
每做一次新的扫描线时，要对已有的边进行三个处理：
1.是否被去除，即判断当前扫描线的y值是否等于该边的$y_{max}$ymax​
2.如果不被去除，第二就要对活性边的数据进行更新。活性边仅有三个字段

• $y_{max}$ymax​: 该边所交的最高扫描线的坐标值$y_{max}$ymax​
• x: 当前扫描线与该活性边的交点的横坐标
• $\Delta x$Δx: 从当前扫描线到下一条扫描线间x的增量，即当前活性边的斜率的倒数，1/m

所以更新字段信息就是更新x。如何更新，加上$\Delta x$Δx即1/m即可。
3.看有没有新的边进来，新的边在ET表里，可以插入排序插进来，活性边的顺序是x坐标递增的顺序。

这个算法过程从来没有求交点，这套数据结构使得你不用求交点！避免了求交运算。

光说不练假把式，看下面这个例子

注意：这里按照道理应该是把小的扫描线写在下面的，这里写在了上面，那我们就从上面往下看就好了。这个例子一定要看懂呀！看懂了这个例子，考试题目就会做了。
这里没有注意取整的问题

参考文献

[1] 中国大学慕课 计算机图形学国家精品课程 中国农业大学