31:Tc60,md`*"Do you mean the [Hilbert curve](https://en.wikipedia.org/wiki/Hilbert_curve)?"* Good guess, but no. I actually mean the H-curve (also known as the H-index), a Hamiltonian space-filling curve introduced by Rolf Niedermeier, Klaus Reinhardt and Peter Sanders in 1997 in *["Towards Optimal Locality in Mesh-Indexings"](http://www.akt.tu-berlin.de/fileadmin/fg34/publications-akt/fct97.pdf)* ([sciencedirect mirror](https://www.sciencedirect.com/science/article/pii/S0166218X00003267)). The unfortunately slightly confusing name comes from the shape it makes, resembling a lot of connected H's. (If you don't yet know what a space-filling curve is and feel a bit lost, 3blue1brown has [a beautiful video explaining the topic](https://www.youtube.com/watch?v=3s7h2MHQtxc) - do yourself a favor and check it out if you haven't seen it before! Also, being a [Hamiltonian](https://en.wikipedia.org/wiki/Hamiltonian_path) curve just means that it forms a closed loop - the classic Hilbert curve does not, for example) What makes the H-curve particularly interesting is that it has the best currently-known *locality property* of all space-filling curves. In simple terms: if you start anywhere on the curve and take ${tex`n`} steps, the absolute distance between the start and end points on the 2D grid is guaranteed to be less than ${tex`cn^{1/2}`}. The smaller the value of ${tex`c`} is for a curve, the closer you can expect to be (on average) to your starting point. The Hilbert curve has ${tex`c = \sqrt{6}`}. The H-curve has ${tex`c = 2`}, and this is conjectured to be optimal (caveat: I'm actually not entirely sure if this information is up-to-date, because the only papers I read about it are more than ten years old.). Whenever strong locality is the reason to resort to space-filling curves (which is almost every case where space-filling curves are used, as far as I know), one might expect the H-curve to be an ideal candidate. However, the only other direct mention I found of this curve was in *["A Note on Space-Filling Visualizations and Space-Filling Curves"](http://hint.fm/papers/158-wattenberg-final3.pdf)*, a paper from 2005 by Martin Wattenberg. So why hasn't it been used more since it was discovered? Well, I suspect the reason is that the construction scheme in the original paper is [rather cryptic](https://blindedcyclops.neocities.org/ObservableData/h-curve/h-curve%20construction.png). The authors also kindly provided code to generate these curves ([archive.org link](https://web.archive.org/web/20060926193901/http://www-fs.informatik.uni-tuebingen.de/%7Ereinhard/hcurve.html)), but... as these snippets of code illustrate, they arguably only confuse would-be implementers more: ![](https://blindedcyclops.neocities.org/ObservableData/h-curve/h-curve%20code.png) ![](https://blindedcyclops.neocities.org/ObservableData/h-curve/h-curve%20code%202.png) It's the thought that counts though - the authors are likely mathematicians first, programmers only by necessity (whereas I am the opposite and am grateful for their hard work on the theory side - for starters, I wouldn't know where to begin to prove the locality of this curve).`32:T6a3,function gridToHCurve(grid, x, y, subgridsize) { const gridsize = Math.sqrt(grid.length); const idx = x + y * gridsize; // The basic idea is this: first make a grid of H's // ┏━┓ ┏━┓ ┏━┓ ┏━┓ // ┃ ┗━┛ ┃ ┃ ┗━┛ ┃ // ┃ ┏━┓ ┃ ┃ ┏━┓ ┃ // ┗━┛ ┗━┛ ┗━┛ ┗━┛ // ┏━┓ ┏━┓ ┏━┓ ┏━┓ // ┃ ┗━┛ ┃ ┃ ┗━┛ ┃ // ┃ ┏━┓ ┃ ┃ ┏━┓ ┃ // ┗━┛ ┗━┛ ┗━┛ ┗━┛ // Then in the middle of the grid, connect the H's like so: // ┏━┓ ┏━┓ ┏━┓ ┏━┓ // ┃ ┗━┛ ┃ ┃ ┗━┛ ┃ // ┃ ┏━┓ ┃ ┃ ┏━┓ ┃ // ┗━┛ ┃ ┗━┛ ┃ ┗━┛ // ┏━┓ ┃ ┏━┓ ┃ ┏━┓ // ┃ ┗━┛ ┃ ┃ ┗━┛ ┃ // ┃ ┏━┓ ┃ ┃ ┏━┓ ┃ // ┗━┛ ┗━┛ ┗━┛ ┗━┛ // This function does only that last part, converting: // ┗━┛ ┗━┛ => ┃ ┗━┛ ┃ // ┏━┓ ┏━┓ => ┃ ┏━┓ ┃ // Or: // RT TL RT TL => BT TR LT TB // BR LB BR LB BT RB BL TB grid[idx] = BT; grid[idx+1] = TR; grid[idx+2] = LT; grid[idx+3] = TB; grid[idx+gridsize] = BT; grid[idx+gridsize+1] = RB; grid[idx+gridsize+2] = BL; grid[idx+gridsize+3] = TB; if (subgridsize > 4) { subgridsize /= 2; gridToHCurve(grid, x-subgridsize, y-subgridsize, subgridsize) gridToHCurve(grid, x+subgridsize, y-subgridsize, subgridsize) gridToHCurve(grid, x-subgridsize, y+subgridsize, subgridsize) gridToHCurve(grid, x+subgridsize, y+subgridsize, subgridsize) } return grid; }33:T5c0,function *canvasDrawing(grid, scale, steps = 1){ const step = scale * 5; const size = Math.sqrt(grid.length); const strokeCtx = DOM.context2d(size * step, size * step, 1); const gradientCtx = DOM.context2d(size * step, size * step, 1); const outCtx = DOM.context2d(size * step, size * step, 1); gradientCtx.fillStyle = "white"; gradientCtx.fillRect(0, 0, size, size); strokeCtx.lineWidth = Math.floor(scale * 2); strokeCtx.lineCap = "round" let x = 0, y = 0, px = 0, py = 0;; for(let i = 0, idx = 0; i < grid.length; i++) { gradientCtx.fillStyle = d3.interpolateSpectral(i / grid.length); gradientCtx.fillRect(x, y, step, step); strokeCtx.strokeStyle = d3.interpolateSpectral((grid.length - i) / grid.length); strokeCtx.beginPath(); strokeCtx.moveTo(px + step/2, py + step/2); strokeCtx.lineTo(x + step/2, y + step/2); strokeCtx.stroke(); px = x; py = y; const direction = grid[idx] & 0b1111; switch (direction) { case T: y -= step; idx -= size; break; case R: x += step; idx += 1; break case B: y += step; idx += size; break; case L: x -= step; idx -= 1; break; } if (i%steps === 0) { outCtx.drawImage(gradientCtx.canvas, 0, 0); outCtx.drawImage(strokeCtx.canvas, 0, 0); yield outCtx.canvas } } outCtx.drawImage(gradientCtx.canvas, 0, 0); outCtx.drawImage(strokeCtx.canvas, 0, 0); return outCtx.canvas; }34:[] 2f:{"title":"A simple algorithm to generate H-curves","cells":[{"id":0,"value":"Title = md`# A simple algorithm to generate H-curves`","pinned":false,"hidden":false,"mode":"ojs"},{"id":922,"value":"**Update 28-07-2023:** `oneearedrabbit` came up with L-system rules for generating this curve! https://kruzenshtern.org/25-h-curve.html ([archive.org mirror](https://web.archive.org/web/20230728215532/https://kruzenshtern.org/25-h-curve.html))\n\n**Update 17-06-2026:** I forgot to link this because I thought people would find it anyway since it's also a notebook on Observable, but Benjamin Schmidt reformulated the algorithm in a way that allows it to be implemented in webGL: [H-Curve in webgl](https://observablehq.com/@bmschmidt/webgl-h-curve).","pinned":false,"hidden":false,"mode":"md"},{"id":325,"value":"The_H_Curve_illustration = canvasDrawing(hcurve(5), 1, 32)","pinned":false,"hidden":false,"mode":"ojs"},{"id":323,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":916,"value":"TopDown = md`Since applying the tile-based recursion in the paper was rather difficult I tried to come up a simpler algorithm. After quite a bit of tinkering I figured one out. The basic idea is this: first make a grid of closed loops at the desired grid size:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":536,"value":"boxdrawing(makeLoops(2))","pinned":false,"hidden":false,"mode":"ojs"},{"id":544,"value":"md`Then for the four loops in the middle of the grid, connect them like so:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":599,"value":"{\n const grid = makeLoops(2);\n const idx = 6 + 7*16;\n grid[idx] = BT;\n grid[idx+1] = TR;\n grid[idx+2] = LT;\n grid[idx+3] = TB;\n grid[idx+16] = BT;\n grid[idx+17] = RB;\n grid[idx+18] = BL;\n grid[idx+19] = TB;\n return boxdrawing(grid);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":604,"value":"md`In case it's not entirely clear, all we really do is apply this change to the 4×2 region in the middle:\n\n

\n          ┗━┛ ┗━┛  => ┃ ┗━┛ ┃\n          ┏━┓ ┏━┓  => ┃ ┏━┓ ┃\n

\n\nThen we split the grid into four parts along that middle, and for each of those parts we recursively repeat this process. We recurse until the parts are four by four tiles (the size of one H), at which point the whole grid is connected.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":898,"value":"{\n const grid = makeLoops(2);\n const w = 16;\n const indices = [\n 6 + 7*w, // first split\n 2 + 3*w, 10 + 3*w, 2 + 11*w, 10 + 11*w, ];\n for (const idx of indices) {\n grid[idx] = BT;\n grid[idx+1] = TR;\n grid[idx+2] = LT;\n grid[idx+3] = TB;\n grid[idx+16] = BT;\n grid[idx+17] = RB;\n grid[idx+18] = BL;\n grid[idx+19] = TB;\n }\n return boxdrawing(grid);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":540,"value":"boxdrawing(hcurve(2))","pinned":false,"hidden":false,"mode":"ojs"},{"id":664,"value":"md`(note: ~~for now my implementation only works for rectangular grids with sides that are a power of two and dividable by four, but approximations for abitrary grid sizes should be possible with minor modifications - I might write a follow-up notebook on that~~ edit: done! [*Arbitrary Hamiltonian Curves*](https://observablehq.com/@jobleonard/arbitrary-hamiltonian-curves?collection=@jobleonard/space-filling-curves))`","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"Implementation = md`## Implementing the H-curve\n\nLet's first come up with a way to respresent curves in general. We basically need a way to represent a grid. An array will do just fine. Then we need a way for each point on the grid to say where the curve enters (top, right, bottom, or left) and where it leaves (same, but note that a curve cannot go back where it came from). Due to a [bad upbringing regarding my first programming experiences](https://www.ticalc.org/archives/files/fileinfo/328/32816.html) I'm very biased to use unnecessarily low-level constructs like bitflags, so I'm afraid that's what I did here.. hope you don't hate bit-twiddling!\n\nBasically, we'll use a number to store the direction. Each bit in the number is used to represent a direction - so we will need eight bits in total: four for each direction, times two for in and out.\n\nFirst, the bit flags for directions:\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":28,"value":"T = 1 // 0b0001","pinned":true,"hidden":false,"mode":"ojs"},{"id":31,"value":"R = 2 // 0b0010","pinned":true,"hidden":false,"mode":"ojs"},{"id":36,"value":"B = 4 // 0b0100","pinned":true,"hidden":false,"mode":"ojs"},{"id":39,"value":"L = 8 // 0b1000","pinned":true,"hidden":false,"mode":"ojs"},{"id":65,"value":"md`Now to indicate where the curve enters and where it leaves:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"// Store \"in\" in the upper four bits, and \"out\" in the bottom four\nTR = T * 16 + R","pinned":true,"hidden":false,"mode":"ojs"},{"id":48,"value":"TB = T * 16 + B","pinned":true,"hidden":false,"mode":"ojs"},{"id":50,"value":"// Note that curves cannot leave in the direction where they entered,\n// so can skip TT. We'll have 3 * 4 = 12 combinations in total.\nTL = T * 16 + L","pinned":true,"hidden":false,"mode":"ojs"},{"id":54,"value":"RB = R * 16 + B // you get the idea (if you're comfy with thinking in bits)","pinned":true,"hidden":false,"mode":"ojs"},{"id":57,"value":"RL = R * 16 + L","pinned":false,"hidden":false,"mode":"ojs"},{"id":59,"value":"RT = R * 16 + T","pinned":false,"hidden":false,"mode":"ojs"},{"id":69,"value":"BL = B * 16 + L","pinned":false,"hidden":false,"mode":"ojs"},{"id":71,"value":"BT = B * 16 + T","pinned":false,"hidden":false,"mode":"ojs"},{"id":80,"value":"BR = B * 16 + R","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"LT = L * 16 + T","pinned":false,"hidden":false,"mode":"ojs"},{"id":85,"value":"LR = L * 16 + R","pinned":false,"hidden":false,"mode":"ojs"},{"id":88,"value":"LB = L * 16 + B","pinned":false,"hidden":false,"mode":"ojs"},{"id":331,"value":"md`Now we can use that to quickly make an array that represents a grid of H's:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":105,"value":"makeHGrid = {\n // Note: the curve walks clockwise along the H-shape\n // ┏━┓ ┏━┓ BR LB BR LB\n // ┃ ┗━┛ ┃ BT TR LT TB\n // ┃ ┏━┓ ┃ BT RB BL TB\n // ┗━┛ ┗━┛ RT TL RT TL\n const lookup = [\n BR, LB, BR, LB,\n BT, TR, LT, TB,\n BT, RB, BL, TB,\n RT, TL, RT, TL,\n ];\n\n return function makeHGrid(k) {\n const size = 4 * 2 ** k;\n const grid = [];\n for(let y = 0; y < size; y++) {\n for (let x = 0; x < size; x++) {\n grid.push(lookup[(y%4)*4 + (x%4)]);\n }\n }\n return grid;\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":706,"value":"makeHGrid(2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":767,"value":"makeLoops = {\n // Note: the curve walks clockwise along the loop\n // ┏━┓ BR LB\n // ┗━┛ RT TL\n const lookup = [\n BR, LB, \n RT, TL,\n ];\n\n return function makeHGrid(k) {\n const size = 4 * 2 ** k;\n const grid = [];\n for(let y = 0; y < size; y++) {\n for (let x = 0; x < size; x++) {\n grid.push(lookup[(y%2)*2 + (x%2)]);\n }\n }\n return grid;\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":343,"value":"md`An array of raw numbers representing directions isn't exactly easy to read - especially since it's a one-dimensional array representing a 2D grid. So let's make a function to test if the output is as expected, using [box-drawing characters](https://en.wikipedia.org/wiki/Box-drawing_character) and [some utility functions I made for formatting them](https://observablehq.com/@jobleonard/unicode-box-drawing-formatter?ui=classic):`","pinned":false,"hidden":false,"mode":"ojs"},{"id":130,"value":"boxdrawing = {\n // Look up table to create ASCII drawings\n const LUT = {\n [TR]: \"┗━\",\n [TB]: \"┃ \",\n [TL]: \"┛ \",\n [RB]: \"┏━\",\n [RL]: \"━━\",\n [RT]: \"┗━\",\n [BL]: \"┓ \",\n [BT]: \"┃ \",\n [BR]: \"┏━\",\n [LT]: \"┛ \",\n [LR]: \"━━\",\n [LB]: \"┓ \"\n };\n return function boxdrawing(grid, returnRawString) {\n const size = Math.sqrt(grid.length);\n let output = \"\";\n for (let i = 0; i < grid.length; i++) {\n if (i % size === 0) output += \"\\n \";\n output += LUT[grid[i]];\n }\n return returnRawString ? output : box`${output}`;\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":141,"value":"boxdrawing(makeHGrid(2))","pinned":true,"hidden":false,"mode":"ojs"},{"id":349,"value":"md`Looking good! Now to turn this grid into an H-curve with the recursive scheme we described above:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":166,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":176,"value":"function hcurve(k) {\n const size = 4 * 2 ** k;\n return gridToHCurve(makeHGrid(k), size / 2 - 2, size / 2 - 1, size / 2)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":179,"value":"boxdrawing(hcurve(1))","pinned":true,"hidden":false,"mode":"ojs"},{"id":633,"value":"boxdrawing(hcurve(2))","pinned":true,"hidden":false,"mode":"ojs"},{"id":635,"value":"boxdrawing(hcurve(3))","pinned":true,"hidden":false,"mode":"ojs"},{"id":353,"value":"md`Ok, that works as expected. However, I don't know about you, but these box-drawing characters still aren't the most easily readable curve. It might be nicer to use a \\`canvas\\` to draw the grid on, and use some colors too to show a gradient from start to finish, to give us a sense of the distance on the curve between pixels:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":208,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":553,"value":"canvasDrawing(hcurve(5), 1, 256)","pinned":true,"hidden":false,"mode":"ojs"},{"id":556,"value":"md`Much better!\n\nNow, we might want to actually use the H-curve in other contexts. Space-filling curves are commonly used to project data between 1D and 2D representations. So we need to easily be able convert between the 2D-grid and a 1D line. This is often done by making an array that represents how indexes in one array are projected into the other:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":559,"value":"function gridToIndices(grid) {\n const size = Math.sqrt(grid.length);\n const gridToLine = [];\n const lineToGrid = [];\n // initiate a numerical array without holes.\n for(let i = 0; i < grid.length; i++) {\n gridToLine.push(0);\n lineToGrid.push(0);\n }\n // Now we basicaly do the same as in the canvasDrawing function above,\n // but instead of drawing to a context we save the indices\n let x = 0, y = 0\n for(let i = 0, idx = 0; i < grid.length; i++) {\n gridToLine[idx] = i;\n lineToGrid[i] = idx;\n const direction = grid[idx] & 0b1111;\n switch (direction) {\n case T:\n idx -= size; break;\n case R:\n idx++; break\n case B:\n idx += size; break;\n case L:\n idx--; break;\n }\n }\n \n return {\n gridToLine,\n lineToGrid,\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":583,"value":"function hcurveIndices(k) {\n return gridToIndices(hcurve(k));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":566,"value":"gridToIndices(hcurve(2))","pinned":false,"hidden":false,"mode":"ojs"},{"id":647,"value":"md`This is where I'd typicaly say \"to use this just do \\`import {hcurveIndices} from \"@jobleonard/...\"\\`, but I just tested it and I actually can't even do that myself - weird CORS errors. Sorry. Hopefully I'll figure out what's wrong and manage to fix it later.\n\nFor now, if you do want to use this you'll have to manually inline the relevant code.\n\nAnyway, many thanks to [\\`@mootari\\`](https://observablehq.com/@mootari) for inspiring me to get off my ass and implement this - the algorithm had been bouncing around in my head for many months already.\n\nThanks for reading, hope you found this notebook interesting!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":372,"value":"d3 = require('d3-scale-chromatic', 'd3-color')","pinned":true,"hidden":false,"mode":"ojs"},{"id":811,"value":"import {\n initBoxFont,\n boxFonts,\n box\n} from \"@jobleonard/unicode-box-drawing-formatter\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":913,"value":"boxFonts","pinned":true,"hidden":false,"mode":"ojs"},{"id":813,"value":"initBoxFont()","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}