企业官网建设流程全解析

1. 为什么已经有了扫描线和种子填充，还要再来一种边标志算法

多边形区域填充算法这个系列写到第十二篇，前面把扫描线填充、种子填充都拆开讲过一遍。在我刚接触图形学的那几年，一直觉得扫描线算法是软件渲染器里唯一的正路，直到一次做地图轮廓渲染时被活活恶心到：几千条边的多边形，每帧要重新构建边表、活性边表，扫描线之间的交点还要排序，基本把所有优化空间都堵死了。那之后我重新去翻了几种被冷落的算法，边标志填充就是其中之一，它不见得在所有场景下比扫描线快，但思路和适用面完全不同，值得单独写一篇。

什么是边标志算法，一句话概括：先只把多边形边界经过的像素打上标记，然后逐行扫描，遇到标记就翻转一次“当前是否在多边形内部”的状态，状态为真时填充该行像素。这个思想很朴素，但它把“多边形边界解析”和“内部像素填充”彻底拆成两个独立问题，换来的是代码简单、无浮点排序、天然可并行这些扫描线算法做梦都想要的特点。

1.1 扫描线算法：精确但维护成本高

扫描线算法不是不好，而是好得“太重”。它的核心是维护一张活性边表，每处理一条扫描线，要更新交点的x坐标、判断边是否失效、插入新边、最后按x排序再两两配对。问题在于每一步都强依赖上一行的结果，形成了一种串行依赖链条。

多边形边数一多，边表的排序代价会迅速放大。而且为了保证交点正确，通常要使用浮点数存储和比较，数值误差在几千条扫描线上累积起来，最终边缘会出现半像素的错位。我在实际项目里吃过这个亏，后来不得不在排序后做额外修正，代码复杂度直线上升。

扫描线算法适合的场景是：多边形数量少、单帧只做一次填充、对边界精度要求极高的软件渲染器。只要是逐帧动态填充，或者涉及大量并发计算，扫描线的维护成本就成了致命瓶颈。

1.2 种子填充算法：能用但不能规模化

种子填充是另一种常见方案，先找一个内部点，然后向四个方向扩散，一路填到边界为止。这个算法胜在实现极其简单，不需要任何几何解析，甚至不需要严格的多边形，任意闭合区域都适用。

但种子填充的问题也同样明显：它需要一个种子点，而你手上往往只有多边形顶点，得先自己算一个内部点，这就要做射线法或内点判定；其次，扩散过程用的是递归或显式栈，遇到凹多边形、复杂自交形状时，栈会变得很深，内存消耗不可控；第三，对于很大的填充区域，逐像素入栈出栈的性能非常差，虽然有些优化版会改用行填充加速，但本质上仍然是一块一块地扫描周围连通区域。

最要命的是，种子填充本质上串行且不可预测——每帧的填充路径都不一样，CPU缓存命中率糟糕，也没法做GPU实现。它适合交互式小工具，比如画图软件里的油漆桶，但不适合作为大规模渲染的核心路径。

1.3 边标志把问题拆成两个独立的子问题

边标志算法的核心贡献在于把“多边形到像素的解析过程”和“像素到颜色的填充过程”解耦。第一阶段只对每条边做光栅化，把与边界相交的像素点标记出来；第二阶段完全不关心多边形的顶点、边、凹凸性，只按行从左到右扫一遍，遇到标记翻转状态并填色。

这个解耦带来的直接收益是，第一阶段的每条边之间互相独立，可以扔到多线程或GPU上并行光栅化；第二阶段的每一行之间也没有依赖，可以按行分块处理。对比扫描线那种“一条扫描线必须等前一条扫描线更新完边表”的串行结构，优势是压倒性的。

另一个容易被忽视的点是数值稳定性。扫描线算法需要维护活性边表中交点的连续更新，任何一行的浮点误差都会传播到下一行；边标志算法则把每条边的交点在所在行内单独计算，行与行之间不存在误差传播。这一点在生产环境中非常重要，后面我会专门展开。

2. 边标志算法第一版：如何从零手写一个能跑的版本

在开始变体讨论之前，最好先把最基础、最朴素的版本吃透。我会直接用Python写一个能跑的实现，加上注释，把这个算法的骨架完整展示出来。之后所有变体都基于这个骨架修修补补。

2.1 数据结构和主流程

