如何给图形"涂色"

多边形的填充

前面我们讲了直线和圆的绘制，想必你现在已经可以绘制一些基础图形了。
但是，现在存在一个问题：我们绘制的都是线条，并不是我们平常看到的实心图形——缺少了颜色的填充。

这一篇文章，我将解释如何填充我们之前绘制的图形。

多边形的填充主要分为两种方式：

• 多边形的扫描转换：通过确定穿越区域的扫描线的覆盖区间来填充
• 区域填充：从给定的位置开始涂描直到指定的边界条件为止

在讨论算法之前，先区分两种多边形表示方式：

扫描转换多边形和区域填充，就是从顶点表示到点阵表示的转换过程。

多边形的扫描转换

x-扫描线算法

基本思想：用一条水平扫描线，从上到下扫描整个多边形，求出每一行的图形内部像素并填充。

算法步骤：

1. 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大 y 值（ymin 和 ymax）
2. 从 y = ymin 到 y = ymax，每次用一条扫描线进行填充
3. 对一条扫描线进行填充的过程分为四个步骤：
   • a. 求交：计算扫描线与多边形各边的交点
   • b. 排序：将所有交点按 x 坐标递增排序
   • c. 交点配对：将排序后的交点两两配对（第 1 与第 2、第 3 与第 4……）
   • d. 区间填色：在每一对交点之间填充像素

但是，算法现在还存在一个问题：

如图所示，当扫描线与多边形顶点相交时，我们需要决定交点的取舍。

为了解决这个问题，我们做出如下规定——当扫描线与多边形的顶点相交时：

• 若共享顶点的两条边分别落在扫描线的两边，交点只算一个
• 若共享顶点的两条边在扫描线的同一边，交点算作零个或两个

如下图所示：

补充说明：第一种情况（异侧）是最常见的——顶点恰好是边的极值转折点，扫描线从一条边穿入、从另一条边穿出，交点只需算一次。第二种情况（同侧）出现在多边形的局部极值点（如尖顶或尖底），此时扫描线碰到顶点但没有穿越内部，所以算零个或两个交点以保持配对正确。

但是，扫描线算法存在效率问题：对于每一行扫描线，我们都要计算每一条边和扫描线的交点，即使这条边并没有和当前扫描线相交。边数多时开销很大。

下面，我们介绍一种基于扫描线算法的改进算法。

有效边表算法

改进原理

核心思想很简单：

• 处理一条扫描线时，仅对”有效边”求交——即与当前扫描线真正相交的边
• 利用扫描线的连贯性：相邻扫描线的交点可以通过简单增量计算，不需要重新解方程
• 利用多边形边的连贯性：一条边往往在连续多条扫描线中都有效

很多边在连续多条扫描线中一直有效，所以没必要每一行都遍历所有边，只需要维护当前活跃的边即可。

对于一条边，两次连续扫描前后，y 坐标增加 1，x 坐标增加一个固定量 dx = Δx / Δy。这利用了增量原理，和 Bresenham 的思想完全一样——用加法代替乘除。

数据结构

算法需要维护两个表：

每条边的数据结构：

1
2
3
4
5
6

struct Edge {
    int   ymax;   // 边的上端点 y 值（边失效的扫描线）
    float x;      // 当前扫描线与该边的交点 x 坐标
    float dx;     // 从当前扫描线到下一条扫描线，x 的增量（= Δx/Δy）
    Edge* next;   // 链表指针
};

ET 的构造方式：

• ET 是一个以 ymin 为索引的数组：ET[ymin] 存储所有从该行”激活”的边
• 对于多边形的每条边，计算它的 ymin（较小 y 端点），将边节点插入 ET[ymin] 链表中
• 同一 ymin 的边以链表方式存储

算法步骤

每一条扫描线的处理流程和扫描线算法基本一致，区别在于加入了对 ET 和 AET 的维护：

1. 从 ET 加入新边：将 ET[y] 中的边移入 AET
2. 删除结束边：从 AET 中移除 ymax == y 的边（该边已失效）
3. 更新交点 x：AET 中每条边的 x += dx
4. 按 x 排序：对 AET 按当前 x 值重新排序
5. 两两配对填充：相邻两交点配对，填充区间内的像素

注意：步骤 3 的更新发生在填充之后（为下一条扫描线准备 x 值）。新加入 AET 的边在加入时就已经携带了 y = ymin 处的 x 值，所以当前扫描线的填充使用的是更新前的 x。

完整示例演练

下面我们用一个具体的五边形来完整走一遍算法流程，理解 ET 和 AET 如何协同工作。

示例多边形顶点：

1

P0(2, 2), P1(7, 1), P2(11, 5), P3(8, 9), P4(1, 7)

第一步：构造 ET（边表）

将五条边分别处理，计算每条边的 ymin、ymax、x_ymin（在 ymin 处的 x 坐标）以及 dx：

dx 的含义：dx = Δx/Δy，即 y 每增加 1，x 的变化量。dx > 0 时边向右走，dx < 0 时边向左走。

将边按 ymin 归类，得到 ET：

1
2
3
4
5
6
7
8
9

ET[1]: e0(ymax=2, x=7.00, dx=-5.00) → e1(ymax=5, x=7.00, dx=1.00)
ET[2]: e4(ymax=7, x=2.00, dx=-0.20)
ET[3]: (空)
ET[4]: (空)
ET[5]: e2(ymax=9, x=11.00, dx=-0.75)
ET[6]: (空)
ET[7]: e3(ymax=9, x=1.00, dx=3.50)
ET[8]: (空)
ET[9]: (空)

