Skip to content

Instantly share code, notes, and snippets.

@alenthomas
Last active November 9, 2020 10:47
Show Gist options
  • Save alenthomas/c61e1fa8cf6a3ba6bdb4bd3fe71f1bb2 to your computer and use it in GitHub Desktop.
Save alenthomas/c61e1fa8cf6a3ba6bdb4bd3fe71f1bb2 to your computer and use it in GitHub Desktop.
delaunay point calculation
const calculateDelaunayPoints = (data, width, height, n) => {
// Initialize the variables
const pointsInput = new Float64Array(n * 2);
const centroid = new Float64Array(n * 2);
const stippling = new Float64Array(n);
// Initialize the pointsInput using rejection sampling.
for (let i = 0; i < n; ++i) {
for (let j = 0; j < 30; ++j) {
const x = pointsInput[i * 2] = Math.floor(Math.random() * width);
const y = pointsInput[i * 2 + 1] = Math.floor(Math.random() * height);
if (Math.random() < data[y * width + x])
break;
}
}
const delaunayPoints = new d3.Delaunay(pointsInput);
for (let k = 0; k < 80; ++k) {
// Compute the weighted centroid for each Voronoi cell.
centroid.fill(0);
stippling.fill(0);
for (let y = 0, i = 0; y < height; ++y) {
for (let x = 0; x < width; ++x) {
const w = data[y * width + x];
i = delaunayPoints.find(x + 0.5, y + 0.5, i);
stippling[i] += w;
centroid[i * 2] += w * (x + 0.5);
centroid[i * 2 + 1] += w * (y + 0.5);
}
}
// Relax the diagram by moving pointsInput to the weighted centroid.
// Wiggle the pointsInput a little bit so they don't get stuck.
const w = Math.pow(k + 1, -0.8) * 10;
for (let i = 0; i < n; ++i) {
const x0 = pointsInput[i * 2];
const y0 = pointsInput[i * 2 + 1];
const x1 = stippling[i] ? centroid[i * 2] / stippling[i] : x0,
const y1 = stippling[i] ? centroid[i * 2 + 1] / stippling[i] : y0;
pointsInput[i * 2] = x0 + (x1 - x0) * 1.8 + (Math.random() - 0.5) * w;
pointsInput[i * 2 + 1] = y0 + (y1 - y0) * 1.8 + (Math.random() - 0.5) * w;
}
return pointsInput;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment