3e:null 3f:["$","title",null,{"children":"Arbitrary Hamiltonian Curves | Job van der Zwan | Observable"}] 45:T8da,md`# Arbitrary Hamiltonian Curves *(As far as I understand these are* ***not*** *space-filling curves, because maths, although I don't understand the maths behind that either. Since I'm only interested in discrete finite grids anyway, it doesn't really affect me personally, but I want to avoid spreading misinformation)* Given a width and height, we can create an arbitrary somewhat-[H-like](https://observablehq.com/@jobleonard/a-simple-algorithm-to-generate-h-curves?collection=@jobleonard/space-filling-curves) closed curve with a simple recursive function and a convenience class for creating paths on a grid. It follows the same basic logic as [the top-down algorithm for generating H-curves](https://observablehq.com/@jobleonard/a-simple-algorithm-to-generate-h-curves?collection=@jobleonard/space-filling-curves#TopDown). That algorithm works for squares that are powers of two. The key insights needed to extend it to arbitrary dimensions are the following: 1. the top-down algorithm works by dividing an area into four corners 2. it only requires that the four subdivisions will (eventually) form a closed loop themselves, and that it can safely use the corners of those loops to connect them into one big loop (meaning that doing so won't break up the loops of the four subdivisions). 3. if the width is equal or more than two times the height, we can also safely split the area in half along the middle instead of in four quarts, and connect the left and right half at the corner. This would still result in a closed loop. Same with shapes where the height is more than twice the width (but split along the other axis). Doing so will ensure that elongated shapes will divide into shapes with more equal proportions. 4. if we include the refinement of the previous step to subdivide a grid into smaller connected loops, and in the case of odd-length grids round the position where we split, we should always eventually end up with either a 2×2, 3×2, 2×3 or 3×3 grid (proof left as exercise for the reader - just draw it out on paper with a few examples and you'll see why it makes sense). 5. therefore, if we have a 3×3 "fallback" loop (the 2×2, 3×2, 2×3 are kind of self-evident), then we can always create a closed (i.e. Hamiltonian) curve:`46:T15de,lutH = { const {T, TR, R, RB, B, BL, L, LT} = directions; const lut = [[], [], [], [], [], [], [], [], []]; // ┏━┓ // ┗━┛ lut[2][2] = [ R, B, T, L ]; // ┏━┓ // ┃ ┃ // ┗━┛ lut[2][3] = [ R, B, T, B, T, L ]; // ┏━━━┓ // ┗━━━┛ lut[3][2] = [ R, R, B, T, L, L, ]; lut[3][3] = [ R, R, B, T, RB, L, T, L, L, ]; // Note: not bothering with rotations right now // ┏━┓ ┏━┓ R B R B // ┃ ┗━┛ ┃ T R T B // ┗━━━━━┛ T L L L lut[4][3] = [ R, B, R, B, T, R, T, B, T, L, L, L, ]; // ┏━━━┓ R R B // ┗━┓ ┃ T L B // ┏━┛ ┃ R T B // ┗━━━┛ T L L lut[3][4] = [ R, R, B, T, L, B, R, T, B, T, L, L, ]; // ┏━┓ ┏━┓ R B R B // ┃ ┗━┛ ┃ T R T B // ┃ ┏━┓ ┃ T B L B // ┗━┛ ┗━┛ T L T L lut[4][4] = [ R, B, R, B, T, R, T, B, T, B, L, B, T, L, T, L, ]; // ┏━━━┓ ┏━┓ R R B R B // ┗━┓ ┗━┛ ┃ T L R T B // ┏━┛ ┏━┓ ┃ R T B L B // ┗━━━┛ ┗━┛ T L L T L lut[5][4] = [ R, R, B, R, B, T, L, R, T, B, R, T, B, L, B, T, L, L, T, L, ]; // ┏━┓ ┏━┓ R B R B // ┃ ┗━┛ ┃ T R T B // ┗━┓ ┏━┛ T L B L // ┏━┛ ┗━┓ R T R B // ┗━━━━━┛ T L L L lut[4][5] = [ R, B, R, B, T, R, T, B, T, L, B, L, R, T, R, B, T, L, L, L, ]; // ┏━┓ ┏━┓ R B R B // ┃ ┗━┛ ┃ T R T B // ┗━┓ ┏━┛ T L B L // ┏━┛ ┗━┓ R T R B // ┃ ┏━┓ ┃ T B L B // ┗━┛ ┗━┛ T L T L lut[4][6] = [ R, B, R, B, T, R, T, B, T, L, B, L, R, T, R, B, T, B, L, B, T, L, T, L, ]; // ┏━━━┓ ┏━━━┓ R R B R R B // ┗━┓ ┗━┛ ┏━┛ T L R T B L // ┏━┛ ┏━┓ ┗━┓ R T B L R B // ┗━━━┛ ┗━━━┛ T L L T L L lut[6][4] = [ R, R, B, R, R, B, T, L, R, T, B, L, R, T, B, L, R, B, T, L, L, T, L, L, ]; // ┏━┓ ┏━┓ R B R B // ┃ ┗━┛ ┃ T R T B // ┗━┓ ┏━┛ T L B L // ┏━┛ ┗━┓ R T R B // ┗━┓ ┏━┛ T L B L // ┏━┛ ┗━┓ R T R B // ┗━━━━━┛ T L L L lut[4][7] = [ R, B, R, B, T, R, T, B, T, L, B, L, R, T, R, B, T, L, B, L, R, T, R, B, T, L, L, L, ]; // ┏━━━┓ ┏━┓ ┏━┓ R R B R B R B // ┗━┓ ┗━┛ ┗━┛ ┃ T L R T R T B // ┏━┛ ┏━┓ ┏━┓ ┃ R T B L B L B // ┗━━━┛ ┗━┛ ┗━┛ T L L T L T L lut[7][4] = [ R, R, B, R, B, R, B, T, L, R, T, R, T, B, R, T, B, L, B, L, B, T, L, L, T, L, T, L, ]; // ┏━━━┓ ┏━┓ R R B R B // ┗━┓ ┗━┛ ┃ T L R T B // ┏━┛ ┏━┓ ┃ R T B L B // ┗━┓ ┃ ┗━┛ T L B T L // ┏━┛ ┃ ┏━┓ R T B R B // ┗━┓ ┗━┛ ┃ T L R T B // ┏━┛ ┏━┓ ┃ R T B L B // ┗━━━┛ ┗━┛ T L L T L lut[5][8] = [ R, R, B, R, B, T, L, R, T, B, R, T, B, L, B, T, L, B, T, L, R, T, B, R, B, T, L, R, T, B, R, T, B, L, B, T, L, L, T, L, ]; // ┏━┓ ┏━┓ ┏━┓ ┏━┓ R B R B R B R B // ┃ ┗━┛ ┗━┛ ┗━┛ ┃ T R T R T R T B // ┗━┓ ┏━━━━━┓ ┏━┛ T L B L L L B L // ┏━┛ ┗━┓ ┏━┛ ┗━┓ R T R B R T R B // ┗━━━━━┛ ┗━━━━━┛ T L L L T L L L lut[8][5] = [ R, B, R, B, R, B, R, B, T, R, T, R, T, R, T, B, T, L, B, L, L, L, B, L, R, T, R, B, R, T, R, B, T, L, L, L, T, L, L, L, ]; lut[5][5] = [ R, R, B, R, B, T, L, R, T, B, R, T, BL, B, L, T, B, T, R, B, T, L, T, L, L, ]; lut[5][6] = [ R, B, R, R, B, T, R, T, BL, B, T, L, B, T, L, R, T, RB, R, B, T, B, L, T, B, T, L, T, L, L, ]; lut[6][5] = [ R, R, B, R, R, B, T, L, R, T, B, L, R, T, BL, L, R, B, T, R, B, R, LT, B, T, L, L, T, L, L ]; lut[6][7] = [ R, R, B, R, R, B, T, BL, L, T, B, L, T, L, TR, BL, R, B, R, T, B, R, LT, B, T, L, L, T, L, L, ]; lut[5][7] = [ R, R, B, R, B, T, B, R, T, B, T, L, LT, B, L, R, B, T, R, B, T, R, T, B, L, T, B, L, R, B, T, L, T, L, L, ]; lut[7][5] = [ R, R, R, B, R, R, B, T, L, B, L, T, L, B, R, T, R, R, TR, B, L, T, B, L, B, L, R, B, T, L, T, L, T, L, L, ]; lut[6][6] = [ R, B, R, B, R, B, T, R, T, R, T, B, T, L, L, B, L, L, R, R, T, R, R, B, T, B, L, B, L, B, T, L, T, L, T, L, ]; lut[6][7] = [ R, B, R, B, R, B, T, R, T, R, T, B, T, B, L, B, L, L, T, L, T, B, R, B, R, R, T, R, T, B, T, B, L, B, L, B, T, L, T, L, T, L, ]; lut[7][6] = [ R, R, B, R, R, R, B, T, L, B, T, L, B, L, R, T, R, R, T, R, B, T, L, B, L, L, B, L, R, T, R, B, T, R, B, T, L, L, L, T, L, L, ]; lut[7][7] = [ R, B, R, B, R, R, B, T, R, T, B, T, B, L, T, L, L, R, T, R, B, R, R, T, BL, B, L, L, T, L, B, T, R, R, B, R, T, B, T, B, L, B, T, L, L, T, L, T, L, ]; return lut; }47:T77c,function hcurveTest(width, height, alwaysSplitMiddle, scale) { if (height === undefined) height = width; const cb = new CurveBuilder(width, height); function split(x, y, w, h, splitTop, splitLeft) { if (cb.lutH[w] && cb.lutH[w][h]) { // are we in a "base case" of our LUT? // if so, draw that version cb.putH(x, y, w, h); // otherwise, would splitting along the height result in a "more square" shape? } else if (!(alwaysSplitMiddle && w >= 4) && h >= 4 && h > Math.SQRT2 * w) { const splity = (h / 2) | 0; cb.connectVertical( splitLeft || alwaysSplitMiddle ? x : x + w - 2, y + splity - 1 ); split(x, y, w, splity, splitTop, !splitLeft); split(x, y + splity, w, h - splity, splitTop, !splitLeft); // otherwise, would splitting along the width result in a "more square" shape? } else if (!(alwaysSplitMiddle && h >= 4) && w >= 4 && w > Math.SQRT2 * h) { const splitx = (w / 2) | 0; cb.connectHorizontal( x + splitx - 1, splitTop || alwaysSplitMiddle ? y : y + h - 2 ); split(x, y, splitx, h, !splitTop, splitLeft); split(x + splitx, y, w - splitx, h, !splitTop, splitLeft); } else if (w >= 4 && h >= 4) { // otherwise, is our current quadrant large enough to // split both horizonally and vertically? const splitx = (w / 2) | 0; const splity = (h / 2) | 0; cb.connectH(x + splitx - 1, y + splity - 1); split(x, y, splitx, splity, true, true); split(x + splitx, y, w - splitx, splity, true, false); split(x, y + splity, splitx, h - splity, false, true); split(x + splitx, y + splity, w - splitx, h - splity, false, false); } else { // at this point it's guaranteed to be 2xN or Nx2 cb.loop(x, y, w, h); } } split(0, 0, width, height, true, true); return cb.toCurve().draw(scale || 2, 10); }48:T79a,randomTest = { await visibility(); // make the randomness a bit more bell curve-shaped const { random } = Math; const rnd_0 = () => (random() - random() + 1) * 0.5; const rnd_1 = () => (rnd_0() + rnd_0())*0.5; const rnd_2 = () => (rnd_1() + rnd_1())*0.5; const rnd_3 = () => (rnd_2() + rnd_2())*0.5; const rnd_4 = () => (rnd_3() + rnd_3())*0.5; // possible ways of manipulating the bias even more // the smaller the region the more random const rnd_more = (w) => w < 8 ? rnd_0() : w < 16 ? rnd_2() : w < 32 ? rnd_4() : w < 64 ? rnd_3() : rnd_4(); // the smaller the region the less random const rnd_less = (w) => w < 16 ? rnd_4() : w < 64 ? rnd_3() : w < 256 ? rnd_2() : w < 512 ? rnd_1() : rnd_0(); const rnd = rnd_more; const width = 128 + 64; const height = 128; const cb = new CurveBuilder(width, height); function split(x, y, w, h) { if ( (w <= 6 && h <= 5 || w <=5 && h <= 6) && cb.lutH[w] && cb.lutH[w][h] ) { cb.putH(x, y, w, h); } else if (w >= 4 && (w >= h * 2**0.5 || h < 4)) { const splitx = 2 + ((rnd(w) * (w - 3)) | 0); cb.connectHorizontal(x + splitx - 1, y); split(x, y, splitx, h); split(x + splitx, y, w - splitx, h); } else if (h >= 4 && (h >= w * 2**0.5 || w < 4)) { const splity = (2 + rnd(h) * (h - 3)) | 0; cb.connectVertical(x, y + splity - 1); split(x, y, w, splity); split(x, y + splity, w, h - splity); } else if (w >= 4 && h >= 4) { let splitx = 2 + ((rnd(w) * (w - 3)) | 0); let splity = (2 + rnd(h) * (h - 3)) | 0; cb.connectH(x + splitx - 1, y + splity - 1); split(x, y, splitx, splity); split(x + splitx, y, w - splitx, splity); split(x, y + splity, splitx, h - splity); split(x + splitx, y + splity, w - splitx, h - splity); } else { cb.loop(x, y, w, h); } } split(0, 0, width, height); return cb.toCurve().draw(1, 256); }49:T885,// Force splitting at even rows/columns. This should avoid all diagonal lines (can you figure out why?) randomTestEven = { await visibility(); // make the randomness a bit more bell curve-shaped const { random } = Math; const rnd_0 = () => (random() - random() + 1) * 0.5; const rnd_1 = () => (rnd_0() + rnd_0())*0.5; const rnd_2 = () => (rnd_1() + rnd_1())*0.5; const rnd_3 = () => (rnd_2() + rnd_2())*0.5; const rnd_4 = () => (rnd_3() + rnd_3())*0.5; // possible ways of manipulating the bias even more // the smaller the region the more random const rnd_more = (w) => w < 8 ? rnd_0() : w < 16 ? rnd_2() : w < 32 ? rnd_4() : w < 64 ? rnd_3() : rnd_4(); // the smaller the region the less random const rnd_less = (w) => w < 16 ? rnd_4() : w < 64 ? rnd_3() : w < 256 ? rnd_2() : w < 512 ? rnd_1() : rnd_0(); const rnd = rnd_2; const width = 128 + 64; const height = 128; const cb = new CurveBuilder(width, height); function split(x, y, w, h) { // if (cb.lutH[w] && cb.lutH[w][h]) { // cb.putH(x, y, w, h); // } else if (w >= 4 && (w >= h * 2**0.5 || h < 4)) { const splitx = 2 + ((rnd(w) * (w - 2) * 0.5) | 0) * 2; cb.connectHorizontal(x + splitx - 1, random() < 0.5 ? y+h-2 : y); split(x, y, splitx, h); split(x + splitx, y, w - splitx, h); } else if (h >= 4 && (h >= w * 2**0.5 || w < 4)) { const splity = 2 + ((rnd(h) * (h - 2) * 0.5) | 0) * 2; cb.connectVertical(random() < 0.5 ? x+w-2 : x, y + splity - 1); split(x, y, w, splity); split(x, y + splity, w, h - splity); } else if (w >= 4 && h >= 4) { const splitx = 2 + ((rnd(w) * (w - 2) * 0.5) | 0) * 2; const splity = 2 + ((rnd(h) * (h - 2) * 0.5) | 0) * 2; random() < 0.5 ? cb.connectH(x + splitx - 1, y + splity - 1) : cb.connectI(x + splitx - 1, y + splity - 1); split(x, y, splitx, splity); split(x + splitx, y, w - splitx, splity); split(x, y + splity, splitx, h - splity); split(x + splitx, y + splity, w - splitx, h - splity); } else { cb.loop(x, y, w, h); } } split(0, 0, width, height); return cb.toCurve().draw(1, 256); }4a:T10f9,letters = { const { T, TR, R, RB, B, BL, L, LT } = directions; const _ = 0; // All characters are 2x4, so 3x5 in terms of // points from which lines originate, // scanned left-to-right, top-to-bottom const a = [_, RB, _, TR, _, B, T + R, R, B, T, _, B, T, _, _], b = [R, RB, _, T, _, BL, T, L + RB, _, T, _, BL, T, L, _], c = [_, BL, _, B, _, LT, B, _, _, RB, _, _, _, TR, _], d = [B, L, _, B, _, LT, B, _, T, B, _, T, R, TR, _], e = [B, L, L, B, _, _, B, L, _, B, _, _, _, L, L], f = [B, L, L, B, _, _, B, L, _, B, _, _, _, _, _], g = [_, BL, L, B, _, _, B, _, L, RB, _, T, _, R, T], h = [_, _, B, T, _, B, T, L + R, B, T, _, B, T, _, _], i = [R, R, _, _, T, _, _, T, _, _, T, _, _, L + T, L], j = [R, R, B, _, _, B, _, _, B, _, _, BL, _, LT, _], k = [B, _, BL, B, BL, _, B, _, _, B, LT, _, _, _, LT], l = [B, _, _, B, _, _, B, _, _, B, _, _, R, R, _], m = [RB, _, B, T, TR, B, T, _, B, T, _, B, T, _, _], n = [B, L, _, B, _, LT, B, _, T, B, _, T, _, _, T], o = [_, RB, _, TR, _, B, T, _, B, T, _, BL, _, LT, _], p = [B, L, _, B, _, LT, B, L + TR, _, B, _, _, _, _, _], q = [_, R, B, TR + RB, _, B, _, R, B, _, _, B, _, _, _], r = [R, RB, _, T, _, BL, T, L, _, T, _, LT, T, _, T], s = [_, BL, L, RB, _, _, _, RB, _, _, _, BL, _, L, _], t = [R, R, _, _, T, _, _, T, _, _, T, _, _, T, _], u = [B, _, _, B, _, T, B, _, T, RB, _, T, _, R, T], v = [B, _, _, B, _, T, B, _, T, RB, _, T, _, TR, _], x = [B, _, B, RB, _, BL, _, _, _, TR, _, LT, T, _, T], y = [B, _, B, RB, _, BL, _, B, _, _, B, _, _, _, _], z = [R, R, B, _, _, BL, _, BL, _, B, _, _, R, R, _]; return { a, A: a, b, B: b, c, C: c, d, D: d, e, E: e, f, F: f, g, G: g, h, H: h, i, I: i, j, J: j, k, K: k, l, L: l, m, M: m, n, N: n, o, O: o, p, P: p, q, Q: q, r, R: r, s, S: s, t, T: t, u, U: u, v, V: v, x, X: x, y, Y: y, z, Z: z, 0: [R, R, B, T, _, B, T, TR, B, T + TR, _, B, T, L, L], 1: [_, B, _, TR, B, _, _, B, _, _, B, _, R, R, _], 2: [_, RB, _, TR, _, BL, _, BL, _, B, _, _, R, R, _], 3: [R, RB, _, _, _, BL, _, L, _, _, _, LT, R, TR, _], 4: [_, _, _, _, BL, T, B, _, T, R, R, T, _, _, T], 5: [B, L, L, B, _, _, R, RB, _, _, _, B, _, L, L], 6: [_, BL, L, B, _, _, B, L, L, B, _, T, R, R, T], 7: [R, R, B, _, _, BL, R, BL, L, B, _, _, _, _, _], 8: [R, R, B, T, _, B, T, L, L + B, T, _, B, T, L, L], 9: [_, BL, L, B, _, T, R, R, T, _, _, T, R, TR, _], "!": [R, B, _, T, B, _, T, L, _, R, B, _, T, L, _], "?": [R, R, B, T, L, BL, TR, L, _, R, B, _, T, L, _], ".": [_, _, _, _, _, _, _, _, _, R, B, _, T, L, _], ",": [_, _, _, _, _, _, _, _, _, R, BL, _, T, _, _], ":": [_, _, _, R, B, _, T, L, _, R, B, _, T, L, _], ";": [_, _, _, R, B, _, T, L, _, R, BL, _, T, _, _], "-": [_, _, _, _, _, _, R, R, _, _, _, _, _, _, _], "+": [_, _, _, _, B, _, R, _, L, _, T, _, _, _, _], '*': [_, _, _, RB, B, BL, R, _, L, TR, T, LT, _, _, _], "%": [R, B, _, T, L, _, _, TR, _, TR, R, B, _, T, L], "=": [_, _, _, _, _, _, R, _, _, R, _, _, _, _, _], '(': [_, _, BL, _, B, _, _, B, _, _, RB, _, _, _, _], ')': [RB, _, _, _, B, _, _, B, _, _, BL, _, _, _, _], '[': [_, B, L, _, B, _, _, B, _, _, B, _, _, R, _], ']': [R, B, _, _, B, _, _, B, _, _, B, _, _, L, _], '{': [_, _, BL, _, RB, _, _, _, L, _, TR, _, _, _, LT], '}': [RB, _, _, _, BL, _, R, _, _, _, LT, _, TR, _, _], '|': [_, B, _, _, B, _, _, B, _, _, B, _, _, _, _], '/': [_, _, _, _, _, T, _, TR, _, TR, _, _, T, _, _], '\\': [B, _, _, RB, _, _, _, RB, _, _, _, B, _, _, _], "'": [_, B, _, _, _, _, _, _, _, _, _, _, _, _, _], '"': [_, B, B, _, _, _, _, _, _, _, _, _, _, _, _], '`': [RB, _, _, _, _, _, _, _, _, _, _, _, _, _, _], '“': [_, _, _, TR, TR, _, _, _, _, _, _, _, _, _, _], '”': [RB, RB, _, _, _, _, _, _, _, _, _, _, _, _, _], '«': [_, _, _, _, _, _, TR, TR, _, _, LT, LT, _, _, _], '»': [_, _, _, _, _, _, _, LT, LT, TR, TR, _, _, _, _], '「': [_, R, _, _, T, _, _, T, _, _, _, _, _, _, _], '」': [_, _, _, _, _, _, _, B, _, _, B, _, _, L, _] }; }4b:T15f9,// Used to insert/modify paths on a grid CurveBuilder = { class CurveBuilder { constructor(width, height) { this.grid = new Uint8Array(width * height); this.width = width; this.height = height; } toCurve(width, height) { return new Curve(this.grid, this.width, this.height); } loop(x, y, w, h) { const { grid, width, height } = this; const { T, R, B, L } = directions; for (let i = 0; i < w - 1; i++) { const p00 = ((x + i) % width) + y * width; const p11 = ((x + w - 1 - i) % width) + ((y + h - 1) % height) * width; if (grid[p00] === 0) grid[p00] = R; if (grid[p11] === 0) grid[p11] = L; } for (let i = 0; i < h - 1; i++) { const p01 = ((x + w - 1) % width) + ((y + i) % height) * width; const p10 = x + ((y + h - 1 - i) % height) * width; if (grid[p01] === 0) grid[p01] = B; if (grid[p10] === 0) grid[p10] = T; } return this; } line(x0, y0, x1, y1, mask) { const { grid, width, height } = this; let dx = x1 - x0; let dy = y1 - y0; // step along the longest axis const axis = Math.max(Math.abs(dx), Math.abs(dy)); const { T, R, B, L, TR, RB, BL, TL } = directions; for (let i = 0; i < axis; i++) { const x = Math.round((x0 * (axis - i) + x1 * i) / axis); const y = Math.round((y0 * (axis - i) + y1 * i) / axis); const xi = Math.round((x0 * (axis - i - 1) + x1 * (i + 1)) / axis); const yi = Math.round((y0 * (axis - i - 1) + y1 * (i + 1)) / axis); dx = xi - x; dy = yi - y; let direction; if (dx > 0) { direction = dy > 0 ? RB : dy < 0 ? TR : R; } else if (dx < 0) { direction = dy > 0 ? BL : dy < 0 ? TL : L; } else { direction = dy > 0 ? B : T; } const point = (x % width) + (y % height) * width; grid[point] = mask ? grid[point] | direction : direction; } return this; } drawPolygon(x0, y0, deltas) { for (const [dx, dy] of deltas) { const x1 = x0 + dx, y1 = y0 + dy; this.line(x0, y0, x1, y1, true); x0 = x1; y0 = y1; } return this; } text(x, y, str) { const { grid, width, height } = this; const x0 = x; for (const char of str) { if (char === '\n' || char === '\r') { x = x0; y += 8; } else { const letter = letters[char]; if (letter) { for (let j = 0, yj = y + j; j < 5 && yj < height; j++, yj++) { for (let i = 0, xi = x + i; i < 3 && xi < width; i++, xi++) { const point = xi + yj * width; grid[point] |= letter[i + j * 3]; } } } x += 3; } } return this; } putH(x, y, w, h) { const { grid, width, height } = this; const lut = this.lutH[w][h]; for (let j = 0; j < h; j++) { const line = ((j + y) % height) * width; for (let i = 0; i < w; i++) { const idx = ((x + i) % width) + line; if (grid[idx] === 0) { // only write on empty spots grid[idx] = lut[i + j * w]; } } } return this; } connectH(x, y) { const { grid, width, height } = this; const { T, R, B, L } = directions; grid[((x - 1 + width) % width) + ((y + 1) % height) * width] = T; grid[x + y * width] = R; grid[((x + 2) % width) + y * width] = B; grid[((x + 1) % width) + ((y + 1) % height) * width] = L; return this; } connectI(x, y) { const { grid, width, height } = this; const { T, R, B, L } = directions; grid[(x % width) + ((y + 1) % height) * width] = T; grid[x + ((y - 1 + height)%height) * width] = R; grid[((x + 1) % width) + y * width] = B; grid[((x + 1) % width) + ((y + 2) % height) * width] = L; return this; } connectRandom(x, y, pick = Math.random() * 16 | 0) { const { grid, width, height } = this; const { T, R, B, L, TL, TR, BL, BR} = directions; // start on bottom right, go clockwise if (pick & 1) { grid[((x + 1) % width) + ((y + 2) % height) * width] = (pick & 2) ? L : TL; } else { grid[((x + 1) % width) + ((y + 1) % height) * width] = (pick & 2) ? BL : L; } if (pick & 2) { grid[(x % width) + ((y+1) % height) * width] = (pick & 4) ? T : TL; } else { grid[((x - 1 + width) % width) + ((y+1) % height) * width] = (pick & 4) ? TR : T; } if (pick & 4) { grid[(x % width) + ((y - 1 + height) % height) * width] = (pick & 8) ? R : BR; } else { grid[(x % width) + (y % height) * width] = (pick & 8) ? TR : R; } if (pick & 8) { grid[(x + 1 % width) + (y % height) * width] = (pick & 1) ? B : BR; } else { grid[(x + 2 % width) + (y % height) * width] = (pick & 1) ? BL : B; } } connectHorizontal(x, y) { const { grid, width, height } = this; const { R, L } = directions; grid[x + y * width] = R; grid[((x + 1) % width) + ((y + 1) % height) * width] = L; return this; } connectVertical(x, y) { const { grid, width, height } = this; const { T, B } = directions; grid[x + ((y + 1) % height) * width] = T; grid[((x + 1) % width) + y * width] = B; return this; } } CurveBuilder.prototype.lutH = lutH; return CurveBuilder; }4c:T653,function hcurve3x3(width, height, alwaysSplitMiddle) { if (height === undefined) height = width; const cb = new CurveBuilder(width, height); function split(x, y, w, h) { if (w === 3 && h === 3) { cb.putH(x, y, w, h); // otherwise, would splitting along the height result in a "more square" shape? } else if (h >= 4 && 3 * h >= 4 * w && !(alwaysSplitMiddle && w >= 4)) { const splity = (h / 2) | 0; cb.connectVertical(x, y + splity - 1); split(x, y, w, splity); split(x, y + splity, w, h - splity); // otherwise, would splitting along the width result in a "more square" shape? } else if (w >= 4 && 3 * w >= 4 * h && !(alwaysSplitMiddle && h >= 4)) { const splitx = (w / 2) | 0; cb.connectHorizontal(x + splitx - 1, y); split(x, y, splitx, h); split(x + splitx, y, w - splitx, h); } else if (w >= 4 && h >= 4) { // otherwise, is our current quadrant large enough to // split both horizonally and vertically, and are the // proportions such that this makes sense? // (I picked any rectangle proportion between 2:1 and 1:2) const splitx = (w / 2) | 0; const splity = (h / 2) | 0; cb.connectH(x + splitx - 1, y + splity - 1); split(x, y, splitx, splity); split(x + splitx, y, w - splitx, splity); split(x, y + splity, splitx, h - splity); split(x + splitx, y + splity, w - splitx, h - splity); } else { // at this point it's guaranteed to be 2xN or Nx2 cb.loop(x, y, w, h); } } split(0, 0, width, height); return cb.toCurve().draw(2, 10); }4d:T4c4,function hcurveTest2(width, height, alwaysSplitMiddle) { if (height === undefined) height = width; const cb = new CurveBuilder(width, height); function split(x, y, w, h) { if (w <= 3 && h <= 3 && cb.lutH[w] && cb.lutH[w][h]) { // are we in a "base case" of our LUT? // if so, draw that version cb.putH(x, y, w, h); } else if (h >= w) { const splity = (h / 2) | 0; cb.connectVertical(x, y + splity - 1); split(x, y, w, splity); split(x, y + splity, w, h - splity); } else if (w >= h) { const splitx = (w / 2) | 0; cb.connectHorizontal(x + splitx - 1, y); split(x, y, splitx, h); split(x + splitx, y, w - splitx, h); } else if (w >= 4 && h >= 4) { const splitx = (w / 2) | 0; const splity = (h / 2) | 0; cb.connectH(x + splitx - 1, y + splity - 1); split(x, y, splitx, splity); split(x + splitx, y, w - splitx, splity); split(x, y + splity, splitx, h - splity); split(x + splitx, y + splity, w - splitx, h - splity); } else { // at this point it's guaranteed to be 2xN or Nx2 cb.loop(x, y, w, h); } } split(0, 0, width, height); return cb.toCurve().draw(2, 10); }4e:[] 43:{"id":"160c7535b293e7ce","slug":"arbitrary-hamiltonian-curves","title":"Arbitrary Hamiltonian Curves","thumbnail":"4c8a9546386455524a512eec72659e0ec69d7f6ef6be52e5f49665abc9630a5c","access_level":"public","create_time":"$D2020-04-15T20:20:02.894Z","update_time":"$D2026-08-12T10:54:19.658Z","view_time":null,"first_public_time":"$D2020-07-05T20:51:27.880Z","has_unpublished_edits":null,"fork":false,"stars":29,"starred":false,"owner":{"type":"team","id":"3f83172cfde1e56a","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":"starter_2024","bio":"Tinkering with code and algorithms for fun"},"version":1947,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null,"bio":"Tinkering with code and algorithms for fun"}],"members":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":{"id":"5462a115d4372a20","slug":"space-filling-curves","title":"Space-Filling Curves","owner":{"id":"3f83172cfde1e56a","login":"jobleonard","name":"Job van der Zwan"}},"type":"notebook","body":{"titling":"auto","title":"Arbitrary Hamiltonian Curves","cells":[{"id":0,"value":"$45","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1279,"value":"LUTtestMinimal = {\n const size = 8;\n const cb = new CurveBuilder(size, size);\n let x = 1,\n y = 1;\n for (let h = 2; h <= 3; h++) {\n for (let w = 2; w <= 3; w++) {\n let lut = cb.lutH[w][h];\n if (lut) {\n if ((x + w) % size < x) {\n x = 1;\n y += h;\n }\n cb.putH(x, y, w, h);\n x = x + w + 1;\n }\n }\n }\n return new Curve(cb.grid).line(8, 10);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":534,"value":"md`This works, but will result in a lot of diagonal connections if we happen to pick a starting length that results in a lot of 3×3 grids.:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1380,"value":"hcurve3x3(23)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1389,"value":"md`We can also see along the left side of the above image that we can end up with very elongated H's, resulting in long stretches of straight lines. This somewhat undermines the idea of optimizing locality, which is often the reason to use these types of curves.\n\nWhat if instead of only using a 3×3 fall-back grid, we try to create a set of \"least-terrible\" filled N×M loops and insert those whenever appropriate? Where \"least terrible\" is interpreted here as *\"least amount of diagonal lines and long stretches of straight lines\"*. We'll get something like this:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1393,"value":"hcurveTest(23)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1463,"value":"md`Here is the grid of fallback-loops that that let us achieve that:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":73,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"LUTtest = {\n const size = 32;\n const cb = new CurveBuilder(size, size);\n let x = 1, y = 1;\n for (let h = 2; h <= 8; h++) {\n for (let w = 2; w <= 8; w++) {\n let lut = cb.lutH[w][h];\n if (lut){\n if ((x + w)%size < x) {\n x = 1;\n y += h;\n }\n cb.putH(x, y, w, h);\n x = x + w + 1;\n }\n }\n }\n return new Curve(cb.grid).line(2, 10);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":607,"value":"md`It is probably possible to make more best-fit shapes for even larger sizes, but this seems good enough for now. Using this set of fall-back grids we can finalize our curve-building function:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"$47","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1534,"value":"hcurveTest(23, 11, false, 4)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":368,"value":"hcurveTest(13, 7, false, 6)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":234,"value":"// If the proportions get really elongated, it splits the rectangle in half instead of in quarts\nhcurveTest(5 * 16, 16)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":902,"value":"// we can also force splitting into quarts, as a point of comparison\nhcurveTest(5 * 16, 16, true, 2)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1299,"value":"hcurveTest(17, 37)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":499,"value":"md`The fun part is that they actually become H-curves when the dimensions are a power of two:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"hcurveTest(8)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":978,"value":"hcurveTest(16)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":312,"value":"hcurveTest(16, 8)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"hcurveTest(128, 32, false, 1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":904,"value":"hcurveTest(32, 8, true)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":236,"value":"hcurveTest(9, 7)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":240,"value":"hcurveTest(11)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":242,"value":"hcurveTest(32+16, 32)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":290,"value":"hcurveTest(32, 32+16)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":288,"value":"hcurveTest(7*8,7*8)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":625,"value":"chaotic = md`Instead of splitting neatly in the middle, or zig-zagging when one side gets too long, we can also split at random positions. The result is quite chaotic, but still forms a closed loop:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"$48","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1094,"value":"md`Note that we can avoid all diagonal lines by constraining the splitting to even rows/columns:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":427,"value":"$49","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"import {directions, Curve} from \"@jobleonard/skewed-curves\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":697,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":710,"value":"// Not used in this notebook, but in others that depend on this one\nletterTest = {\n const size = 32+12;\n const cb = new CurveBuilder(size, size);\n const chars = Object.keys(letters);\n let x = 1, y = 1;\n for (const char of chars) {\n cb.text(x, y, char);\n x += 3;\n if (x+3 > size) {\n x = 1;\n y += 6;\n }\n }\n return cb.toCurve().line(2, 10);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":629,"value":"lineTest = {\n const size = 32;\n const cb = new CurveBuilder(size, size);\n for (let i = 0; i < 10; i++) {\n const x0 = (Math.random() * size) | 0;\n const y0 = (Math.random() * size) | 0;\n const x1 = (Math.random() * size) | 0;\n const y1 = (Math.random() * size) | 0;\n cb.line(x0, y0, x1, y1, true);\n }\n return cb.toCurve().line(2, 10);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1151,"value":"lineTest2 = {\n const size = 48;\n const cb = new CurveBuilder(size, size);\n for (let i = 0; i <= 10; i++) {\n cb.line(i, 0, i + i, 10, true);\n cb.line(20 - i, 12, 20 - i - i, 22, true);\n cb.line(i, 34, i + i, 24, true);\n cb.line(20 - i, 46, 20 - i - i, 36, true);\n }\n return cb.toCurve().line(2, 10);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1180,"value":"lineTest3 = {\n const size = 3;\n const cb = new CurveBuilder(size, size);\n cb.line(0, 0, 0, 2, true);\n cb.line(0, 2, 1, 2, true);\n cb.line(1, 2, 1, 0, true);\n cb.line(1, 0, 2, 0, true);\n cb.line(2, 0, 2, 2, true);\n return cb.toCurve().draw(2, 10);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1190,"value":"polygonTest2 = {\n const size = 3;\n const cb = new CurveBuilder(size, size);\n cb.drawPolygon(0, 0, [[0, 2], [1, 0], [0, -2], [1, 0], [0, 2]]);\n return cb.toCurve().draw(2, 10);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"$4b","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":96,"value":"// Testing the basic functionality of the CurveBuilder class above\nloopTest = {\n const size = 32;\n const cb = new CurveBuilder(size, size);\n let x = 1, y = 1;\n for (let h = 2; h <= 8; h++) {\n for (let w = 2; w <= 8; w++) {\n let lut = cb.lutH[w][h];\n if (lut){\n if ((x + w)%size < x) {\n x = 1;\n y += h;\n }\n cb.loop(x, y, w, h);\n x = x + w + 1;\n }\n }\n }\n return cb.toCurve().line(2, 10);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1099,"value":"// Testing the polygon functionality\npolygonTest = {\n const size = 64;\n const cb = new CurveBuilder(size, size);\n const deltas = [];\n const { random } = Math;\n const x = (random() * size) | 0;\n const y = (random() * size) | 0;\n let x0 = x,\n y0 = y;\n for (let i = 0; i < 10; i++) {\n const x1 = (random() * size) | 0;\n const y1 = (random() * size) | 0;\n deltas.push([x1 - x0, y1 - y0]);\n x0 = x1;\n y0 = y1;\n }\n cb.drawPolygon(x, y, deltas);\n return cb.toCurve().line(1, 10);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1291,"value":"$4c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1638,"value":"hcurve3x3(13, 7)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1694,"value":"$4d","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1696,"value":"hcurveTest2(96, 48)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4e","stdlib":"1"}} 44:"$43:body"