吉尔伯特曲线：让一串数字填满整张图

混淆的第一步不是搬像素，而是决定按什么顺序访问像素。这一篇讲清吉尔伯特曲线如何不重不漏地走遍任意宽高的矩形，以及这条顺序为什么决定了打乱后的画面质感。

问题的起点：二维图像要怎么变成一维队列

把一张图画进画布，得到的是一个二维像素阵列：宽 W、高 H 的图像一共 N = W × H 个像素。混淆要做的事情很轻巧，就是把整条像素序列整体挪一段距离；而要让「整体挪动」有意义，得先把二维阵列压成一条有先后顺序的一维队列。

压平听起来无关紧要，实际是算法里唯一有设计空间的地方。最省事的压法是按行扫描：队列里第 i 个元素对应第 ⌊i / W⌋ 行、第 i mod W 列。它同样是双射，也能原样还原，只是把「空间上相邻」和「队列里相邻」绑错了方向。

按行序循环移位 k 位，像素在垂直方向被整体挪动约 k / W 行。以 1920×1080 为例，k = 1 281 555，相当于画面沿垂直方向卷动六百多行，轮廓与色块保持不变，只是换了位置。

要真正打散画面，需要一条在二维平面里到处游走的访问顺序：局部有序，全局上却不断改变方向。这正是空间填充曲线（space-filling curve）要解决的问题，曲线可视化可以把任意宽高的遍历直接画出来。

递归思想：从 2×2 的四种走法讲起

吉尔伯特曲线（Gilbert curve）是希尔伯特曲线在任意宽高矩形上的推广。可以先只看 2×2 的四个格子：一条 U 形路径依次走过 (0,0)、(1,0)、(1,1)、(0,1)，四步走完四格，每一步都落在共用一条边的相邻格上，不重复也不遗漏。

把这条 U 形路径旋转 90 度，就得到入口和出口朝向不同的四种走法。四种朝向是递归能成立的关键：一段曲线有两个端口，入口和出口各落在某条边上，旋转后端口位置随之改变，于是任何一段曲线都能被摆到需要的位置和邻居对接。

2×2 只是起点：更大的网格靠把每个格子换成一个更小的同构块递归得到，4×4 就是每个格子各装进一个 2×2 小块的结果。

希尔伯特曲线的四等分递归

希尔伯特曲线的经典构造是四等分：把正方形切成四个象限，每个象限放一段缩小一半的同型曲线，四段首尾相接，整条路径就填满原来的正方形。

难点出在「首尾相接」上。一段曲线的入口和出口是固定的两个端口，如果四个象限都用同一种朝向，上一段的出口与下一段的入口很可能不相邻，接起来就需要斜向跳线，那已不是沿格子边行走的路径；更糟的是接线穿过已访问的格子，导致曲线自交。

所以递归时必须给子块指定朝向：需要与邻居相连的子块要旋转，有时还要镜像，让开口对准连接边。旋转不是为了让图形好看，而是为了让出口与入口恰好落在共用边两侧的相邻格上。判断标准只有一条：连接之后每一步都落在相邻格上，且所有格子恰好各访问一次。本站把朝向编码成起点与两个方向向量，递归时传入旋转后的向量；置换流程与伪代码里有完整写法。

为什么需要「广义」版本

经典希尔伯特曲线只适用于 2 的幂次边长正方形，而真实图片是 1920×1080、640×480 这类矩形。广义吉尔伯特曲线保留「递归切分、处处相邻、不重不漏」的性质，把切分规则放宽到任意宽高。

原算法的入口先比较宽高：width >= height 时把主方向设为水平，否则设为垂直。主方向上的长度记为 w，另一个方向记为 h，切分分两种情况。

• 长方形情形：如果 2w > 3h，图形明显偏长，只把主方向对半切开，递归处理前后两段。
• 常规情形：否则按「先上一步、再走一条长横线、再下一步」拆成三段递归，这是四等分结构的一般化写法。

递归到极小规模时会出现退化情形。h = 1 时只剩一行，直接把这一行的 w 个格子沿主方向取完；w = 1 时只剩一列，沿垂直方向取完 h 个格子。这两个分支同时是递归的终止条件：切分一次后子块尺寸一定变小，递归深度有限，不会无限展开。整个过程只做整数除法与判断，生成曲线是严格的 O(N)。切分时若一半长度是奇数且原长大于 2，实现会把它加上一步，让切分点落在偶数上。

