WiP

hilbertcurve.ts

import { AffineTransform } from "./math/2d/AffineTransform";
import { M } from "./math/2d/M";
import { V } from "./math/2d/V";

const R = [
  M(1, 0, 0, 1),
  M(0, 1, 1, 0),
  M(0, 1, 1, 0),
  M(-1, 0, 0, -1),
];

const T = [
  V(0, 1),
  V(1, 0)
]
/*
export function h2xy(n: number) {
  let m = n;
  let p = V(0, 0);
  for (let i = 0; m > 0; i++) {
    const l = 2 ** i;
    const q = m % 4;
    p = R[q].multiply(p).add(T[i % 2][q].scale(l));
    if (q === 3) {
      p = p.add(V(Math.max(0, l - 1), Math.max(0, l - 1)));
    }
    m = m >>> 2;
  }
  return p;
}
*/

let xy2h: number[][] = [];

export function h2xy(n: number) {
  let m = n >>> 2;
  let p = ((n: number) => {
    switch (n % 4) {
      case 0:
        return V(0, 0);
      case 1:
        return V(0, 1);
      case 2:
        return V(1, 1);
    }
    return V(1, 0);
  })(n);

  for (let i = 1; m > 0; i++) {
    const l = 2 ** i;
    switch (m % 4) {
      case 1:
        p = V(p.y, p.x).add(T[i % 2].scale(l));
        break;
      case 2:
        p = V(p.y, p.x).add(V(1, 1).scale(l));
        break;
      case 3:
        p = V(p.x * -1, p.y * -1).add(V(l - 1, l - 1)).add(T[(i + 1) % 2].scale(l));
        break;
    }
    m = m >>> 2;
  }
  if (xy2h[p.x] === undefined) xy2h[p.x] = [];
  xy2h[p.x][p.y] = n;
  return p;
}