Example things I like: geometry, trippy geometry, recursion, maps. 👌
Published
Edited
Feb 20, 2021
11 stars
class LookupGrid {
constructor(points, neighborhoodRadius) {
this.r = neighborhoodRadius;
this.rDouble = 2 * neighborhoodRadius;
this.tree = d3.group(
points,
d => this.computeKey(d.x - this.r),
d => this.computeKey(d.y - this.r),
)
}
getPointsInAdjacentCells(point) {
const xa = this.computeKey(point.x);
const ya = this.computeKey(point.y);
const xb = xa - 1;
const yb = ya - 1;
// Get the points in all four grid cells around the
// grid line crossing closest to the point.
return [
this.getPointsInCell(xa, ya),
this.getPointsInCell(xa, yb),
this.getPointsInCell(xb, yb),
this.getPointsInCell(xb, ya),
].flat()
}
getNeighbors(point, measureDistance = (dx, dy) => dx*dx + dy*dy) {
const maxDistance = measureDistance(this.r, 0);
return this.getPointsInAdjacentCells(point)
// I considered using an intermediate filtering step here that removes
// all points outside the bounding box with radius r around point,
// but opted to just do the distance calculation right away. Two multiplications
// and one addition for the squared distance shouldn't be too bad...
.filter(({x, y}) => measureDistance(x - point.x, y - point.y) <= maxDistance)
}
// Using another distance measure is easy, but bear in mind the extents of the grid cells
getManhattanNeighbors(point) {
return this.getNeighbors(point, (dx, dy) => Math.abs(dx) + Math.abs(dy));
}
getPointsInCell(xKey, yKey) {
return this.tree.get(xKey)?.get(yKey) ?? [];
}
computeKey(coordinate) {
return Math.round(coordinate / this.rDouble);
}
}
// Generate some high dimensional points
highDimPoints = createPoints(10, 4, () => Math.floor(Math.random() * 10))
// Explore this example instance!
highDimLookupGrid = new LookupGridRn(highDimPoints, 10)
// Using euclidean distance
highDimLookupGrid.getNeighbors(highDimPoints[0])
// Using the included other example distance measure, Manhattan distance
highDimLookupGrid.getManhattanNeighbors(highDimPoints[0])
// Another exotic distance measure
new LookupGridRn(highDimPoints, 4).getNeighbors(highDimPoints[0], point =>
Math.max(...point)
)
class LookupGridRn {
// With points expressed as an array of their coordinates, we can extend to work in any dimensional space
constructor(points, neighborhoodRadius) {
this.r = neighborhoodRadius;
this.rDouble = 2 * neighborhoodRadius;
this.nDims = points[0]?.length ?? 0;
const keyExtractors = Array.from(
{ length: this.nDims },
(_,iDim) => point => this.computeKey(point[iDim] - this.r)
);
this.tree = d3.group(
points,
...keyExtractors
)
}
getPointsInAdjacentCells(point) {
const keys = this.computeKeys(point);
const powers = keys.map((x, i) => Math.pow(2, i)).reverse();
// The keys for adjacent cells are produced by subtracting 1 from some coordinates.
// The specific coordinates to modify to get cell n are those with ones
// in row n of a boolean truth table with nDims variables.
const adjacentKeySets = Array.from(
{ length: Math.pow(2, this.nDims) },
() => keys.slice()
).map((arr, i) => arr.map((x, j) => x - (Math.floor(i / powers[j]) % 2)))
return adjacentKeySets.map(this.getPointsInCell, this).flat();
}
getNeighbors(point, norm = point => Math.hypot(...point)) {
const pointOnRadius = Array.from(
{length: this.nDims},
(_, i) => i === 0 ? this.r : 0
);
const maxNorm = norm(pointOnRadius);
return this.getPointsInAdjacentCells(point)
.filter(candidate => norm(candidate.map((coordinate, i) => coordinate - point[i])) <= maxNorm)
}
// Using another distance measure is easy, but bear in mind the extents of the grid cells
getManhattanNeighbors(point) {
return this.getNeighbors(point, point => point.reduce((s, x) => s + Math.abs(x), 0));
}
getPointsInCell(keys) {
let subtree = this.tree;
let i = 0;
while (subtree && i < keys.length) {
const key = keys[i++];
subtree = subtree.get(key);
}
return subtree instanceof Array
? subtree
: [];
}
computeKeys(point) {
return point.map(coordinate => this.computeKey(coordinate));
}
computeKey(coordinate) {
return Math.round(coordinate / this.rDouble);
}
}
import { Range } from "@observablehq/inputs"
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.
