Tinkering with code and algorithms for fun
function createWNframe(width, height, imageScale, scale, sourceData, d) {
const targetData = new ImageData(d.data.slice(), width);
for (let i = 0, n = sourceData.data.length; i < n; i += 4) {
const pixel = sourceData.data[i] < Math.random() * 256 ? 0 : 255;
targetData.data[i] = pixel;
targetData.data[i + 1] = pixel;
targetData.data[i + 2] = pixel;
targetData.data[i + 3] = 255;
}
return targetData;
}
mutable framesPQT = {
width;
return [];
}
function createPQTframe(
pqt,
width,
height,
imageScale,
scale,
totalPixels,
sourceData,
d
) {
const targetData = new ImageData(d.data.slice(), width);
for (let i = 0; i < totalPixels; i++) {
const val = (i * 256) / totalPixels;
const [x, y] = pqt.insert(val);
const j = (x + y * width) << 2;
const pixel = sourceData.data[j] < val ? 0 : 255;
targetData.data[j] = pixel;
targetData.data[j + 1] = pixel;
targetData.data[j + 2] = pixel;
targetData.data[j + 3] = 255;
}
return targetData;
}
PachinkoQuadTree = {
class PachinkoQuadTree {
constructor(depth, seed) {
this.depth = depth;
let size = 1;
this.offsets = [0];
for (let i = 1; i <= depth; i++) {
this.offsets[i] = size;
size += 4 ** i;
}
// What a node needs to store:
// - 4 bits to keep track of which direction previous
// insertions have fallen towards
// what a leaf needs to store:
// - 32 bits for index (supports a depth of 16, or
// textures up to 65535 × 65535)
// Easiest solution: two separate arrays.
// Note that we could try to be clever and pack two
// 4-bit values in a Uint8Array byte, but this code
// is probably tricky enough to follow as is.
this.pachinkoBitNodes = new Uint8Array(size);
this.valueLeaves = new Uint32Array(4 ** depth);
}
clear() {
this.pachinkoBitNodes.fill(0);
this.valueLeaves.fill(0);
}
idx(x, y, depth) {
return this.offsets[depth] + x + y * 2 ** depth;
}
getBits(x, y, depth) {
return this.pachinkoBitNodes[this.idx(x, y, depth)];
}
setBits(x, y, depth, bits) {
this.pachinkoBitNodes[this.idx(x, y, depth)] = bits;
}
pickChild(x, y, depth) {
const bits = this.getBits(x, y, depth);
// Note that we *branchlessly* pick a random child
const r = ((Math.random() * 12) | 0) * 2;
const picks = this.picks[bits];
const randomPick = (picks >> r) & 0b11;
// Convert the random pick to x and y offsets
const xn = randomPick & 1;
const yn = randomPick >> 1;
x = (x << 1) + xn;
y = (y << 1) + yn;
return [x, y];
}
// Note: does not update the tree! (because we want to
// be able to implement best-candidate approaches)
randomWalk() {
let xy = [0, 0];
let depth = 0;
for (let i = 0; i < this.depth; i++) {
xy = this.pickChild(xy[0], xy[1], depth++);
}
return xy;
}
// Once we have picked our final x,y coordinate, update
// the tree. We need to:
// - update our pachinko array so that every branch that
// was picked has its bitflag set
// - bubble up our x,y coordinate to the top unsaturated
// layer of our coordinateArray (for the sake of finding
// nearest neighbors faster in best-candidate search)
applyPick(x, y, index) {
this.valueLeaves[x + y * 2 ** this.depth] = index;
for (let i = 0; i < this.depth; i++) {
const xi = x >> (this.depth - i);
const yi = y >> (this.depth - i);
const idx = this.idx(xi, yi, i);
// x,y coordinates of picked child of the current node
const xn = x >> (this.depth - 1 - i);
const yn = y >> (this.depth - 1 - i);
// Set the appropriate bitflag in our pachinko array
const pick = 0b1000 >> ((xn & 1) + ((yn & 1) << 1));
const bits = this.pachinkoBitNodes[idx];
const updatedBits = bits | pick;
// if our pachinoArray is full we reset it,
// otherwise write back the updated flags
this.pachinkoBitNodes[idx] = updatedBits === 0b1111 ? 0 : updatedBits;
}
}
insert(val) {
const xy = this.randomWalk();
this.applyPick(xy[0], xy[1], val);
return xy;
}
}
// TODO: change the following to static propertites
// once Observable parser is updated to support it.
const TOP = 0,
BOTTOM = 2,
LEFT = 0,
RIGHT = 1,
TL = TOP + LEFT,
TR = TOP + RIGHT,
BL = BOTTOM + LEFT,
BR = BOTTOM + RIGHT;
// Twelve two-bit (x, y) picks packed into 16 bits in total.
// This way we can always have an unbiased pick of the
// remaining openings.
const packPicks = (...picks) => {
let out = 0;
for (const pick of picks) {
out = (out << 2) + pick;
}
console.log({ picks, out });
return out;
};
const picks = Uint32Array.from([
// outputs , // input flags (i.e. which branches were already picked?)
packPicks(TL, TL, TL, TR, TR, TR, BL, BL, BL, BR, BR, BR), // 0b0000 - none set
packPicks(TL, TL, TL, TL, TR, TR, TR, TR, BL, BL, BL, BL), // 0b0001 - bottom-right
packPicks(TL, TL, TL, TL, TR, TR, TR, TR, BR, BR, BR, BR), // 0b0010 - bottom-left
packPicks(TL, TL, TL, TL, TL, TL, TR, TR, TR, TR, TR, TR), // 0b0011 - bottom
packPicks(TL, TL, TL, TL, BL, BL, BL, BL, BR, BR, BR, BR), // 0b0100 - top-right
packPicks(TL, TL, TL, TL, TL, TL, BL, BL, BL, BL, BL, BL), // 0b0101 - right
packPicks(TL, TL, TL, TL, TL, TL, BR, BR, BR, BR, BR, BR), // 0b0110 - top-right, bottom-left
packPicks(TL, TL, TL, TL, TL, TL, TL, TL, TL, TL, TL, TL), // 0b0111 - everything except top-left
packPicks(TR, TR, TR, TR, BL, BL, BL, BL, BR, BR, BR, BR), // 0b1000 - top-left
packPicks(TR, TR, TR, TR, TR, TR, BL, BL, BL, BL, BL, BL), // 0b1001 - top-left, bottom-right
packPicks(TR, TR, TR, TR, TR, TR, BR, BR, BR, BR, BR, BR), // 0b1010 - left
packPicks(TR, TR, TR, TR, TR, TR, TR, TR, TR, TR, TR, TR), // 0b1011 - everything except top-right
packPicks(BL, BL, BL, BR, BR, BR, BL, BL, BL, BR, BR, BR), // 0b1100 - top
packPicks(BL, BL, BL, BL, BL, BL, BL, BL, BL, BL, BL, BL), // 0b1101 - everything except bottom-left
packPicks(BR, BR, BR, BR, BR, BR, BR, BR, BR, BR, BR, BR) // 0b1110 - everything except bottom-right
]);
Object.assign(PachinkoQuadTree.prototype, {
TOP,
BOTTOM,
LEFT,
RIGHT,
TL,
TR,
BL,
BR,
picks
});
return PachinkoQuadTree;
}
image = FileAttachment("ricardo-gomez-angel-9AdeEdYB2yk-unsplash.jpg").image({width: 64})
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.