整个算法只依赖两个核心数据结构：一个和画布等大的标记数组，用来记录“这个像素是否是多边形边界与扫描线的交点”；另一个是当前扫描状态布尔值，在每行扫描时用来判断是否需要填充。

主流程分三步：

1. 初始化一个width * height的标记数组，所有值为false。
2. 遍历多边形的每一条边，在标记数组上对所有交点像素做“翻转”操作。
3. 逐行扫描标记数组，遇到true就翻转内部状态，状态为真时把当前像素写入帧缓冲。

第二步里有个容易踩的细节：为什么是“翻转”而不是“置为 true”。假设两条边恰好经过同一个像素，用“置为 true”的话，这个像素就只有一个标记；但实际在这里发生了两次边界跨越，按照奇偶规则状态应该不变。而“翻转”天然能处理这种情况，两个标记叠加后等于没标记。这个细节很重要，我在第三章会仔细讲。

2.2 光栅化边的两种方法

对每条非水平边做光栅化，本质上是求这条边在每一行扫描线上的 x 坐标。最常见的方法是 DDA（数字微分分析）和 Bresenham。

DDA 的思路是，既然知道了边的两个端点，就可以算出 x 相对于 y 的变化斜率dx/dy，然后从下端点开始，每增加一行 y，就让 x 累加一次斜率。实现非常直观，适合作为基础版本。

Bresenham 则把 DDA 中的浮点运算换成整数加法和比较，避免浮点误差累积。在边标志算法里，DDA 的浮点误差通常不会扩散到下一行，所以其实问题不大；但如果你处理的是几万条边的超大多边形，浮点斜率累加几千次后确实可能造成边缘像素偏移，这时候还是整数 Bresenham 更让人安心。

我在基础版本里用 DDA 实现，理由只有一个——清晰。后面讲到踩坑时会再给出 Bresenham 版本的建议。

2.3 一个可以直接运行的 Python 实现

class EdgeFlagFiller: def __init__(self, width, height): self.width = width self.height = height def fill(self, polygons): # 阶段一：初始化标记数组 flag = [[False] * self.width for _ in range(self.height)] # 阶段二：逐边打标 for poly in polygons: n = len(poly) for i in range(n): x0, y0 = poly[i] x1, y1 = poly[(i + 1) % n] self._mark_edge(flag, x0, y0, x1, y1) # 阶段三：逐行扫描填充 buffer = [[0] * self.width for _ in range(self.height)] for y in range(self.height): inside = False for x in range(self.width): if flag[y][x]: inside = not inside if inside: buffer[y][x] = 1 return buffer def _mark_edge(self, flag, x0, y0, x1, y1): # 水平边跳过 if y0 == y1: return # 保证从下往上遍历 if y0 > y1: x0, y0, x1, y1 = x1, y1, x0, y0 slope = (x1 - x0) / (y1 - y0) x = float(x0) # 下闭上开：只处理 [y0, y1) 的扫描线 for y in range(y0, y1): px = int(round(x)) if 0 <= px < self.width: flag[y][px] = not flag[y][px] x += slope

整个核心逻辑不到40行。_mark_edge中两个关键点，一是水平边直接跳过，二是遍历范围用了range(y0, y1)而不是range(y0, y1 + 1)。这两个细节决定了算法的正确性，第三章会深入解释。

2.4 验证这个基础版本

随便拿一个简单多边形测试，比如一个三角形[(10, 10), (90, 50), (10, 90)]，跑完后输出的 buffer 应该是中间被填满、边缘带锯齿的三角形状。

我第一次跑通这个版本时，第一反应是“这也太简单了”。扫描线算法光写活性边表和排序就花了一百多行，边标志算法三四十行就结束了，而且所有边界情况都有清晰的数学定义。但这种“简单”的表象下藏着不少坑，尤其当多边形变复杂之后，很多原本看不见的问题会浮出水面。

3. 顶点、水平边和奇偶翻转：边标志最容易翻车的三个边界 Case

基础版本能跑通简单多边形不意味着算法就安全了。顶点恰好落在扫描线上、多边形存在水平边、两条边共享同一交点，这三个场景是所有填充算法的统一噩梦，边标志算法也不例外。

3.1 水平边：千万别画上去

