教程文档示例工程【免费下载链接】website-archiveArchive of the Coding Train website (first version)项目地址https://gitcode.com/gh_mirrors/we/website-archive点击查看免费下载本文基于 website-archive 仓库中「Coding in the Cabana」系列第 3 期页面 003-hilbert-curve.md 展开结合仓库内 P5 与 Processing 双版本源码完整剖析如何用一条纯位运算的迭代算法把一维序号精确映射到二维 Hilbert 曲线路径上并用 HSB 色相渐变逐帧动画化这条经典空间填充曲线space filling curve。读完本文你可以掌握 Hilbert 曲线的 uvwx 迭代求点算法、order与点数的指数关系以及可直接运行的 p5.js / Processing 完整实现。挑战背景与剧集信息该文档是「Coding in the Cabana」系列的第 3 集页面系列入口见 _challenges/coding-in-the-cabana/index.md正文写道Its the third episode of Coding in the Cabana! On this snowy day, I attempt to animate the path of the classic space filling curve known as the Hilbert Curve.即在一天的时间盒内尝试对经典空间填充曲线——Hilbert 曲线的路径进行动画化。文档 front matter 中记录的元信息如下字段值说明video_number3系列第 3 集date2020-02-08发布日期video_iddSK-MW-zuAc配套视频 IDweb_editorLPf9PLmpp5.js Web Editor 中的 sketch IDrepositorycoding-in-the-cabana/003_hilbert_curve对应本仓库的challenges/coding-in-the-cabana/003_hilbert_curve目录文档的 front matter 同时给出了两条重要的延伸阅读线索Hilbert 曲线的维基百科条目以及 Marcin Chwedczuk 提出的“绘制 Hilbert 曲线的迭代算法Iterative algorithm for drawing Hilbert curve”推荐视频则是 3Blue1Brown 的《Hilberts Curve: Is infinite math useful?》。下文将看到仓库源码实现的正是这条线索所指的迭代算法。什么是 Hilbert 曲线Hilbert 曲线是一条连续、不自交、恰好遍历正方形网格内每一个格子一次的二维空间填充曲线。它的实用价值在于给出了从一维序号i到二维坐标(x, y)的双射映射常被用于图像重排、缓存友好的数据遍历、空间索引如数据库空间填充曲线索引以及程序化图形生成。与递归分形式的画法不同本文代码采用的是迭代求点思路给定序号i直接算出它落在曲线上的格子坐标无需递归展开或回溯。这样setup()里可以用一个for循环一次性预计算出整条路径draw()只负责按序画线动画与几何解耦。仓库实现总览对应repository字段的实现目录为challenges/coding-in-the-cabana/003_hilbert_curve包含两套等价实现P5/sketch.jsp5.js 版本画布 512×512曲线阶数order 8P5/index.html加载 CDN 上的 p51.4.1与p5.sound再引入sketch.jsProcessing/Hilbert/Hilbert.pdeProcessing 版本画布 1024×1024曲线阶数order 9。两个版本结构完全一致setup()预计算整条路径的点数组draw()每帧增量画线并推进计数器核心几何全部收敛在一个hilbert(i)函数里。核心算法hilbert(i) 的 uvwx 迭代求点下面以 p5.js 版本为例见 sketch.js完整展示核心函数并补充注释function hilbert(i) { // 曲线起点i 的低 2 位对应的 2x2 基本形四个角点 // 构成 Hilbert 曲线的“基本块”逆时针走完 2x2 网格 const points [ new p5.Vector(0, 0), new p5.Vector(0, 1), new p5.Vector(1, 1), new p5.Vector(1, 0) ]; // 取 i 的最低 2 位确定点在基本块中的位置 let index i 3; let v points[index]; // 从低阶到高阶逐位构建每处理一次就把 i 逻辑右移 2 位 for (let j 1; j order; j) { i i 2; index i 3; let len pow(2, j); if (index 0) { // 情形 0转置沿对角线镜像坐标互换 let temp v.x; v.x v.y; v.y temp; } else if (index 1) { // 情形 1向下平移 len v.y len; } else if (index 2) { // 情形 2沿对角方向平移 (len, len) v.x len; v.y len; } else if (index 3) { // 情形 3绕中心旋转 180° 再转置最后整体平移 len let temp len - 1 - v.x; v.x len - 1 - v.y; v.y temp; v.x len; } } return v; }算法的工作方式可以逐层拆解基本块order 1Hilbert 曲线最小的自相似单元是一个 2×2 网格上的“U”形路径访问顺序恰为points数组中的四个点(0,0) → (0,1) → (1,1) → (1,0)。序号i的最低 2 位i 3决定落在哪个角点。逐位放大外层循环从j 1到order - 1。每一轮把i逻辑右移 2 位i 2取出的新 2 位编码index决定当前子块相对于更小尺度坐标系的几何变换——四种变换分别对应 Hilbert 曲线四种朝向index 0子块被转置transpose只需交换v.x与v.yindex 1子块方向不变整体下移lenindex 2子块方向不变整体沿对角平移(len, len)index 3子块被旋转 180° 并转置len - 1 - v完成翻转 len完成归位。 其中len 2^j是当前尺度块的边长。结果从最低有效位向最高有效位逐轮施加变换最终v就是序号i在N × NN 2^order网格中的整数格子坐标。整个过程只有按位与、逻辑右移和少量加减没有任何递归或查表时间与空间都是 O(order)。这正是文档 front matter 中延伸阅读所指向的 Marcin Chwedczuk 迭代算法用序号的二进制位逐段解码曲线的自相似变换序列。可以推断作者选择该算法而非分形递归正是为了让path[i] hilbert(i)这种“按序号随机取点”的 O(1) 直接寻址成为可能从而支撑后面的逐帧增量动画。setup()预计算整条路径sketch.js 的setup()将网格坐标换算为画布像素坐标const order 8; function setup() { createCanvas(512, 512); colorMode(HSB, 360, 255, 255); background(0); N int(pow(2, order)); // 网格边长 N 2^order 256 total N * N; // 路径总点数 total N^2 65536 let len width / N; // 每格像素边长 512 / 256 2 for (let i 0; i total; i) { path[i] hilbert(i); // 整数格子坐标 path[i].mult(len); // 放大为像素坐标 path[i].add(len / 2, len / 2); // 平移到格子中心 } }几个关键量之间的关系值得注意orderN 2^ordertotal N²说明5321,024适合大屏低延迟预览712816,3848P5 版默认25665,536512×512 画布每格 2px9Processing 版默认512262,1441024×1024 画布每格 2px点数按4^order增长order每加 1 内存与绘制量翻 4 倍这是该挑战里最主要的“难度旋钮”。add(len / 2, len / 2)把整数格子坐标平移到格子中心避免线端点与格线重合。draw()按序号增量画线 HSB 色相动画动画逻辑sketch.js非常直接let counter 0; function draw() { background(0); stroke(255); strokeWeight(1); noFill(); for (let i 1; i counter; i) { let h map(i, 0, path.length, 0, 360); stroke(h, 255, 255); // 色相沿路径从 0 扫到 360 line(path[i].x, path[i].y, path[i - 1].x, path[i - 1].y); } counter 50; // 每帧推进 50 个点 if (counter path.length) { counter 0; // 画完一整圈后重新开始形成循环 } }色相映射colorMode(HSB, 360, 255, 255)下map(i, 0, path.length, 0, 360)让色相沿着曲线序号从 0 线性扫到 360。由于 Hilbert 曲线在空间上是连续的视觉上就出现“颜色带沿着曲线蜿蜒填充整个画布”的效果——这是本期挑战标题中“animate the path”的直观呈现。增量速度counter 50意味着每帧新画 50 段线。以order 8的 65,536 个点计画满一整圈约需 1311 帧按 p5.js 默认 60 FPS 约 22 秒后counter归零循环重播。想加速或减速只需调整该步长。源码中还保留了一段被注释的调试代码把strokeWeight(4)的散点连同序号text(i, ...)打出来用于肉眼核对“序号 → 坐标”映射是否正确这可以作为验证自己改写算法时的自检手段。Processing 版本的差异Processing 版 Hilbert.pde 与 P5 版逐行对应仅有三处系统性差异order 9、size(1024, 1024)点数 262,144约为 P5 版的 4 倍因此完整动画循环耗时约为其 4 倍向量类型用PVector代替p5.Vectornew PVector(0, 1)等写法一一对应位运算部分i 3与i 2语义一致Java 的同为逻辑右移。这组双版本也印证了 front matter 中同时挂出 web editor sketch 与repository指针的用法同一算法在不同宿主环境下的平行实现便于对照。如何运行仓库为只读归档以下为本地运行方式P5 版用浏览器直接打开 challenges/coding-in-the-cabana/003_hilbert_curve/P5/index.html 即可index.html通过 CDN 加载 p51.4.1需要网络p5.sound 虽被引入但本 sketch 未使用音频。Processing 版在 Processing IDE 中打开 challenges/coding-in-the-cabana/003_hilbert_curve/Processing/Hilbert/Hilbert.pde 所在目录运行。调参建议修改order时要同时权衡点数4^order与每格像素width / 2^order。若希望动画节奏与原版一致可相应缩放counter的步长。延伸方向与社区贡献文档 front matter 的contributions字段收录了一批基于本期的社区扩展按主题归拢具体作品以文档列表为准其他语言移植C#、PygamePython、Haskell5 行函数式写法、R 包hilbeRt、VB.NET带 0→6 阶变形 GIF、以及“矩阵”思路的 p5.js 实现曲线扩展Peano 曲线、Gosper 曲线与龙形曲线L-system 画法、用 L-system 生成 SVG 的 Hilbert 曲线可视化玩法阶数插值order 之间的变形、从一阶向下一阶 zoom out 的动画、用 Hilbert 曲线做图像 dithering 与图像重排渲染、可编辑的空间填充曲线、以及让一辆小车沿 order 5 曲线行驶艺术变体Hilbert 花Hilberts Flower等。这些方向共同说明该算法的两个复用点hilbert(i)提供的 O(1) 序号寻址以及“曲线即遍历顺序”的空间连续性都可以作为图像重排、运动路径、数据遍历等场景的底座。小结本期挑战的价值在于用最少的代码量打通了 Hilbert 曲线“数学定义 → 可运行动画”的完整链路hilbert(i)用 4 种位运算变换完成 uvwx 迭代解码setup()以4^order个预计算点支撑随机寻址draw()则用 HSB 色相沿序号线性映射实现循环动画。仓库中的 P5 实现 与 Processing 实现 互为参照可直接复制运行也是继续调参order、步长、色相映射区间或移植到其他语言的良好起点。赞分享教程文档示例工程【免费下载链接】website-archiveArchive of the Coding Train website (first version)项目地址https://gitcode.com/gh_mirrors/we/website-archive点击查看免费下载相关推荐Coding in the Cabana 第 1 期使用 p5.js 与 Processing 实现 Maurer Rose 可视化Coding in the Cabana 第 1 期使用 p5.js 与 Processing 实现 Maurer Rose 可视化 导读 Maurer Ro教程文档示例工程Collatz 猜想可视化用 p5.js 与 Processing 绘制考拉兹序列树Coding in the Cabana 第 2 期Collatz 猜想可视化用 p5.js 与 Processing 绘制考拉兹序列树Coding in the Cabana 第 2 期 本文基于 Cod教程文档示例工程Coding in the Cabana 系列解读用 Processing 与 p5.js 可视化 5 个经典生成式算法Coding in the Cabana 系列解读用 Processing 与 p5.js 可视化 5 个经典生成式算法 Coding in the Caba教程文档示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考