Published
Edited
Jul 14, 2020
2 stars
Plot: Voronoi labelsDelaunay edge coloringDelaunay sub-graphsd3-delaunay@6 robustly releasedClip LloydSemi-square voronoiTP3: Power Diagram and Semi-Discrete Optimal TransportSpatial interpolation: Voronoi & Blur (code)Paths Delaunay hoverSelf-Organizing Maps meet DelaunayPolygon TriangulationHello, constrainautorThe Gray-Fuller spatial gridUnconnected Delaunay NeighborsLinde–Buzo–Gray stipplingLloyd’s relaxation on a graphManhattan Voronoi IIManhattan VoronoiGraph VoronoiWorld Cities UrquhartUK TricontoursGeo Voronoi interpolationSpherical contoursPetri dish bubblingd3-geo-voronoi and gridded dataDelaunay.findTriangleIris Voronoi 3The Voronoi projectionSouth Africa’s medial axisDirection to shoreDistance to shoret-SNE VoronoiMurphey Butterfly ProjectionAlpha shapes 3Alpha shapes 2So many countries’ VoronoisKruskal MazeOffscreen VoronoiGeo Mesh & fake pointsDrawing Voronoi with two.jsAlpha shapesSpherical VoronoiPerturbed Geodesic RainbowWorld Airports UrquhartSpherical Lloyds RelaxationAntarctica’s VoronoiWorld Airports VoronoiThe Urquhart graphGeo Delaunay
VoronoiMap2D
Also listed in…
Algorithms
{
const context = DOM.context2d(width, height, 1);
const isSite = new Uint8Array(width * height);
function draw() {
const timer = performance.now();
isSite.fill(0);
for (const [x, y] of sites) isSite[x + width * y] = 1;
const map = computeVoronoiMap(width, height, isSite);
const time = performance.now() - timer;
const data = context.getImageData(0, 0, width, height);
let rgb, prev;
for (let i = 0; i < map.length; i++) {
if (display) {
context.fillStyle =
i === map[i]
? "white"
: colorDistance(
Math.hypot(
(i % width) - (map[i] % width),
Math.floor(i / width) - Math.floor(map[i] / width)
)
);
} else {
context.fillStyle = i === map[i] ? "white" : color(map[i]);
}
if (context.fillStyle !== prev) {
prev = context.fillStyle;
rgb = d3.rgb(context.fillStyle);
data.data[4 * i + 0] = rgb.r;
data.data[4 * i + 1] = rgb.g;
data.data[4 * i + 2] = rgb.b;
} else {
data.data[4 * i + 0] = rgb.r;
data.data[4 * i + 1] = rgb.g;
data.data[4 * i + 2] = rgb.b;
}
data.data[4 * i + 3] = 255;
}
context.putImageData(data, 0, 0);
context.clearRect(0, 0, 150, 14);
context.fillStyle = "black";
context.fillText(time.toFixed(2) + "ms", 10, 10);
}
draw();
d3.select(context.canvas).on("click", function() {
sites.push(d3.mouse(this).map(Math.round));
draw();
});
return context.canvas;
}
sites = (reset,
Array.from({ length: 500 }, () => [
(Math.random() * width) | 0,
(Math.random() * height) | 0
]))
function computeVoronoiMap(w, h, isSite) {
const n = w * h,
voromap = new Int32Array(n),
infty = n + 1;
function index(x, y) {
return x + y * w;
}
function getX(pos) {
return pos % w;
}
function getY(pos) {
return Math.floor(pos / w);
}
// At point (x,y) which one between siteA and siteB is the closest?
function closest(x, y, siteA, siteB) {
const sAx = getX(siteA),
sAy = getY(siteA),
sBx = getX(siteB),
sBy = getY(siteB);
return (
(x - sAx) * (x - sAx) + (y - sAy) * (y - sAy) >
(x - sBx) * (x - sBx) + (y - sBy) * (y - sBy)
);
}
// On a vertical slab "slabX", do sites A and C hide the site B ?
// (if true, the cell of C does not intersect the slab)
function hiddenBy(A, B, C, slabX) {
const sAx = getX(A),
sAy = getY(A),
sBx = getX(B),
sBy = getY(B),
sCx = getX(C),
sCy = getY(C),
a = sBy - sAy,
b = sCy - sBy,
c = a + b,
dA = (sAx - slabX) * (sAx - slabX),
dB = (sBx - slabX) * (sBx - slabX),
dC = (sCx - slabX) * (sCx - slabX);
return c * dB - b * dA - a * dC - a * b * c > 0;
}
// First scan along the rows
// #pragma omp parallel for schedule(dynamic)
for (let y = 0; y < h; ++y) {
let prev = infty;
let firstSite = true;
for (let x = 0; x < w; ++x) {
voromap[index(x, y)] = Math.min(infty, index(prev, y));
if (isSite[index(x, y)]) {
const site = index(x, y);
voromap[index(x, y)] = site;
if (firstSite) {
firstSite = false;
for (let xx = 0; xx < x; ++xx) voromap[index(xx, y)] = site;
} // rewrite
else
for (let xx = Math.floor((prev + x) / 2) + 1; xx < x; ++xx)
voromap[index(xx, y)] = site;
prev = x;
}
}
}
// Second scan along the columns
// #pragma omp parallel for schedule(dynamic)
for (let x = 0; x < w; ++x) {
// Looking for the sites with non empty intersection between
// their voronoi cell and the vertical slab at "x"
var sites = [];
for (let y = 0; y < h; ++y)
if (voromap[index(x, y)] != infty) {
while (
sites.length >= 2 &&
hiddenBy(
sites[sites.length - 2],
sites[sites.length - 1],
voromap[index(x, y)],
x
)
)
sites.pop();
sites.push(voromap[index(x, y)]);
}
// Rewrite
let pos = 0;
if (sites.length == 1)
for (let y = 0; y < h; ++y) voromap[index(x, y)] = sites[0];
else
for (let y = 0; y < h; ++y) {
while (
pos < sites.length - 1 &&
closest(x, y, sites[pos], sites[pos + 1])
)
pos++;
voromap[index(x, y)] = sites[pos];
}
}
return voromap;
}
d3 = require("d3@5", "d3-delaunay@5")
color = d3.scaleOrdinal(d3.schemeCategory10)
colorDistance = d3.scaleSequential(d3.interpolateTurbo).domain([0, 200])
height = 500
import { checkbox } from "@jashkenas/inputs"
{
const timer = performance.now();
d3.Delaunay.from(sites).voronoi([0, 0, width, height]);
const time = performance.now() - timer;
return time;
}
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.