第二步：逐扫描线遍历 AET

y = 1：

• ① 从 ET[1] 加入 e0、e1
• ② 删除 ymax == 1：无
• ③ AET = [e0(7.00), e1(7.00)]，排序后不变
• ④ 配对填充：(7.00, 7.00)，仅 x=7 一个像素（多边形底部尖点）
• ⑤ 更新为下一条扫描线：e0.x = 7.00−5.00 = 2.00，e1.x = 7.00+1.00 = 8.00

y = 2：

• ① 从 ET[2] 加入 e4（x=2.00）
• ② 删除 ymax == 2：e0 失效，移除
• ③ AET = [e4(2.00), e1(8.00)]，排序后不变
• ④ 配对填充：区间 (2.00, 8.00)，填充 x = 2~8 共 7 个像素
• ⑤ 更新：e4.x = 2.00−0.20 = 1.80，e1.x = 8.00+1.00 = 9.00

y = 3～4：无新边加入和删除，每行仅更新 x 后排序填充。

y = 5：

• ① 从 ET[5] 加入 e2（x=11.00）
• ② 删除 ymax == 5：e1 失效，移除
• ③ AET = [e4(1.40), e2(11.00)]
• ④ 配对填充：区间 (1.40, 11.00)，填充 x = 2~11
• ⑤ 更新：e4.x = 1.40−0.20 = 1.20，e2.x = 11.00−0.75 = 10.25

y = 7：

• ① 从 ET[7] 加入 e3（x=1.00）
• ② 删除 ymax == 7：e4 失效，移除
• ③ AET = [e3(1.00), e2(9.50)]
• ④ 配对填充：区间 (1.00, 9.50)，填充 x = 1~9
• ⑤ 更新：e3.x = 1.00+3.50 = 4.50，e2.x = 9.50−0.75 = 8.75

y = 9：

• ① 从 ET[9] 加入：无
• ② 删除 ymax == 9：e2、e3 均失效
• ③ AET 变为空，算法结束

将所有扫描线的填充区间汇总如下：

区域填充

区域是指已经表示成点阵形式的填充图形，它是像素的集合。与扫描转换从”顶点表示”出发不同，区域填充从”点阵表示”出发，在区域内改变像素颜色。

4-邻接点与 8-邻接点

在区域填充中，”相邻”的定义决定了扩散的方向和范围：

选择哪种邻接方式取决于边界定义：4-连通边界需配合 8-连通填充（反之亦然），否则可能出现填充越界。

边界填充算法（Boundary-fill Algorithm）

算法思想：从一个种子像素开始，只要相邻像素与边界颜色不一致，就不断向外扩散填充。

算法步骤：

1. 选定一个种子点 (x, y)，设定要填充的颜色和边界颜色
2. 检查当前像素：如果它已经是边界颜色或已经填充过，则停止（递归终止条件）
3. 将当前像素设为填充颜色
4. 向四个（或八个）邻接方向递归重复步骤 2~3，直到所有连通区域被填满

洪水填充算法（Flood-fill Algorithm）

算法思想：从一个种子像素开始，只要相邻像素与目标颜色（待替换的旧颜色）一致，就继续扩散。与边界填充的区别在于：它不需要知道边界颜色，而是通过替换”同类颜色”来工作。

算法步骤：

1. 选定一个种子点 (x, y)，设定目标颜色（待替换的旧颜色）和填充颜色
2. 检查当前像素：如果它不是目标颜色，则停止（递归终止条件）
3. 将当前像素设为填充颜色
4. 向四个（或八个）邻接方向递归重复步骤 2~3，直到所有同色区域被替换

但是以上两种算法都存在一些明显的问题：

1. 逐像素扩散太慢：每个像素都要递归，填充一个大矩形区域需要大量函数调用
2. 递归/栈爆炸：递归深度等于区域面积，稍大的区域就会导致栈溢出
3. 扩散路径混乱：像素被重复访问，缺乏空间连贯性的利用

下面介绍一种结合扫描线思想的优化算法。

扫描线种子填充算法

算法思想：不再”一个像素一个像素地扩散”，而是按水平扫描线整段填充。利用区域的像素连续性，一次性填完一整行，再将上下相邻行的未填充段入栈。

算法步骤：

1. 将种子点 (x, y) 压入栈
2. 从栈中弹出一个点，从该点向右扩展，逐个像素填充直到碰到边界颜色，记录右边界 x_right
3. 从该点向左扩展，逐个像素填充直到碰到边界颜色，记录左边界 x_left
4. 当前行填充区间为 [x_left+1, x_right-1]，一次性整段填完
5. 检查上一行（y-1）在区间内的像素，找到其中未填充的连续段，将每段的起始点压入栈
6. 检查下一行（y+1）同理，将未填充连续段的起始点压入栈
7. 重复步骤 2~6，直到栈为空

和普通的递归填充算法相比，扫描线种子填充有质的提升：

本质上是从”图遍历“升级为”区间扫描“。

多边形扫描转换与区域填充方法比较

联系

• 都是光栅图形面着色，用于真实感图形显示
• 可以相互转换：
  • 扫描转换 → 区域填充：给定多边形内一点为种子点，用直线算法将多边形边界表示成八连通区域后，扫描转换问题转化为区域填充
  • 区域填充 → 扫描转换：若已知多边形顶点，区域填充问题可转化为多边形扫描转换

区别

这次的插图来自画师画师JW

图片地址：https://www.pixiv.net/artworks/144486189