1. 简介
Marching Squares 是上世纪80年代提出的一种计算机图形学算法，用于等高线（contour）绘制。它可以用于绘制：
- 地形图中的海拔等高线
- 热力图中的温度等值线
- 压力场图中的压力等高线
本教程中，我们将学习 Marching Squares 是如何从图像的采样点网格中提取出轮廓线的。
2. 等高线与水平曲线
2.1. 数学定义
我们经常绘制一元函数如 f(x) = sin x 或隐函数如 x² + y² = 1 的图像。但对于二元函数 z = f(x, y)，绘制其图像就复杂得多。
为了简化，我们可以通过水平截面来观察这个三维曲面。具体来说，就是将曲面与水平面 z = c 相交，得到的交线称为等高线（contour curve）。这些曲线投影到 xy 平面上，就形成了该函数的水平曲线（level curve）。
数学上，函数 f(x, y) 在高度 c 处的水平曲线定义为：
Level curve at height c = { (x, y) ∈ R² | f(x, y) = c }
2.2. 示例
以函数 f(x, y) = 4 - x² - y² 为例：
- 当
c < 4时，水平曲线是圆：x² + y² = 4 - c，圆心在原点，半径为√(4 - c) - 当
c = 4时，曲线退化为一个点(0, 0)
| c | 水平曲线方程 |
|---|---|
| -21 | x² + y² = 25 |
| -12 | x² + y² = 16 |
| -5 | x² + y² = 9 |
| 0 | x² + y² = 4 |
| 3 | x² + y² = 1 |
| 4 | x = 0, y = 0 |
这些曲线共同构成了函数的“地形图”：
如果把这些等高线叠加起来，就能看到完整的曲面图 —— 一个倒扣的抛物面（paraboloid）：
3. 算法核心概念
以下图的云朵为例，我们希望提取出它的轮廓：
假设图像是一个 100×100 的矩阵 A，每个像素值 a_ij 表示亮度，范围是 0~255，其中 0 表示黑色，255 表示白色。
3.1. 图像采样
将图像划分为 4×4=16 个 5×5 的子网格。每个子网格包含 25 个采样点：
然后，我们根据一个等值线阈值（iso-value）σ 来判断每个点是“内部”还是“外部”：
ON(1)：像素值小于 σOFF(0)：像素值大于等于 σ
例如，若 σ = 200，则得到如下二值化网格：
3.2. 子网格配置（Configuration）
每个 5×5 子网格的四个角点（左上、右上、右下、左下）按顺时针顺序组成一个二进制码。例如，若角点值是 (0,1,1,0)，则二进制码为 (0110)_2 = 6，这就是该子网格的配置（configuration）。
例如：
对应配置为 6，其轮廓线形状如下图所示：
3.3. 等高线查找表（Contour Lookup Table）
一个正方形有 4 条边，每条边是否与等高线相交，有 2 种可能，因此共有 2⁴ = 16 种配置。我们为这 16 种配置建立查找表：
例如配置 7 = (0111)_2，表示左上角为 0，其余为 1。此时等高线应穿过该正方形的顶部和左侧边：
对应的轮廓线近似如下：
4. 算法实现
Marching Squares 的核心步骤如下：
- 采样网格，生成二值矩阵
F - 遍历每个子网格，查表生成等高线段
伪代码
algorithm MarchingSquares(G, m, n, σ, stepX, stepY):
F, coord, p, q <- SampleGrid(G, m, n, σ, stepX, stepY)
γ <- March(F, coord, p, q)
return γ
4.1. 采样网格（SampleGrid）
algorithm SampleGrid(G, m, n, σ, stepX, stepY):
p <- m / stepX
q <- n / stepY
F <- zero matrix of size p x q
coord <- zero matrix of size p x q
for i <- 0 to p - 1:
for j <- 0 to q - 1:
if G[i * stepY, j * stepX] > σ:
F[i, j] <- 0
else:
F[i, j] <- 1
coord[i, j] <- (x = j * stepX, y = i * stepY)
return F, coord, p, q
4.2. 遍历网格（March）
algorithm March(F, Coord, p, q):
γ <- an empty set
for i <- 0 to p - 2:
for j <- 0 to q - 2:
a <- Coord[i, j]
b <- Coord[i, j + 1]
c <- Coord[i + 1, j + 1]
d <- Coord[i + 1, j]
k <- 8 * F[i, j] + 4 * F[i, j + 1] + 2 * F[i + 1, j + 1] + F[i + 1, j]
north <- (a.x + b.x / 2, a.y)
east <- (b.x, (b.y + c.y) / 2)
south <- ((d.x + c.x) / 2, d.y)
west <- (a.x, (a.y + d.y) / 2)
S <- LUT(k, north, east, south, west)
γ <- γ + S
return γ
示例输出
以下是一张瑞士阿尔卑斯山勃朗峰地区的地形图，使用 Marching Squares 算法提取出的等高线效果如下：
5. 总结 ✅
Marching Squares 是一个经典的图形学算法，它的核心思想是：
- 局部构建：每条等高线可以在每个子网格中独立构建，不需要依赖其他网格
- 查表法：通过预定义的查找表快速获取每个子网格中等高线的形状
✅ 优点：
- 实现简单
- 效率高
- 适用于多种场景（地形图、热力图、压力图等）
❌ 缺点：
- 只能生成 2D 等高线
- 无法处理复杂的拓扑结构（如孔洞）
如果你在图像处理、地形渲染、可视化等领域工作，Marching Squares 是一个非常值得掌握的基础算法。