Software engineer and visualization enthusiast. Lives in Cambridge, Massachusetts, with no dogs.
Unlisted
Edited
Jul 1, 2024
Importers
Plot.plot({
marks: [
Plot.rect([0], {
x1: decode2x(lo),
x2: decode2x(hi),
y1: decode2y(lo),
y2: decode2y(hi),
stroke: "#00f2",
fill: "#0001",
inset: -2
}),
Plot.line(xy, {
x: (d) => d[0],
y: (d) => d[1],
stroke: color,
strokeWidth: 2,
channels: {
xBin: (d) => d[0].toString(2).padStart(4, "0"),
yBin: (d) => d[1].toString(2).padStart(4, "0")
},
tip: true
}),
Plot.text(xy, {
x: (d) => d[0],
y: (d) => d[1],
stroke: "#fff",
fill: "#000",
text: (d) => {
const x = d[0].toString(2).padStart(4, "0");
const y = d[1].toString(2).padStart(4, "0");
return `${x}\n\n${y}`;
}
}),
Plot.text(zs, {
x: (d, i) => xy[i][0],
y: (d, i) => xy[i][1],
stroke: "#fff",
fill: "#000",
fontWeight: "bold",
fill: "#f0f"
})
],
y: { reverse: true },
axis: null,
margin: 25,
aspectRatio: 1,
width: 400
})
// https://mediatum.ub.tum.de/doc/601718/document.pdf
litMaxBigMin
encode2 = (x, y) => ((Part1By1(y) << 1) + Part1By1(x)) >>> 0
encode3 = (x, y, z) =>
((Part1By2(z) << 2) + (Part1By2(y) << 1) + Part1By2(x)) >>> 0
decode2x = (code) => Compact1By1(code >> 0)
decode2y = (code) => Compact1By1(code >> 1)
decode2 = (d) => [decode2x(d), decode2y(d)] // convenience function
decode3x = (code) => Compact1By2(code >> 0)
decode3y = (code) => Compact1By2(code >> 1)
decode3z = (code) => Compact1By2(code >> 2)
// Experimenting with byte interleaving since it is possible to implement using wasm simd128 (swizzle, shuffle)
function Part8By8(x) {
x &= 0x0000ffff; // x = ---- ---- ---- ---- fedc ba98 7654 3210
x = (x ^ (x << 8)) & 0x00ff00ff; // x = ---- ---- fedc ba98 ---- ---- 7654 3210
return x;
}
// "Insert" a 0 bit after each of the 16 low bits of x
function Part1By1(x) {
x &= 0x0000ffff; // x = ---- ---- ---- ---- fedc ba98 7654 3210
x = (x ^ (x << 8)) & 0x00ff00ff; // x = ---- ---- fedc ba98 ---- ---- 7654 3210
x = (x ^ (x << 4)) & 0x0f0f0f0f; // x = ---- fedc ---- ba98 ---- 7654 ---- 3210
x = (x ^ (x << 2)) & 0x33333333; // x = --fe --dc --ba --98 --76 --54 --32 --10
x = (x ^ (x << 1)) & 0x55555555; // x = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
return x;
}
function Compact1By1(x) {
x &= 0x55555555; // x = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
x = (x ^ (x >> 1)) & 0x33333333; // x = --fe --dc --ba --98 --76 --54 --32 --10
x = (x ^ (x >> 2)) & 0x0f0f0f0f; // x = ---- fedc ---- ba98 ---- 7654 ---- 3210
x = (x ^ (x >> 4)) & 0x00ff00ff; // x = ---- ---- fedc ba98 ---- ---- 7654 3210
x = (x ^ (x >> 8)) & 0x0000ffff; // x = ---- ---- ---- ---- fedc ba98 7654 3210
return x;
}
// "Insert" two 0 bits after each of the 10 low bits of x
function Part1By2(x) {
x &= 0x000003ff; // x = ---- ---- ---- ---- ---- --98 7654 3210
x = (x ^ (x << 16)) & 0xff0000ff; // x = ---- --98 ---- ---- ---- ---- 7654 3210
x = (x ^ (x << 8)) & 0x0300f00f; // x = ---- --98 ---- ---- 7654 ---- ---- 3210
x = (x ^ (x << 4)) & 0x030c30c3; // x = ---- --98 ---- 76-- --54 ---- 32-- --10
x = (x ^ (x << 2)) & 0x09249249; // x = ---- 9--8 --7- -6-- 5--4 --3- -2-- 1--0
return x;
}
function Compact1By2(x) {
x &= 0x09249249; // x = ---- 9--8 --7- -6-- 5--4 --3- -2-- 1--0
x = (x ^ (x >> 2)) & 0x030c30c3; // x = ---- --98 ---- 76-- --54 ---- 32-- --10
x = (x ^ (x >> 4)) & 0x0300f00f; // x = ---- --98 ---- ---- 7654 ---- ---- 3210
x = (x ^ (x >> 8)) & 0xff0000ff; // x = ---- --98 ---- ---- ---- ---- 7654 3210
x = (x ^ (x >> 16)) & 0x000003ff; // x = ---- ---- ---- ---- ---- --98 7654 3210
return x;
}
// From https://twitter.com/jonahharris/status/1337087177591820290/photo/1
// Used with permission from Jonah, who can't remember where he got it but
// says he obtained it under the BSD license.
// The basic idea is to determine the MSB, then split the range below that,
// using the common prefix together with a calculation for the new y/x
// positions indicating the split point.
// See also: https://snorrwe.onrender.com/posts/morton-table/#range-query-splitting
// NOTE: Only valid in 2d due to the masks
function litMaxBigMin(uMin, uMax) {
const xor = uMin ^ uMax;
const uMSBD = 1 << (31 - Math.clz32(xor)); // note: fails for xor = 0 (31-clz is negative)
const xMask = 0x55555555;
const yMask = 0xaaaaaaaa; // ~xMask;
const splitXAxis = uMSBD & xMask;
const splitMask = splitXAxis ? xMask : yMask;
const uMSMask = (uMSBD - 1) & splitMask;
const uLSMask = (uMSBD - 1) & ~splitMask;
const uBSCommon = uMin & ~(uMSBD + uMSBD - 1);
const uLitMax = uBSCommon | uMSMask | (uLSMask & uMax);
const uBigMin = uBSCommon | uMSBD | (uLSMask & uMin);
return { litMax: uLitMax >>> 0, bigMin: uBigMin >>> 0 };
}
Math.clz32(123)
litMaxBigMin(123, 456)
(0b100100100100100100100100100100100100100100100100100100100100).toString(16)
(0b1010101010101010101010101010101010101010).toString(16)
Math.clz32((0xffffffff - 2 ** 31) >>> 0)
msb = 32 - Math.clz32(7)
[low(msb), high(msb)]
// 0 1 | 2 3 | 4 5
low = (x) => x - (x & 1)
high = (x) => x | 1
f(8, 9)
(8).toString(2)
(9).toString(2)
(4).toString(2)
onesMask = (numOnes) =>
numOnes === 32 ? 0xffffffff : ((1 << numOnes) - 1) >>> 0
(~onesMask(4) >>> 0).toString(2)
(~onesMask(0) >>> 0).toString(2)
f = (min, max) => {
const xor = min ^ max;
if (xor === 0) return true; // we are good
const msb = 31 - Math.clz32(xor);
const lo = low(msb);
const hi = high(msb);
return {
xor,
msb,
lo,
hi,
minLo: min & (~onesMask(lo) >>> 0),
maxLo: max & (~onesMask(lo) >>> 0),
ret:
(min & (~onesMask(lo) >>> 0)) === (max & (~onesMask(lo) >>> 0)) &&
(min & (~onesMask(hi) >>> 0)) === (max & (~onesMask(hi) >>> 0))
};
}
a = (2 ** 32) >>> 0
Math.clz32(a)
decode2(1)
viewof color = Inputs.color({ label: "Favorite color", value: "#fec300" })
Plot.text({
(~0x55555555 >>> 0).toString(16)
lo
lo = 3
hi = 48
codeRangeContainedInBoundingBox(1, 4)
codeRangeContainedInBoundingBox(1, 6)
codeRangeContainedInBoundingBox(0, 7)
// We can determine whether the range of Morton codes between lo and hi (lo..hi) is contained within the bounding box by looking at the size of the box and comparing that to the number of codes in between.
// If the size of the box is exactly the number of codes in between, then no further splitting is required.
// You can also quantify the 'lossiness' by comparing the number of codes in the z-order code sequence to the size of the box, and determine a splitting criterion by bounding this loss rather than using the hard cutoff implemented below.
// NOTE: If there are fewer items in the range than in the bounding box, that means that we need more ranges to cover the actual bounding box (if that was our intention).
// topLeft and bottomRight are with respect to z-order along a Z: (tl, tr, bl, br).
codeRangeContainedInBoundingBox = (topLeft, bottomRight) => {
const width = decode2x(bottomRight) - decode2x(topLeft) + 1;
const height = decode2y(bottomRight) - decode2y(topLeft) + 1;
// assert (width >= 1 and height >= 1)
const count = width * height;
// Not all the points in the box might be in the z-range, hence the inequality
return bottomRight - topLeft + 1 <= count;
}
litMaxBigMin(5, 27)
litMaxBigMin(0, 15)
litMaxBigMin(48, 51)
litMaxBigMin(4, 27)
litMaxBigMin(5, 27)
litMaxBigMin(12, 15) // hmm... splits at 13/14, which is fine actually.
litMaxBigMin(15, 16) // ! interesting, bbox wise
litMaxBigMin(0, 53)
(0x5555).toString(2)
(0xaaaa).toString(2)
encode2(3, 0).toString(2)
encode2(2, 0).toString(2)
x = litMaxBigMin(lo, hi)
y = litMaxBigMin(lo, x.litMax)
z = litMaxBigMin(x.bigMin, hi)
encode2(0, 43328)
encode2(22208 - 1, 65600 - 1)
decode2(encode2(22208 - 1, 65600 - 1))
decode2(encode2((22208 - 1) >>> 0, (65600 - 1) >>> 0))
Type JavaScript, then Shift-Enter. Ctrl-space for more options. Arrow ↑/↓ to switch modes.
decode2y(65600)
// note: points ordered along zorder are not necessarily orderd in either x or ty; all you know is it is not before it in both dimensions
// {
// let passed = 0;
// const pow = 2;
// const sz = 2 ** pow;
// for (let iter = 0; iter < 10; iter++) {
// let start = encode3(
// Math.round(sz * Math.random()),
// Math.round(sz * Math.random()),
// Math.round(sz * Math.random())
// );
// let end = encode3(
// Math.round(sz * Math.random()),
// Math.round(sz * Math.random()),
// Math.round(sz * Math.random())
// );
// const startX = decode3x(start);
// const startY = decode3y(start);
// const endX = decode3x(end);
// const endY = decode3y(end);
// const ranges = [];
// splitIntoContiguousRanges(start, end, ({ min, max }) =>
// ranges.push({ min, max })
// );
// return { start, end, ranges };
// for (const { min, max } of ranges) {
// for (let value = min; value < max; value++) {
// const x = decode3x(value);
// const y = decode3y(value);
// assert(inRange(x, startX, endX), { startX, x, endX });
// assert(inRange(y, startY, endY), { startY, y, endY });
// passed++;
// }
// }
// }
// return passed;
// }
inRange = (v, start, end) => {
if (start > end) {
const tmp = start;
start = end;
end = tmp;
}
return start <= v && v <= end;
}
assert = (cond, other) => {
if (!cond) throw JSON.stringify(other);
}
encode2(3, 3)
codeRangeContainedInBoundingBox(3, 7)
splitIntoContiguousRanges = {
// Computes the minimal set of contiguous ranges that cover the
// (possibly non-power-of-two) rectangle specified by the Morton
// codes `min` and `max`.
// NOTE: We assume that min is the top-left and max is the bottom-right based on a Z-shape (in order, tl, tr, bl, br)
const s = [];
return (min, max, emit) => {
// todo: debug-asset that min is the top-left and max is the bottom-right.
// assert that max > min
s.length = 0;
s.push({ min, max }); // endpoints are inclusive
let range = { min, max: min - 1 }; // start the first range at the passed-in min
while (s.length) {
const { min, max } = s.pop();
if (codeRangeContainedInBoundingBox(min, max)) {
// coalesce contiguous ranges as they are emitted
if (range.max + 1 == min) {
range.max = max;
} else {
emit(range);
range = { min, max };
}
} else {
// Split the range
const { litMax, bigMin } = litMaxBigMin(min, max);
s.push({ min: bigMin, max });
s.push({ min, max: litMax });
}
}
// emit the final range being built up in the loop
if (range.max >= range.min) emit(range);
// emit a final range up to the passed-in max
if (range.max < max) emit({ min: range.max + 1, max });
};
}
litMaxBigMin(3, 48)
litMaxBigMin(123, 456)
{
const xs = [];
splitIntoContiguousRanges(3, 48, (x) => xs.push(x));
return xs;
}
litMaxBigMin
litMaxBigMin(0, 3)
splittable = (min, max) => {
const { litMax, bigMin } = litMaxBigMin(min, max);
return max - min !== litMax - min + max - bigMin + 1;
}
xsplittable = (min, max) => {
const { litMax, bigMin } = litMaxBigMin(min, max);
return [
max - min,
litMax - min,
max - bigMin,
litMax - min + max - bigMin + 1,
{ litMax, bigMin }
];
}
xsplittable(3, 48)
xsplittable(4, 13)
zs = d3.range(2 ** 6)
xy = d3.map(zs, decode2)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
