希尔伯特曲线：一维线上的二维世界

1891 年，德国数学家大卫·希尔伯特（David Hilbert）画出了一条不寻常的曲线：它蜿蜒、分岔、层层盘旋，最终却宣称自己能"填满"一整块正方形区域。这就是希尔伯特曲线——第一条被严格构造出来的空间填充曲线（Space-filling Curve）。

一条一维的线，怎么装得下一个二维的平面？希尔伯特的答案是：让曲线"无限折叠"。

最直观的构造方式是从一条简单的折线开始，我们称之为第 1 阶：一条"Π"形的折线恰好穿过 2×2 网格的全部 4 个格点。要得到第 2 阶，就把 4 个第 1 阶副本按不同朝向放进 4×4 网格，再用 3 条短线把相邻副本首尾相连——于是曲线一次扫过 16 个格点。每升高一阶，网格边长翻倍：第 n 阶曲线会穿过 2ⁿ×2ⁿ 的全部格点。

在本应用中，拖动文章顶部滑杆从第 1 阶到第 6 阶，你看到的就是这个递归过程。第 6 阶已有 4096 个顶点，曲线在正方形里密集穿行，仿佛要填满整个平面——而它始终只是一条不断头的折线。

希尔伯特曲线有两个迷人的数学性质。其一，它处处连续却无处可微：曲线从不间断，但处处拐弯，没有任何一点有切线方向，像一条"圆滑不起来"的折线。其二，当阶数趋向无穷时，曲线上每一点都在平面里任意稠密——平面上任一点都能被曲线上某点无限逼近，这就是"填满"的真正含义。

更实用的是它的"局部性"：一维序列里相邻的两个序号，对应的两个格点在平面里也总是紧挨着。换句话说，曲线把平面上的"近邻"关系，翻译成了一维的"相邻"关系。

这个性质让希尔伯特曲线成了天然的"空间索引"。把经纬度按曲线序号排序，地图上彼此靠近的地点就会在数据库里相邻存储，查询"附近"的数据只需在连续一段序号里扫描。类似的思路还出现在图像压缩（按曲线顺序扫描像素，让相近的像素一起处理）、电路板布线（让连线尽可能短）和相机抖动渲染（Bayer 抖动）中。

构造希尔伯特曲线的算法优雅而简洁。代码里用到了"位运算 + 旋转"的经典技巧 d2xy：把序号 d 写成四进制，从最高位到最低位逐级判断当前落在哪个象限，再对局部坐标做一次 90 度旋转或镜像翻转（函数 rot），累加每一级的偏移量。整个算法只要十几行，却能在 O(n) 时间内解出任意阶曲线上每个格点的精确位置。

从 1891 年的黑板到今天地图 App 的定位服务，希尔伯特曲线跨越了纯数学与应用工程。它提醒我们：一维和二维之间，并没有想象的那么遥远——有时候，只需把线折得足够密。

现在，拖动文章顶部的滑杆，观察第 1 阶到第 6 阶曲线的生长：注意每一阶都由上一阶的四个副本拼接而成，以及曲线如何一步步"侵占"整个正方形。