Plot: Voronoi labelsDelaunay edge coloringd3-delaunay@6 robustly releasedClip LloydSemi-square voronoiTP3: Power Diagram and Semi-Discrete Optimal TransportSpatial interpolation: Voronoi & Blur (code)Paths Delaunay hoverSelf-Organizing Maps meet DelaunayVoronoiMap2DPolygon 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
Delaunay sub-graphs
points = Array.from(pick2d(760, 460, N, distributionType), (d) =>
d.map((x) => x + 20)
)
render = (delaunay, subgraph) => {
const p = new path();
const { points, halfedges, triangles } = delaunay;
const accept = subgraph(delaunay);
for (let i = 0, n = triangles.length; i < n; ++i) {
const j = halfedges[i];
if (i < j) continue;
if (accept(i)) {
const a = triangles[i];
const b = triangles[i % 3 === 2 ? i - 2 : i + 1];
p.moveTo(points[2 * a], points[2 * a + 1]);
p.lineTo(points[2 * b], points[2 * b + 1]);
}
}
return "" + p;
}
delaunay = d3.Delaunay.from(points)
gabriel = (delaunay) => {
const { points, triangles } = delaunay;
return (i) => {
const a = triangles[i];
const b = triangles[i % 3 === 2 ? i - 2 : i + 1];
return [a, b].includes(
delaunay.find(
(points[2 * a] + points[2 * b]) / 2,
(points[2 * a + 1] + points[2 * b + 1]) / 2,
a
)
);
};
}
urquhart = (delaunay, score = euclidean2) => {
const { halfedges, points, triangles } = delaunay;
const n = triangles.length;
const removed = new Uint8Array(n);
for (let e = 0; e < n; e += 3) {
const p0 = triangles[e],
p1 = triangles[e + 1],
p2 = triangles[e + 2];
const p01 = score(points, p0, p1),
p12 = score(points, p1, p2),
p20 = score(points, p2, p0);
removed[
p20 > p01 && p20 > p12
? Math.max(e + 2, halfedges[e + 2])
: p12 > p01 && p12 > p20
? Math.max(e + 1, halfedges[e + 1])
: Math.max(e, halfedges[e])
] = 1;
}
return (i) => !removed[i];
}
hull = (delaunay) => {
const { hull, triangles } = delaunay;
const s = new Set(hull);
return (i) => {
const a = triangles[i];
if (!s.has(a)) return false;
const j = hull.indexOf(a);
const b = triangles[i % 3 === 2 ? i - 2 : i + 1];
return hull[(j + 1) % hull.length] === b;
};
}
mst = (delaunay, score = euclidean2) => {
const { points, triangles } = delaunay;
const set = new Uint8Array(points.length / 2);
const tree = new Set();
const heap = [];
const bisect = bisector(([v]) => -v).left;
function heap_insert(x, v) {
heap.splice(bisect(heap, -v), 0, [v, x]);
}
function heap_pop() {
return heap.length && heap.pop()[1];
}
// Initialize the heap with the outgoing edges of vertex zero.
set[0] = 1;
for (const i of delaunay.neighbors(0)) {
heap_insert([0, i], score(points, 0, i));
}
// For each remaining minimum edge in the heap…
let edge;
while ((edge = heap_pop())) {
const [i, j] = edge;
// If j is already connected, skip; otherwise add the new edge to point j.
if (set[j]) continue;
set[j] = 1;
tree.add(`${[i, j].sort()}`);
// Add each unconnected neighbor k of point j to the heap.
for (const k of delaunay.neighbors(j)) {
if (set[k]) continue;
heap_insert([j, k], score(points, j, k));
}
}
return (i) => {
const a = triangles[i];
const b = triangles[i % 3 === 2 ? i - 2 : i + 1];
return tree.has(`${[a, b].sort()}`);
};
}
complete = () => () => true
function euclidean2(points, i, j) {
return (
(points[i * 2] - points[j * 2]) ** 2 +
(points[i * 2 + 1] - points[j * 2 + 1]) ** 2
);
}
path = d3.path
bisector = d3.bisector
import { pick2d } from "@fil/2d-point-distributions"
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.