水平边是唯一一种在边标志算法中应该完全跳过的边。原因很直接：水平边本身不产生“扫描线交点的进入或离开”，它的渲染结果应该是被内部填充所覆盖。

如果手贱把水平边也标记进去，会发生什么？假设一条水平边从 x=10 到 x=50，你会在这行的 flag 数组里标上一整排的true。扫描时每遇到一个标记就翻转一次状态，如果这段水平边长度为奇数个像素，最终状态会被翻转奇数次，导致从此之后整个行内状态全部反掉，填充区域向一侧偏移，严重的会污染整行。

3.2 顶点处理的半开区间技巧

顶点问题是最复杂的一个边界场景。扫描线恰好穿过一个顶点时，两条相邻边都会在该行产生交点。如果两条边位于扫描线两侧，这个顶点对应一次正常的“进入/离开”；如果两条边位于扫描线同侧（也就是局部极值点），按照奇偶规则应该被计数两次或零次，但实现中我们必须精确定义规则。

边标志算法通行的做法是“下闭上开”：每条边只处理[ymin, ymax)的半开区间，即包含下端点、不包含上端点。这样每个顶点到底贡献几次，完全由它在两条边中充当的角色决定。

拿局部极值点举例：一个尖端向上的顶点，必然同时是左右两条边的最大 y 值，按照下闭上开规则，两条边都把这个顶点排除在外，于是该点处标记次数为 0，扫描线穿过时不会发生状态翻转，填充区域在极值点上方断开，图形正确。反过来，如果极值点朝下，两条边都把它当作下端点包含进来，标记次数为 2，翻转两次等于没有翻转，状态同样正确。

普通转折点则不同：一条边把它当上端点排除，另一条边把它当下端点包含，于是恰好产生一个标记，状态正确翻转一次。一个规则一次性处理了所有情况，这就是半开区间的价值。

3.3 两个标记重合：为什么“翻转”比“置位”更安全

基础版本里我用的是not flag[y][px]，而不是直接赋值True，这个选择背后有讲究。

想象一个宽度极窄的多边形，比如一个锐角长条，两条边在某行扫描线上落到同一个像素。如果使用“置位”版本，这个像素只会被标记为true一次；扫描到这一行时状态翻转一次，之后整行都会被认为在多边形内部，垃圾填充一路蔓延到行尾。

而“翻转”版本天然能处理这种重合：两条边各翻转一次，叠加后等于没有翻转，该像素内部的扫描状态保持不变，不会产生错误填充。这个细节在图纸上往往看不见，只有真正实现过的人才会意识到。我在实际代码里也遇到过类似的问题，当时用了置位版本，调试了整整一个晚上才定位到原因，后来改成翻转就再也没出过毛病。

3.4 共享边与多边形内部边界

还有一个很容易被忽略的场景：多个多边形共用一条边，比如两张相邻的地图瓦片，或者一个整体被拆成多个子多边形。基础版本里，共享边会被两条多边形各处理一次，这会导致什么后果？

在单多边形填充中，一条边只会被标记一次。但共享边同时属于两个多边形，两个多边形分别打标后，共享边像素被翻转两次，结果等于没有标记。填充时，共享边所在行不会发生状态翻转，两个多边形各自的内部区域都正确填充，共享边本身则恰好是两者之间的交界线，不会出现重叠或空洞，这其实已经算不错了。

更麻烦的情况是两个多边形重叠区域很小，共享边附近出现两对标记同时落在相邻像素，这时候奇偶规则会把它们错配成一对“进入-离开”，导致中缝被错误填充。遇到这种复杂拓扑，光靠基础版本的奇偶翻转已经不够，需要用到方向标志，下一章展开。

4. 三种边标志变体的演进：方向标志、并行化和反走样

基础版边标志算法能用，但工程实践会逼你做出各种改进。我实际使用中比较有价值的变体有三个：支持自交多边形的方向标志版、面向多核/GPU的并行化版、以及带抗锯齿效果的覆盖率版。这一章把它们的思路和取舍都讲透。

4.1 方向标志：统一处理自交与重叠区域

奇偶规则解决不了自交多边形。一个五角星或者任意自交图形，某条扫描线可能穿过多边形边界四次，奇偶规则会把它当成“进入-离开-进入-离开”，但几何直觉告诉我们中间那个交叉区域其实在多边形内部覆盖了两层，是否应该填充取决于你的定义。

