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

本节首先完成中点画椭圆算法的推导：根据中点在椭圆内外，判别式 d 的增量分别为 b(2x+2)+a(-2y+3) 和 a(-2y+3)，起点为 (0,b)……

本节首先完成中点画椭圆算法的推导：根据中点在椭圆内外，判别式 d 的增量分别为 b(2x+2)+a(-2y+3) 和 a(-2y+3)，起点为 (0,b)，初值 d0=b+a(-b+0.25)，上部区域循环至 2b(x+1)≥2a(y-0.5)，下部至 y=0，绘制时利用椭圆对称性一次画出四个对称点。由于判别式含浮点运算，效率受影响，于是介绍 Bresenham 椭圆算法，用 D=d1-d2 作判别式，D<0 取 P1 否则取 P2，完全化为整数运算，并给出上下部区域各自的递推公式与初值 D0=2b-2ab+a。

随后进入多边形区域填充。种子填充算法基于递归搜索，按搜索方向分为 4-联通与 8-联通：注入填充把连通区域内指定颜色的点全部替换，不强调边界；边界填充则以边界为递归终止条件，边界内所有颜色都改为指定色，即画图软件"油漆桶"的原理。二者递归开销大，故提出扫描线种子填充算法，改为沿水平扫描线逐段填充，只把每段起点压栈。其步骤为：种子点入栈；取栈顶作当前种子；沿当前扫描线左右填充至边界并记下 [xLeft,xRight]；再在相邻上下两条扫描线的该区间内搜索，把找到的最右非边界点作新种子入栈，循环至栈空。文中还用两例说明：相邻扫描线区间更大且连续时，靠左右填充即可补全；若中间有边界阻挡，则靠右取点的原则会让该行在后续扫描中再次获得种子，从而分段填满。