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

本节先总结了扫描线种子填充算法的实现要点：FillLineRight()和FillLineLeft()从种子点向两侧填充并返回点数，以调整当前区间……

本节先总结了扫描线种子填充算法的实现要点：FillLineRight()和FillLineLeft()从种子点向两侧填充并返回点数，以调整当前区间；SearchLineNewSeed()在新扫描线上寻找种子点入栈，外层循环保证区间被障碍点分段后每段都能找到种子点，SkipInvalidInLine()负责跳过障碍点。至此种子填充算法介绍完毕。

随后引入扫描线填充算法，它面向矢量图形，无需指定种子点，适合自动图形处理。其基本思想是用水平扫描线求与多边形边的交点，按x排序后两两配对填充，分求交、排序、填充、换线四步。为提高效率，算法维护活动边表（AET）记录当前扫描线相交的边，并利用步进关系Δx=-b/a直接推算下一条扫描线的交点，另设新边表（NET）存放每条扫描线首次出现的边。实现时还需处理三类细节：顶点分左右上下四种，左右顶点通过修改ymax排除终点以平衡交点奇偶，上下顶点可算0个或2个交点；水平边直接画出后忽略；填充采用“左闭右开”原则避免越界。最后给出新边表的数据结构及多边形y范围的初始化方法。