方向标志版把每个标记从布尔值升级为带方向的整数：边从左到右跨越扫描线时标记为+1，从右到左跨越时标记为-1。扫描填充时不再用简单的奇偶翻转，而是累加一个环绕数，只有当环绕数非零时才填充像素。

# 对每条边的打标逻辑更改为 direction = 1 if x1 > x0 else -1 for y in range(y0, y1): px = int(round(x)) if 0 <= px < self.width: flag[y][px] += direction # flag 变成 int 矩阵 x += slope # 扫描填充逻辑 inside = 0 for x in range(self.width): inside += flag[y][x] if inside != 0: buffer[y][x] = 1

这个变体对重叠层数大于1的区域也能正确处理：环绕数2、3、4都是非零，按需求填充。开销是标记矩阵从1 bit变成至少一个int8，内存增加了8倍，但在现代硬件上通常可以接受。如果不想牺牲这么多内存，也可以用两个布尔矩阵分别记录正方向和负方向，扫描时按需加减，效果相同。

4.2 按边分块并行：扫描线做不到的优化

边标志算法第一阶段的可并行性是它的招牌优势。每条边的光栅化只依赖这条边的端点坐标和画布尺寸，与其他边完全无关，可以做完美的数据并行。

具体做法是把所有边分成若干组，每个线程处理一组，各自在局部标记矩阵上打标，全部完成后把局部矩阵合并；或者直接在共享的int8矩阵上用atomicAdd合并方向标志，省去合并步骤。第二阶段逐行扫描填充同样可以按行分块，不同行之间没有数据依赖，扔给 GPU 着色器时只需要一个简单的计算着色器就能完成。

对比扫描线算法的活性边表结构，它的每一条扫描线状态都依赖前一条线的更新结果，基本没法并行。我在一个项目里做过实测，仅仅把边标记阶段拆到 4 个线程，8000 条边的多边形填充性能就提升了接近3倍，继续增加线程时瓶颈转移到了内存带宽。这种扩展特性是边标志算法在现代渲染管线中重新被重视的根本原因。

4.3 覆盖率标记：在不牺牲太多性能的前提下抗锯齿

基础边标志和二值标记最大的视觉问题是锯齿。有没有可能既保留边标志的并行与简洁，又得到平滑边缘？可行方向之一是覆盖率标记。

覆盖率标记的核心思路是：标记阶段不再只记录“这个像素是否覆盖了边”，而是记录“这条边在这个像素内部覆盖的面积比例”，填充阶段根据覆盖率混合前景色和背景色。这个方案比分四次超采样快很多，因为每条边只需要做一次几何计算，而且覆盖率可以用增量方式估算，不需要逐样本测试。

具体实现上，可以在像素内部做 4x4 或者 8x8 的采样点阵列，用边的直线方程快速判断每个采样点落在哪一侧，统计落入多边形内部的采样点比例作为覆盖率。这样做代价是标记矩阵需要保存float覆盖率而不是int8，内存进一步增加，但换来的边缘质量提升是肉眼可见的。字体渲染引擎里有不少这种思路的成熟实践。

4.4 三个变体的横向对比

选择建议非常直接：开发周期紧、多边形简单，用基础版；要处理自交图形，立刻上方向标志版；有性能瓶颈，把并行化加上；追求边缘质量，就在方向标志版的基础上做覆盖率标记。四者不是互斥关系，工程实现里完全可以叠加。

5. 实测：同一张图，三种填充算法的耗时和坑

算法好不好，光看原理不够，还是得实际拉出来遛遛。我在自己的软件渲染器项目里做过一组对比测试，用一张中等复杂度的城市道路轮廓图，包含大约8000条多边形边，画布尺寸为 1920x1080，CPU 为某颗 8 核桌面处理器，单线程与多线程两个版本分别记录耗时。

5.1 测试集和记录方式

对比对象是扫描线算法、种子填充算法和基础/并行边标志算法。种子填充需要种子点，我用多边形质心或重心做了个内部点计算，然后调用现有实现。整个测试在 Debug 和 Release 两种配置下各跑三遍，取 Release 下的中位时间，避免编译器优化波动影响结论。

另外准备了一组小规模测试：一个只有几十条边的凹多边形，画布缩小到 512x512，目的是看看三种算法在小任务上的开销差异。

5.2 测试数据与结论

