《算法的乐趣》第四十五节

本节先讲解原始扫描线填充算法的实现：InitScanLineNewEdgeTable()根据前后相邻顶点判断左、右顶点，对边的ymax做减一修正，水平边不处理……

本节先讲解原始扫描线填充算法的实现：InitScanLineNewEdgeTable()根据前后相邻顶点判断左、右顶点，对边的ymax做减一修正，水平边不处理；ProcessScanLineFill()对每条扫描线依次执行四个操作——将新边按序插入活动边表、按左闭右开原则成对填充、删除已结束的边、更新交点xi并重新排序。算法实现不足百行。

随后介绍改进算法：不再单独维护新边表，而是在边表中直接划分活动边区间，用first、last两个指针界定区间，并为边增加dy属性，dy减到0即表示该边处理完毕。构造时剔除水平边，按ymax从大到小排序，左、右顶点的终点坐标按规则调整。每处理一条扫描线，更新dy与xi，调整指针并重新排序区间，再成对取交点填充。

最后引入边界标志填充算法，它是一类利用扫描线连贯性、以边界为标志的填充算法的总称，本节介绍其中以边为中心的填充算法：对每条边与扫描线的交点，将其右方像素取补，背景色设为M'。