★ FEATURED ARTICLE 1. 这个实验到底在做什么从旋转变换到“给图形上色”图像编辑软件里的“油漆桶”工具大家多少都用过——点一下封闭区域整个范围内的颜色就被替换成你想要的颜色。图形学课程做到第四个实验核心任务就落到了这个功能的地基种子填充算法。前面几个实验如果都在画线、画圆、做变换那这个实验就是从“画图形”迈向“填图形”的关键一步。种子填充的思路其实非常直接给定一个封闭区域内的一点称为种子点从这个点出发不断向外扩散把区域内所有与种子点颜色相同或未被填充的像素都填上目标颜色。听起来像一个“扩散染色的过程”但真正自己动手实现一遍你会发现里面藏着递归深度、边界封闭、颜色判定、栈溢出这些老熟人——任何一个处理不好程序要么直接崩溃要么把不该填的区域填得乱七八糟。这个实验适合正在学习图形学基础算法的学生也适合工作中突然需要处理位图区域处理的开发者。它不像光栅化光束发射那样抽象核心逻辑用手推都能跑通但想要写出一份稳定、高效、能拿得出手的实现需要你对递归、栈、边界条件都有足够清晰的认知。我用 C 配合 EasyX 图形库做了完整实现代码框架换成 OpenGL 或者其他图形框架也能直接迁移因为算法本身与渲染 API 无关。2. 整体思路设计先用“四连通”想清楚再谈优化2.1 种子填充到底在遍历什么在动手写代码之前先想明白一个根本问题填充的本质是遍历。从一个种子点出发你要不断访问它的邻接像素判断这些像素是否“值得填入”然后继续向外扩展。这里的“邻接”有两种定义四连通只考虑上下左右四个方向八连通还多算了左上、右上、左下、右下四个对角方向。初学者比较容易想当然地用八连通因为直觉上觉得“八个方向都走一遍填得更快”。但这里有个关键区别四连通能够正确填充的区域如果用八连通填充有可能通过斜向路径绕过本该阻隔的边界线把不该连通的两个区域串到一起。反过来说如果边界线本身存在对角线上的“缝隙”四连通更容易被边界挡住八连通则可能沿着对角缝隙渗出去。在实验场景里画出来的多边形边界通常是一条像素宽此时四连通更符合人们对边界封闭的直觉所以我强烈建议第一次实现就用四连通后面再根据需求扩展八连通。在实际代码中四连通的扩散逻辑是取出当前点对它上下左右四个邻居逐一判断——如果该邻居在画布范围内、颜色不等于边界色、也不等于目标填充色就把它压入待处理队列。等队列里的点全部处理完填充就完成了。2.2 三个实现版本的演进路径我见过不少同学的实验报告只写了一版递归实现能跑就万事大吉。但如果你去仔细看运行效果画布稍大一点比如 600×400 的绘图区递归填充简单多边形通常还能撑住一旦碰到复杂多边形或者区域边界起伏比较厉害程序直接崩溃退出的情况非常常见。所以这次实验我没有只停留在“能跑”的层面而是按三个版本递进实现版本一递归版种子填充用于理解算法思想验证小规模区域的正确性版本二显式栈替代递归调用解决栈溢出问题代码仍然简单版本三扫描线种子填充逐行处理性能显著提升这也是实际工程中最常用的变体。这三个版本不是三条平行的路线而是一条递进优化的路径。实验报告如果能把三个版本的演变逻辑讲清楚老师很难不给高分更重要的是你真正理解了每一种写法解决的是什么问题以后做图像分割、连通域标记、区域生长这些进阶工作时都能少吃不少亏。2.3 为什么实验环境选 EasyX 而不是原生 OpenGL我这次用的是 EasyX 图形库配合 C 环境一个很重要的原因是它把像素点操作封装得极其简单putpixel(x, y, color)往画布上写点getpixel(x, y)读取指定坐标的颜色值不需要搭建渲染管线也不涉及 GPU 资源管理。种子填充算法的核心在像素级操作上EasyX 提供的接口正好把注意力集中在算法逻辑本身非常适合课程实验的场景。当然如果你的课程指定了 OpenGL 或者 Qt算法本身不会变你只需要把“读取颜色”和“写入颜色”两个操作替换成对应框架的像素读写接口即可。我的习惯是先把算法逻辑和绘制操作彻底分离写一个独立的seedFill函数只接收画布数据、种子坐标、填充色、边界色这几个参数这样移植起来基本零成本。3. 递归种子填充的实现懂原理更要懂它为什么“爆”3.1 完整可运行的递归版本代码先给出一版最直观的递归实现。为了演示方便我基于 EasyX 写了一个完整的填充流程#include graphics.h #include conio.h // 四连通递归种子填充 void FloodFill4(int x, int y, COLORREF fillColor, COLORREF borderColor) { // 超出画布范围直接返回 if (x 0 || x 640 || y 0 || y 480) return; COLORREF currentColor getpixel(x, y); // 如果当前像素是边界色或者已经被填充过停止递归 if (currentColor borderColor || currentColor fillColor) return; // 填充当前像素 putpixel(x, y, fillColor); // 向四个方向递归扩散 FloodFill4(x 1, y, fillColor, borderColor); FloodFill4(x - 1, y, fillColor, borderColor); FloodFill4(x, y 1, fillColor, borderColor); FloodFill4(x, y - 1, fillColor, borderColor); } int main() { initgraph(640, 480); setbkcolor(WHITE); cleardevice(); // 绘制一个矩形边界颜色为黑色 setcolor(BLACK); rectangle(100, 100, 300, 200); // 在矩形内部任取一点填充为红色 FloodFill4(150, 150, RED, BLACK); _getch(); closegraph(); return 0; }这段代码的逻辑足够清晰拿到当前点坐标判断颜色——是边界或者已经填充就无条件返回否则写颜色接着向四个方向递归。小矩形测试完全没问题填充 200×100 的区域效果也很正常。但如果你把矩形扩大到接近全屏比如rectangle(10, 10, 630, 470)递归深度会瞬间飙升到接近十万层程序十有八九直接中断。3.2 递归实现的两个隐藏致命点先说“颜色相等”这个判断条件。getpixel返回的COLORREF是一个 32 位整数值如果你在绘图时设置的边界色和填充色都是精确创建的纯色直接用比较问题不大。但假如图形被抗锯齿处理过或者画布上有渐变、抖动之类的效果边界像素的颜色并不是唯一的判断就会漏掉边界让填充越过不该越过的地方。这种问题在基础实验里不常见但一旦扩展到真实图像处理你就需要引入颜色容差判断——比如 RGB 三个通道分别比较差值在某个阈值内就视为相同颜色。更隐蔽的问题是“重复判断”带来的性能损耗。递归填充一个矩形区域内部每个像素都会被四个方向的邻居各访问一次也就是说平均每个像素至少要执行 4 次颜色读取和判断。填充 200×100 的区域光是颜色读取调用就高达八万次这还没有算递归的函数调用开销。所以在测试时你会明显感觉到大区域填充不仅可能崩溃即使不崩溃也明显卡顿。3.3 显式栈替换递归把隐式开销摆到桌面上递归版本崩溃的本质是函数调用栈不够用。每一次函数调用都要在系统栈上分配一段空间保存返回地址、局部变量和参数深度达到几万层时栈空间必然耗尽。解决思路也很直接不用系统栈自己维护一个数组或者链表来模拟栈把“待访问的点”显式地存进去。#include stack #include graphics.h void FloodFill4_Stack(int seedX, int seedY, COLORREF fillColor, COLORREF borderColor) { std::stackstd::pairint, int pixelStack; pixelStack.push({seedX, seedY}); while (!pixelStack.empty()) { auto [x, y] pixelStack.top(); pixelStack.pop(); if (x 0 || x 640 || y 0 || y 480) continue; COLORREF currentColor getpixel(x, y); if (currentColor borderColor || currentColor fillColor) continue; putpixel(x, y, fillColor); // 四个方向入栈注意顺序不影响最终效果 pixelStack.push({x 1, y}); pixelStack.push({x - 1, y}); pixelStack.push({x, y 1}); pixelStack.push({x, y - 1}); } }这段代码和递归版本在扩散顺序上略有差别但最终填充结果完全一样。它最大的优势是把栈空间从系统栈转移到了堆上只要你的std::stack能动态增长填充任意大小的矩形区域都不会因为“栈溢出”崩溃。当然这个版本仍然存在重复访问的问题一个点可能被四次入栈栈内元素峰值很高但作为一个过渡版本它的简单性和正确性非常值得保留。4. 扫描线种子填充一次填充一整行性能质的提升4.1 算法思想从“逐点扩散”到“区间扩展”如果你手动模拟一下显式栈版本的运行过程会发现大量操作是重复的——“一个像素被反复判断四次”带来的时间开销极其浪费。扫描线种子填充算法解决这个问题的思路非常聪明不再一个个处理像素而是先找到一条水平线段一次性填充整段连续的、可填充的像素然后在这条线段的上下相邻行中寻找新的可填充区间把它们作为新的种子记录下来。这样做有几个立竿见影的好处。第一每个像素的访问次数从平均 4 次降到接近 1 次因为整行是一次性填进去的第二栈中保存的元素从“像素点”变成了“线段种子”数量级从 O(面积) 降到了 O(行数)第三算法天然支持后续扩展成任意复杂多边形区域因为边界判断只看左右端点。4.2 核心实现步骤与关键代码我拆解出四个核心步骤来实现扫描线版本从种子点开始沿当前行向左和向右分别扫描找到连续可填充区间的左端点和右端点用fillColor填充这个完整区间分别检查上一行和下一行在与当前区间有交叠的 x 范围内寻找新的可填充区间并把每个区间的任意一点作为新种子入栈从栈中取出一个种子回到步骤 1直到栈为空。#include stack #include graphics.h void ScanLineFill(int seedX, int seedY, COLORREF fillColor, COLORREF borderColor) { struct Seed { int x, y; }; std::stackSeed seedStack; seedStack.push({seedX, seedY}); while (!seedStack.empty()) { Seed seed seedStack.top(); seedStack.pop(); int x seed.x; int y seed.y; // 当前点不在区域内是边界或已填充跳过 if (getpixel(x, y) borderColor || getpixel(x, y) fillColor) continue; // 向左找区间左端点 int left x; while (getpixel(left - 1, y) ! borderColor getpixel(left - 1, y) ! fillColor left - 1 0) { left--; } // 向右找区间右端点 int right x; while (getpixel(right 1, y) ! borderColor getpixel(right 1, y) ! fillColor right 1 640) { right; } // 一次性填充整行 for (int i left; i right; i) { putpixel(i, y, fillColor); } // 检查上下两行寻找新的种子区间 for (int row y - 1; row y 1; row 2) { if (row 0 || row 480) continue; int i left; while (i right) { // 找到可填充区间的起始点 bool findStart false; int startX i; while (i right getpixel(i, row) ! borderColor getpixel(i, row) ! fillColor) { findStart true; i; } if (findStart) { // 取区间内任意一点作为新种子 seedStack.push({(startX i - 1) / 2, row}); } // 跳过不可填充区域 while (i right (getpixel(i, row) borderColor || getpixel(i, row) fillColor)) { i; } } } } }这段代码值得仔细读几遍。找左端点时用while循环逐个向左移动直到碰到边界或者已经填充的颜色填充整个区间后再对相邻两行做同样的区间检测。有个细节容易被忽略检查上一行时相邻行可能出现多个互不相连的可填充区间所以我在for循环内部用两个while分别处理“可填充段”和“不可填充段”确保每一个独立区间都能生成一个新种子。这也是扫描线版本比朴素递归“更快”的关键所在。4.3 越界与边界条件的防护扫描线版本里最容易出 bug 的地方是数组越界。代码中我分别在左端点、右端点以及检查上下两行时都加了判断left - 1 0、right 1 640、row 0 || row 480。这些条件缺一不可。我在初版实现中漏掉了left - 1 0这个条件填充贴近画布左侧边界的多边形时直接读取了坐标 -1 的像素导致程序异常退出。这种错误在调试时不太容易一眼看出来因为图形区域本身显示正常但运行几分钟后偶发性崩溃。另外还有一个让很多人困惑的问题如果待填充区域内部本身已经存在一些和目标填充色相同的像素扫描线算法会把它们当作“已经填过”而跳过导致部分区域漏填。比如你要把一个白色矩形填充成红色但矩形内部已经有一个红色小圆算法会在碰到红圆的那一列停下来造成填充不完整。处理方法是如果初始区域内部允许出现与填充色相同的像素需要引入“访问标记数组”来记录哪些像素已经被算法处理过而不是单纯依赖颜色判断。5. 常见问题与排查技巧实录5.1 典型问题速查表我整理了一份自己在编码和调试过程中遇到过的典型问题对照表排查时对付着看会很有帮助现象可能原因解决方法程序在填充中途直接退出递归版本栈溢出改用显式栈或扫描线种子填充填充越过边界蔓延到外部边界颜色不一致或边界不封闭统一边界色检查绘图接口是否抗锯齿检查多边形是否完全闭合区域内部分像素未被填充扫描线判断了“已填充”的颜色改用访问标记数组记录状态不要依赖颜色本身填充过程肉眼可见地卡顿像素反复访问效率低用扫描线版本减少重复判断填充区域边缘出现毛刺或漏点八连通穿过对角缝隙对矩形、多边形实验改用四连通种子点取在边界上初始点颜色即边界色立即返回检查点击区域确保种子点确实在封闭区域内填充结果颜色偏色COLORREF的 RGB 通道混用统一使用RGB(r, g, b)宏创建颜色这张表里的每一条我几乎都实际踩过。最典型的是第一项“栈溢出”它一般不会每次必现而是当多边形面积较大或者形状复杂时偶发消失调试运行出现这种情况最让人头疼——建议直接在测试阶段就换成非递归版本别等火苗烧到眉毛。5.2 调试技巧用“慢填充”模式观察算法执行过程如果你在调试种子填充算法时觉得“代码看起来没问题但结果就是不对”我建议不要直接跑完整填充而是加一个“慢速模式”。做法很简单在putpixel之后插入一个Sleep(5)并实时刷新屏幕。这样你可以人眼追踪算法的扩散路径看到底是哪个方向越过了边界哪个区域被漏掉了。这对检查递归顺序、扫描线的区间错位、以及边界缝隙问题特别有效。比如我第一次实现扫描线版本时检查相邻行的逻辑写错了导致某些行被重复扫描某些行被完全跳过。用慢填充模式跑一次肉眼能看到填充路径出现“跳空”现象顺着跳空的位置一查代码马上就能定位到问题比单步断点强得多。5.3 从实验到应用种子填充不止是“填色”做完这个实验不妨再想想它能延伸到哪里。种子填充的核心就是“从一个点出发按照连通性扩散到整个目标区域”这种思路在图像处理中几乎无处不在连通域标记会用类似的遍历方式给不同物体贴上不同的标签图像分割中的区域生长算法本质上就是种子填充加一个相似度判断Photoshop 的魔棒工具用的是带颜色容差的填充变体甚至一些游戏里的泛洪填充比如扫雷中点击空白格自动展开一片区域底层也是这个算法。所以我的建议是别把这个实验当作一个“交差”的任务。递归版本、显式栈版本、扫描线版本三个层次你完整写一遍对“递归怎么把问题缩小”“栈为什么能替代递归”“如何利用数据结构的特性换性能”这三组问题的理解会有一个质的飞跃。后面学到分治法、图遍历时你会发现这些思想其实一脉相承。最后分享一个小技巧如果你打算把扫描线版本进一步优化可以考虑先对多边形的每一条边做一次“边界标记”把所有边界像素存入哈希集之后判断“是否可填充”时直接查哈希集复杂度降到 O(1)比反复调用getpixel要快得多。我当时在课程实验中顺手试了一下填充速度又提升了将近一倍这也给实验报告加分不少。这个实验做完图形学里“区域填充”这块地基就算真打牢了。
阅读完成 · 觉得有帮助？
