多边形扫描转换算法中的活性边表（ActiveEdgeTable,AET ） 活性边表(Active Edge Table, AET)
在上⼀节中，我们讲解了如何⽣成根据多边形⽣成ET
这⼀节我们讲解活性边和活性边表。
⾸先，什么是活性边？
活性边
与当前扫描线相交的边称为活性边(active edge)， 把这些活性边按与扫描线交点x坐标递增的顺序存⼊⼀个链表中，这个链表就是活性边表(Active Edge Table)。它记录了多边形边沿扫描线的交点序列。 所以活性边表⽰⼀个链表，链表的节点是与当前扫描线相交的边（即活性边）。那么活性边这个结构体包含哪些字段呢？（这⾥为了和前⾯的边表中字段的顺序保持⼀致）: 该边所交的最⾼扫描线的坐标值x: 当前扫描线与该活性边的交点的横坐标
:
从当前扫描线到下⼀条扫描线间x的增量，即当前活性边的斜率的倒数，1/m
形象展⽰：
x 1/m
我们需要知道⼀条边何时不再与下⼀条扫描线相交，以便及时将这样的边从活性边表中删除，避免下⼀步进⾏⽆谓的计算。是该边所交的最⾼扫描线的坐标值，通过这个值就可以知道何时才能“抛弃”该边。
⼀旦⽣成了ET, 扫描线算法就按照下列步骤进⾏处理：
1. 将y置为边表ET中最⼩的y坐标值，即第⼀个⾮空的桶的y值。
2. 将AET初始化为空。
3. 重复以下运算，直到AET和ET都为空：
3.1 从ET的y桶中选择那些的边加⼊到AET中（进⼊边）。（此时AET中就有边了）
3.2 除去AET中那些的项（即与下⼀条扫描线不再相交的边），根据x坐标值进⾏排序（这很容易实现，
因为ET是已排好序的）。
3.3 在扫描线y上，根据AET中的x坐标，两两成对地构成跨段，并对其中的像素以所希望的颜⾊进⾏填充。
3.4 y坐标增加1（即移到下⼀条扫描线的位置）
3.5 对于每⼀条留在AET中的⾮垂直的边，根据新的y值修改x坐标。
总计⼀下：
⾸先从边表中的桶⾮空的最低的扫描线开始做，然后把这些边加⼊活性边表来处理。该边
每做⼀次新的扫描线时，要对已有的边进⾏三个处理：
1.是否被去除，即判断当前扫描线的y值是否等于该边的
2.如果不被去除，第⼆就要对活性边的数据进⾏更新。活性边仅有三个字段: 该边所交的最⾼扫描线的坐标值x: 当前扫描线与该活性边的交点的横坐标
: 从当前扫描线到下⼀条扫描线间x的增量，即当前活性边的斜率的倒数，1/m
所以更新字段信息就是更新x。如何更新，加上即1/m即可。
3.看有没有新的边进来，新的边在ET表⾥，可以插⼊排序插进来，活性边的顺序是x坐标递增的顺序。
y max y max
Δx y max y max y =min y y =y max y max
y max y max
Δx Δx
这个算法过程从来没有求交点，这套数据结构使得你不⽤求交点！避免了求交运算。
光说不练假把式，看下⾯这个例⼦
注意：这⾥按照道理应该是把⼩的扫描线写在下⾯的，这⾥写在了上⾯，那我们就从上⾯往下看就好了。这个例⼦⼀定要看懂呀！看懂了这个例⼦，考试题⽬就会做了。
这⾥没有注意取整的问题
参考⽂献
[1]
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议