图示：4×4 与 8×8 的遍历顺序

两张图放在一起看，递归结构会自己显形：4×4 的曲线是四个 2×2 小 U 形拼出来的大 U 形，8×8 再把每个小块换成一个 4×4，走向也不容易用眼睛跟踪了。

图中的红点是沿曲线等间隔取得的采样点：4×4 每 4 格取一个，8×8 每 8 格取一个。它们不是特殊像素，也不参与算法，只把一维下标的落点标出来。需要留意的是每张图里的访问序号都不重复：曲线没有跳过任何格子，也没有在任何格子上停留两次。

双射是可逆的前提

整条曲线必须是双射：每个格子恰好被访问一次。这等价于曲线序是一张一一对应表——第 i 步落在哪个格子、某个格子是第几步被访问，两个方向都能唯一确定。有了一一对应，位移之后的像素搬运才能被精确反向执行。

如果曲线自交或者漏格，后果不是画质差一点，而是彻底不可逆。自交意味着同一格被访问两次，曲线序里会有两个下标指向同一个像素位置，其中一个在搬运时覆盖另一个；漏格则意味着某些位置的像素从来没被搬动过，解混淆时无从知道它应该来自哪里。验证办法很简单：准备一个长度为 N 的标记数组，沿曲线走一遍，每访问一格就加一，走完之后所有计数都必须正好是 1。完整推导见可逆性与误差分析。

局部性：一维相邻的索引在二维上也相邻

曲线序有一个可以直接检验的性质：序列里前后相邻的两个下标，对应的两个格子一定共用一条边，不存在斜向跳跃。于是「沿曲线走 k 步」在画面上是一段连续而不断拐弯的路径，而不是一次无从预期的瞬移。

好的一面是相关性被打散得比较均匀：按行序位移会把整幅画面上下卷动，曲线位移则让每个像素沿曲线向前走 k 步，落点分散在画面各个角落，原本挨在一起的像素对几乎都被拆开，靠统计相邻像素关系来重建图像的思路会明显变难。

另一面是画面会出现沿曲线延展的条纹感：k 接近 0.618N，像素走过的距离很长，一段连续的源区域被拉成细长的曲线带铺在整幅图上。这种质感与曲线形状有关：1920×1080 与 1080×1920 的 N 相同，k 也相同，混淆结果却完全不同。

这顺带解释了混淆后的 JPEG 为什么往往更大：相邻像素的相关性被破坏，JPEG 的预测与熵编码效率下降。输出格式与画质里有更细的对照。

曲线序在代码里就是 order[i] = y * width + x

曲线是数学描述，落到代码里需要一个数据结构。最直接的做法是存一份下标序列：order 是长度为 N 的整型数组，order[i] 表示曲线第 i 步访问的像素在画布上的线性下标，由 y * width + x 算出。

const order = new Uint32Array(N);
for (let i = 0; i < N; i++) {
  const [x, y] = curve[i];
  order[i] = y * width + x;      // 二维坐标压成线性下标
}
// 混淆：把曲线第 i 步的像素写到第 (i + k) mod N 步的位置
out[order[(i + k) % N]] = in[order[i]];

用线性下标代替 [x, y] 数组，省掉的是每个像素一个数组对象的开销：一份 Uint32Array 占 4N 字节，200 万像素约 8 MB。复杂度与性能里给出了完整的内存账。

局限：曲线不是唯一选择

空间填充曲线不止一种。希尔伯特与吉尔伯特之外还有皮亚诺曲线、摩尔曲线、Z 序等，它们都能不重不漏地遍历网格，但访问顺序不同，混淆后的质感也不同：Z 序的局部性更弱，容易留下规则的块状条带，九等分的皮亚诺曲线纹理更细碎。随机置换同样可行，代价是要额外保存随机种子。

本站严格沿用原方案的曲线。原因很实际：只有曲线、位移量与遍历方向三者都与原工具一致，混淆与解混淆的结果才能逐字节对上，跨工具的图片才能互相解开。任何一次「把曲线改得更好」的尝试，都会让已经混淆过的老图片再也还原不回来。

想确认某个尺寸下的遍历是否真的不重不漏，把宽高填进曲线可视化，再拿生成的点数与 N 对一遍。