种子填充算法详解：从递归实现到扫描线优化

计算机图形学课程做到实验四很多同学的卡点已经从“直线怎么画”变成了“一个多边形怎么填满”。前几次实验跑通了点、线、圆这些基本图元之后到这一步要处理的不再是一条条轮廓线而是一块块有边界的区域。种子填充算法就是这条线路上最直观的一种思路从一个内部点出发像水波一样向外扩散把连通区域逐像素染上目标颜色。这篇文章写给正在做图形学实验的学生也写给需要在软渲染器或小工具里实现区域填充的开发者。我会把实验四的核心拆成几块算法原理、最小可运行的递归实现、递归版在大尺寸图形下的崩溃问题以及替代方案扫描线种子填充。最后补上一套完整实验框架和验收自查清单方便你对着做、对着查、对着写实验报告。1. 实验定位种子填充在光栅图形学中的价值1.1 这个实验要解决的真实问题是什么图形学课程的前几个实验通常围绕“如何在像素网格上画线、画圆”展开那些算法解决的是轮廓生成问题。到了实验四问题性质变了一条封闭曲线已经画好现在需要把曲线内部的区域全部涂上颜色。这个动作在图形学里叫区域填充在图像处理软件里叫油漆桶在游戏引擎里叫泛洪填充本质上是同一件事。区域填充有两类主流路线。一类是先确定多边形边界再按扫描线方向逐行求交点、配对区间并填充叫扫描转换另一类是给定一个内部种子点利用连通性向外蔓延填充所有可达像素叫种子填充。实验四做的是第二类因为它的逻辑更适合初学者理解“区域”的语义区域不是一个函数表达式而是一堆像素的集合边界内和边界外由连通性区分。这个实验在整条教学线里的位置也很关键。前面画线时每个像素的位置由数学公式直接算出后面做裁剪、做三维投影时更多处理的是顶点和变换矩阵。唯独种子填充让学习者第一次直接操作“屏幕上的像素集合”第一次遇到“光栅化之后对象到底是什么”的问题。如果这一步没打通后面做抗锯齿、做模板缓冲、做绘制管线里的光栅化阶段都会觉得隔着一层。1.2 种子填充与边界填充类算法的路线对比实验教材里通常还会提一句扫描线多边形填充也就是多边形扫描转换。有人会问既然扫描线能填多边形为什么还要单独学种子填充这其实是两种不同抽象层次的方法。多边形扫描转换的前提是知道完整的边界方程算法按扫描线求交本质是从几何到像素的“正向推导”。种子填充的前提只需要一个已知的内部点和边界条件它不关心多边形有几条边、是凸是凹甚至边界是直线还是曲线都不影响。凡是能用边界色或背景色区分的闭合区域都可以填。所以种子填充更接近“图像级操作”而不是“几何级操作”。从实验意义上讲它和扫描线填充恰好互补前者适合一次填一个已知区域后者适合批量生成规则多边形的像素数据。如果哪天你要给十几个互相嵌套的复杂岛屿填色扫描线求交点会很痛苦而种子填充只需要把每个岛屿内部点各点一次就行。2. 四连通与八连通连通方向定义与选择依据2.1 像素连通性概念与经典误区种子填充的第一步不是写递归而是搞清楚“连通”的定义。像素网格上两个像素相邻的方式有两种上下左右四个正方向相邻叫四连通再加上四个对角方向叫八连通。这个区别看似简单却在实验里制造了大量“看起来填对了实际上填漏了”的案例。四连通区域指从任一像素出发只能通过上、下、左、右移动到达区域内的其他像素八连通则把斜对角也当成一步。很多人写递归填充时顺手用了八连通因为代码只多了一个方向但后果可能很严重。我把两种方向的计算量列个表方便你对比连通类型邻域像素数递归时每层检查次数典型使用场景四连通44多边形内部填充、区域漫水填充八连通88图像膨胀、细线连通性分析实际图形学实验里默认应该用四连通。原因不在于八连通不对而在于八连通会把某些“仅通过一个角接触”的区域也连通起来。下一小节具体说明这个陷阱。2.2 连通方向不同对填充效果的直接影响举个例子一个区域像两间相邻的屋子中间隔着一道斜向的像素墙。这堵墙如果在四连通规则下是完整的边界那么两间屋子就是两个独立区域。但在八连通规则下因为斜对角移动被允许边界像素的对角空隙会让填充水波从一间屋子渗透到另一间最终整个区域被一起染色。这在填充有细小裂缝、斜边或多边形镂空区域时会带来麻烦。实验里常见的情况是多边形边界用直线算法绘出斜向边界在像素网格上天然呈阶梯状阶梯的转角刚好形成对角像素的“漏点”。如果你用八连通填充色会通过这些漏点跑到边界外面表现出“我怎么填到外面去了”的诡异现象。因此我的建议很简单图形学实验里的种子填充一律实现四连通除非题目明确要求处理八连通区域。你可以在同一个实验里同时写两个版本做对比展示但主功能一定以四连通为准这样既避开了渗透问题也更贴合扫描线填充、边界生成等前序实验的像素模型。3. 基础递归实现能跑通的最小代码与三个关键细节3.1 最小可运行的递归种子填充递归版种子填充是所有版本里最好写、也最容易出事的写法。核心逻辑只有几步判断当前像素是否可填、填色、向四个方向递归。我用类 C 风格写一个最小实现void seedFill4(int x, int y, color boundary, color fill) { if (x 0 || y 0 || x WIDTH || y HEIGHT) { return; } if (screen[y][x] boundary || screen[y][x] fill) { return; } screen[y][x] fill; seedFill4(x 1, y, boundary, fill); seedFill4(x - 1, y, boundary, fill); seedFill4(x, y 1, boundary, fill); seedFill4(x, y - 1, boundary, fill); }调用时只需要传入多边形内部任意一个像素坐标边界色和填充色用全局变量或参数传入即可。这个版本在几十像素的小图形上完全可用适合先跑通逻辑再逐步替换成更稳的版本。3.2 从“能跑”到“跑得对”的三个易错点第一点终止条件必须同时判断边界色和填充色。如果漏掉前者填充会穿过边界继续蔓延如果漏掉后者填充色像素会被反复处理最坏情况是无限递归。这两个判断顺序可以互换但都不能少。第二点种子点必须确认在多边形内部且不在边界上。很多人直接在窗口里随机点一个位置结果点到了边界色或背景色上要么一个像素都不填要么瞬间把整张画布填满。稳妥做法是在画布上先打印出当前鼠标位置的像素颜色判断无误后再调用填充函数。第三点递归调用顺序会影响程序卡顿的体感。先向下再向右、先向左再向上填充过程的水波扩散方向不同。虽然最终结果一致但某些极端形状下先朝大面积方向递归会让程序更快达到栈空间上限表现为“一填就崩”。实验阶段最好把四个方向都保留不要为了“优化”删掉某个方向。4. 递归版的隐藏风险栈溢出与像素级重复入栈4.1 典型崩溃复现与定位过程递归版看起来逻辑完美但一到复杂图形就原形毕露。我复现过这样一个案例在一个 800×600 的画布上画一个带弧边的闭合图形内部面积大约十几万像素然后调用递归填充。程序很快崩溃光标变成一个红色感叹号。起初还以为是画布数组越界但逐行检查后发现没越界。再通过断点观察发现程序在填充到约几万层深度时栈空间耗尽。问题定位到这里就很清晰了这是递归深度过大导致的栈溢出不是逻辑错误。复现这个崩溃并不难。你只需要把矩形变大比如填充一个 300×300 的纯色矩形递归调用次数约等于像素数减去边界像素数。C 语言默认栈空间通常只有几 MB每层递归会保存返回地址和参数几万层深度就能耗尽。如果你用的是 C、Java、Python 这类带较深方法栈的语言可能看起来没事但资源开销也一样夸张。4.2 为什么递归版不适用于大规模填充填充一个矩形区域时每次递归只处理一个像素这意味着每个像素都对应一次函数调用。四连通版本在处理 N 个像素时递归调用次数大约是 N 的常数倍几十万像素就是几十万次调用。更麻烦的是像素级递归做了大量重复检查。同一个像素可能从四个方向都被临近递归访问到虽然填充色判断能挡住重复填色但这些检查仍然消耗时间。画一个简单的 1000×1000 矩形递归版实际访问次数可能接近 400 万次这不是逻辑错是设计上的结构性浪费。一个小技巧可以临时缓解问题把递归改成显式栈模拟也就是用栈保存待处理像素循环处理代替函数递归。这样至少避免了函数调用栈的深度限制。但说实话这个方案的性能仍然不理想因为还是像素级处理。真正实用的优化是把“像素扩散”改成“线段扩散”也就是下一节要讲的扫描线种子填充。5. 扫描线种子填充优化把像素问题变成线段问题5.1 扫描线算法的核心思想与执行流程扫描线种子填充的核心转变是从“每个像素独立压栈”变成“每条连续线段只压一个种子”。你想填充的本质其实是把水平方向上连续的一段像素染成同一种颜色。既然这一段已经被染色后续递归要做的事情只是从这一段出发继续找上下行的新段。压缩到线段级别后栈里的元素不再是几十万像素而是几百几千条线段性能完全不同。具体流程是这样先从种子点所在行出发向左右扩展找到当前行的可填充区间把整个区间填色然后检查上面一行和下面一行找出位于该区间投影范围内的新可填充区间每个新区间只压一个代表种子之后循环弹栈重复上述过程直到栈空。这里面有个容易想偏的地方上下行的新区间不是按整行扫描而是只扫描当前区间左右端点之间的投影范围。因为当前段已经确认是连通的新种子只能从这些列范围内冒出来。如果上下行的可填充区间超出投影范围它一定已经被其他更早入栈的种子覆盖了不需要重复处理。5.2 关键实现与性能对比我把扫描线版本的核心逻辑写成了 Python 风格的伪代码方便理解def scanline_fill(image, seed, boundary, fill): width len(image[0]) height len(image) stack [seed] while stack: x, y stack.pop() # 在当前行向左向右扩展出可填充区间 left x while left - 1 0 and image[y][left - 1] not in (boundary, fill): left - 1 right x while right 1 width and image[y][right 1] not in (boundary, fill): right 1 # 填充整个区间 for cx in range(left, right 1): image[y][cx] fill # 检查上、下相邻行的新种子区间 for ny in (y - 1, y 1): if ny 0 or ny height: continue cx left while cx right: # 跳过已填色或边界像素 if image[ny][cx] in (boundary, fill): cx 1 continue # 找到一个新区间压栈一个种子点 stack.append((cx, ny)) while cx right and image[ny][cx] not in (boundary, fill): cx 1这段代码的关键判断是中途检查到未填色的像素就压入一个种子点然后继续向右跳过整个未填色区间。这样同一行上的连续段永远只对应一个栈元素。我用同样的 1000×1000 矩形做过对比测试实现方式处理粒度栈元素量级填充耗时稳定性递归四连通单个像素约百万级递归调用会发生栈溢出不稳定显式栈像素版单个像素约百万级栈元素较慢但不会栈溢出可用扫描线种子填充连续线段约千级栈元素毫秒级稳定这个对比已经足够说明实验结论递归版适合演示原理扫描线版才适合真正用来干活。6. 配套框架把算法接到一个完整可演示的实验程序中6.1 多边形边界数据的构建方案实验如果只做一个纯函数报告会非常单薄。完整的实验四一般需要展示三样东西一个可交互的绘制窗口、一个可点击的种子点拾取功能、一个能实时看到填充效果的输出区域。边界数据的构建方案很直接前几次实验已经实现了直线和多边形的边界绘制实验四直接复用即可。我在工程里通常维护一个顶点数组先用鼠标点击一系列点形成多边形的顶点序列再调用已有的线段绘制函数把边界逐条画出来。边界绘制的像素颜色设为固定的边界色背景设为背景色两者必须严格区分否则种子填充会同时把边界和背景一起混淆。这里有一个容易被忽视的细节多边形顶点闭合。最后一个顶点必须回到第一个顶点否则边界上会留下一个像素缺口种子填充会通过缺口蔓延到整个背景区域。我建议在画边界时显式补一条从最后一个顶点到第一个顶点的连线并把“是否闭合”做成一个状态标识在界面上显示。6.2 种子点拾取与显示刷新种子点的拾取逻辑不复杂核心是鼠标点击时读取鼠标在当前画布坐标下的像素颜色判断是否属于内部点然后调用填充函数。如果是边界色或者背景色直接弹一个提示指出“种子点不合法”。显示刷新方面最省事的做法是维护一个像素缓冲区每次填色后把缓冲区整体刷新到窗口。数据量大时可以用脏矩形区域刷新的思路只更新发生变化的行区域。但对于实验演示整体刷新足够代码也更清晰。如果想把实验做得更有区分度可以同时跑两个填充算法把递归版和扫描线版的运行时间分别显示出来。用带时间戳的接口在填充前和填充后各取一次时间差值就是填充耗时。在复杂图形下这个时间差会非常直观地体现优化效果写实验报告时也有实际数据支撑。7. 实验验收自查清单与常见错误速查收尾部分我一直不太喜欢写空泛的总结干脆把我在调试过程中反复用到的自查清单列在这里。按这个顺序检查大部分问题都能自己定位。现象可能原因定位与解决思路点击后填充色蔓延到整个画布边界不闭合或边界色与背景色设置相同检查多边形最后一个顶点回连打印鼠标位置像素颜色确认边界色填充没有反应种子点落在了背景色或边界上在点击处打印坐标和颜色值重新确认内部点填充边缘有零星未填像素八连通误用了四连通或四连通误用了八连通检查递归方向的邻域定义是否应该包含斜对角程序崩溃或卡死递归栈溢出或者有几像素小裂隙不断递归换扫描线版本在边界绘制时补缺口填充慢肉眼可见一格一格蔓延像素级处理调用次数过大改用扫描线种子填充再观察性能差异其中最容易踩的坑就是边界不闭合。我见过好几份实验代码画的五边形只用四条边最后一个点没有闭合结果每次填充都是整幅画布变红。这个问题一步就能查出来但确实是最常见的失败原因。另外一个建议是不要只测试一个矩形。多边形的形状会影响算法的表现凹多边形、带洞的区域、斜边较多的图形都是很好的测试样例。我在做实验验收时会给每个图形三秒钟观察填充过程如果出现“漏一格”“穿边界”“卡顿”中的任意一种现象都会建议学生回到上面的表格重新排查。最后分享一个我自己的习惯每次跑填充算法前先打印种子点位置的原始像素颜色。这一行输出只需要两分钟却能避免一半的“为什么点了没反应”的困惑。种子填充就像给房间刷墙一开始选错了起点后面再怎么调整涂料配方都没有用。把起点、边界、算法三件事理清楚实验四就能顺畅收尾了。