三、改进的扫描线填充算法
扫描线填充算法的原理和实现都很简单，但是因为要同时维护 “活动边表（AET）”和“新边表（NET）”，对存储空间的要求比较高。这两张表的部分内容是重复 的，而且“新边表”在很多情况下都是一张稀疏表，如果能对其进行改进，避免出现两张表，就可以 节省存储空间，同时省去从“边表”生成“新边表”的开销，同时也省去了用“新边表”维护“活动 边表”的开销，基于这个原则可以对原始扫描线算法进行改进。
3.1重新设计“活动边表”
改进的算法仍然使用了“活动边表”的概念，但是不再构造独立的“活动边表”，而是直接在 “边表”中划定一部分区间作为“活动边区间”，也就是说，把多边形的边分成两个子集，一个是与 扫描线有交点的边的集合，另一个是与扫描线没有交点的边的集合。要达到这个目的，只需要对“活 动边表”按照每条边的顶点ymax坐标排序即可。这个排序与原始扫描线算法中对“活动边表”的维护 原理是一样的，因为只有边的ymax坐标区间内与扫描线有交点的边才可能是“活动边”。为了避免重 复扫描整个“活动边表”，需要用一个first指针和一个last指针用于标识“活动边区间”。first指 针之前的边都是已经处理过的边，同样，last指针之后的边都是还没有处理的边。每处理完一条扫描 线，都要更新first和last指针位置，调整last指针的位置将ymax大于当前扫描线的边纳入到“活动边 区间”，同时调整first指针将处理完成的边排除在“活动边区间”之外。
如果调整last指针 的依据是边的ymax是否大于当前扫描线，那么调整first指针的依据是什么？也就是如何判断一条边已 经处理完了？方法是在边（EDGE）定义中增加一个dy(Δy)属性，这个属性被初始化成这条边在y方向 上的长度，每处理完一条扫描线，dy都要做减一处理，当dy＝0时，就说明这条边已经不与扫描线相交 了，可以被排除在活动边区间之外。改进的扫描线算法的“边”的完整定义如下：
7 typedef struct tagEDGE2
8 {
9 double xi;
10 double dx;
11 int ymax;
12 int dy;
17 }EDGE2;
EDGE2定义中xi、dx和ymax的含义和原始算法中EDGE的定义相同，只是多了一个 dy属性。
每当处理一条扫描线时，除了“活动边区间”的first指针和last指针需要调整之外 ，还要将first指针和last指针之间的“活动边”按照xi从小到大的顺序排序，以保证填充算法能够用 正确的交点线段序列画线填充。因此，每次调整“活动边区间”的first指针和last指针之后，都要对 “活动边区间”重新排序，也就是说“活动边区间”内的各边的位置并不固定，会随着扫描线的变化 而相应地变化。
仍以图（6）所示的多边形为例，处理扫描线10时的“活动边表”状态如图 （11-a）所示，而处理扫描线8时的“活动边表”状态则如图（11-b）所示。可以看出，当处理扫描线 8时，“活动边区间”内的边的顺序有了调整，因为新加入的P6P1和P1P2两条边与扫描线的交点坐标xi 比P5P6与扫描线的交点坐标xi小，因此排在P5P6前面。
图（11）改进的活动边表结构
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索指针
， 算法
， 区间树
， 扫描线算法
， 活动
， 算法 空间坐标
， 处理
， 区间
， 调整
线段交点算法
十二星座算法、十二生肖算法、铁扫十二支的算法、十二神算法、十二位 纯字母 算法，以便于您获取更多的相关知识。