第一组数据里，边标志的并行优势体现得非常明显，8线程相比扫描线快了近8倍；第二组数据则暴露了边标志在小任务上的短板——需要初始化整个标记矩阵，这个固定成本在画布较小时不可忽略，反而比扫描线还慢一些。

种子填充在两组数据里都不占优，主要是因为它需要额外的内部点计算和递归栈操作，即使填充本身很快，前置开销也把它拖垮了。用极端一点的说法，种子填充更像一个“涂色工具”，而不是“批量几何填充引擎”。

5.3 我在实际实现中踩过的三个坑

第一个坑是浮点累计误差。基础版 DDA 在处理上万条边的大多边形时，斜率累加会让交点位置偏出去一两个像素，边缘出现明显的毛刺。解决办法是把交点计算改成定点数或者 Bresenham 整数算法，保证每条边的光栅化过程完全可控。

第二个坑是标记矩阵的内存布局。一个 1920x1080 的布尔标记矩阵占大约 2MB，看起来不多，但如果每一帧都新建并清零，再叠加方向标志版本里的int8内存占用，内存带宽很快就会成为瓶颈。我在并行版本里改成复用静态分配的标记矩阵，每帧只清空上一帧用到的行，性能立刻提升了20%左右。

第三个坑是相邻多边形共享边时的中缝问题。用方向标志版之后，共享边两侧的环绕数逻辑相通，但仍然会出现共享边被填充成一条虚线的视觉噪点。我的最终处理方式是，在填充阶段遇到标志像素时先用半透明颜色写入覆盖层，再根据左侧和右侧的环绕数决定是否顶替为不透明颜色。这个处理对地图渲染非常关键，否则瓦片接缝处永远有一条清晰的竖直裂缝。

6. 什么项目适合拥抱边标志，什么项目应该绕开

算法选型这件事，没有一个绝对正确的答案，但通过上面这些实践我形成了比较清晰的判断标准，也踩过不少错配的坑。这一章算是给前面所有内容的归拢，同时也是我自己的经验总结。

6.1 边标志算法的优势区间

边标志算法最强的场景是大量复杂多边形需要重复填充，或者需要并行加速。地图渲染、矢量图形转位图、GPU 上的动态区域着色，这些都是它的主场。配合方向标志后，哪怕多边形是自交的、有洞的、重叠的，实现逻辑依然比扫描线简单得多。

另一个容易被忽略的优势是代码的可维护性。边标志算法把填充拆成两阶段，每一阶段都可以独立测试、独立优化。我经常先单独验证边界标记阶段，把标记矩阵可视化输出，肉眼检查边界形状是否正确，再单独调试扫描填充阶段。这种调试体验在扫描线算法里几乎不可能复制。

如果你在写小型工具或者教学项目，基础版几十行代码即可完成，这本身就是巨大的工程优势。

6.2 不适合边标志的情况

边标志算法也绝对不是万能药。小画布小多边形场景，初始化标记矩阵的开销会占到总耗时的一大半，这时候扫描线反而更划算。另外如果边界需要精确到亚像素级别，或者要在填充过程中做大量渐变、贴图映射等逐像素计算，标志矩阵能提供的信息量是不够的，传统扫描线配合插值计算会更自然。

还有一类情况必须提醒：如果只需要填充一次，并且画布尺寸极大，边标志打标阶段会把整个边界区域都访问一遍，即使填充区域很小，也要支付整块画布的初始化成本。这种场景下暴力扫描线可能表现更好。

6.3 一点个人经验

这个系列走到第十二篇，我把多边形填充的主流路线都写了一遍。如果你只打算记住一个结论，我建议是：不要看到扫描线算法经典就想当然地在所有项目里用它，也不要因为边标志算法思路简单就小看它的上限。我见过有人在嵌入式环境用边标志做实时渲染，也见过有人在大型地图引擎里靠方向标志版稳定输出复杂行政区划轮廓。真正决定算法价值的，是对场景特点的理解和对边界情况的处理细节。

如果你现在打算手写一个多边形填充，我的建议是先搭基础版，用一组包含自交、水平边、极值点、共享边的测试多边形把正确性打磨到无懈可击，然后根据实际性能瓶颈决定要不要加方向标志、做并行化或者上覆盖率标记。从最简单能跑的版本起步，比一开始就追求满配要明智得多。