2a:null 2b:["$","title",null,{"children":"The Delaunay’s Dual | Mike Bostock | Observable"}] 30:T4a4,md`The [Voronoi diagram](https://en.wikipedia.org/wiki/Voronoi_diagram) shows the region of the plane that is closest to each given input point or *site*. Voronoi diagrams are beautiful (see [Raven Kwok](http://ravenkwok.com/skyline/), [Mario Klingemann](https://www.flickr.com/photos/quasimondo/8254540763/)), and occur frequently in nature. They are also useful in human-computer interaction, for example as an [overlay](https://bl.ocks.org/mbostock/8033015) to assist selection. [Fortune’s algorithm](https://en.wikipedia.org/wiki/Fortune’s_algorithm) is often used to construct the Voronoi diagram; however, it is much easier and faster to construct the Voronoi diagram if we already have the [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) of the same set of points! This approach is used in the new [d3-delaunay library](https://github.com/d3/d3-delaunay), which is based on the excellent [Delaunator](https://github.com/mapbox/delaunator) by [Vladimir Agafonkin](/@mourner) and recent [sweephull algorithms](https://github.com/mapbox/delaunator/blob/master/README.md#papers). Here’s how it works. First we compute the Delaunay triangulation.`31:T40e,{ replay2; const context = DOM.context2d(width, height); context.globalCompositeOperation = "darken"; context.beginPath(); delaunay.renderPoints(context); context.fillStyle = "black"; context.fill(); context.beginPath(); delaunay.render(context); context.strokeStyle = "lightgray"; context.stroke(); context.fillStyle = "red"; context.strokeStyle = "lightgray"; yield visibility(context.canvas); for (let i = 0, n = delaunay.triangles.length / 3; i < n; ++i) { let cx = voronoi.circumcenters[i * 2]; let cy = voronoi.circumcenters[i * 2 + 1]; let x0 = delaunay.points[delaunay.triangles[i * 3] * 2]; let y0 = delaunay.points[delaunay.triangles[i * 3] * 2 + 1]; let r = Math.sqrt((cx - x0) ** 2 + (cy - y0) ** 2); context.beginPath(); context.moveTo(cx + r, cy); context.arc(cx, cy, r, 0, 2 * Math.PI); context.stroke(); context.beginPath(); context.moveTo(cx + 2, cy); context.arc(cx, cy, 2, 0, 2 * Math.PI); context.fill(); yield context.canvas; } }32:T43a,{ replay3; const context = DOM.context2d(width, height); context.beginPath(); delaunay.render(context); context.strokeStyle = "lightgray"; context.stroke(); context.fillStyle = "red"; for (let i = 0, n = delaunay.triangles.length / 3; i < n; ++i) { let cx = voronoi.circumcenters[i * 2]; let cy = voronoi.circumcenters[i * 2 + 1]; context.beginPath(); context.moveTo(cx + 2, cy); context.arc(cx, cy, 2, 0, 2 * Math.PI); context.fill(); } context.beginPath(); delaunay.renderPoints(context); context.fillStyle = "black"; context.fill(); context.strokeStyle = "red"; yield visibility(context.canvas); for (let i = 0, n = delaunay.halfedges.length; i < n; ++i) { let j = delaunay.halfedges[i]; if (i < j) continue; let vi = Math.floor(i / 3) * 2; let vj = Math.floor(j / 3) * 2; context.beginPath(); context.moveTo(voronoi.circumcenters[vi], voronoi.circumcenters[vi + 1]); context.lineTo(voronoi.circumcenters[vj], voronoi.circumcenters[vj + 1]); context.stroke(); yield context.canvas; } }33:T5a9,{ replay4; const context = DOM.context2d(width, height); context.beginPath(); delaunay.render(context); context.strokeStyle = "lightgray"; context.stroke(); context.beginPath(); delaunay.renderPoints(context); context.fillStyle = "black"; context.fill(); context.strokeStyle = "red"; yield visibility(context.canvas); for (let i = 0, n = delaunay.halfedges.length; i < n; ++i) { let j = delaunay.halfedges[i]; if (i < j) continue; let vi = Math.floor(i / 3) * 2; let vj = Math.floor(j / 3) * 2; let xi = voronoi.circumcenters[vi]; let yi = voronoi.circumcenters[vi + 1]; let xj = voronoi.circumcenters[vj]; let yj = voronoi.circumcenters[vj + 1]; context.beginPath(); context.moveTo(xi, yi); context.lineTo(xj, yj); context.stroke(); } context.strokeStyle = "blue"; let node = delaunay.hull; do { const {x: x1, y: y1, t: i, next: {x: x2, y: y2, t: j}} = node; const ci = Math.floor(i / 3) * 2; const cx = voronoi.circumcenters[ci]; const cy = voronoi.circumcenters[ci + 1]; const dx = (x1 + x2) / 2 - cx; const dy = (y1 + y2) / 2 - cy; const k = ((x2 - x1) * (cy - y1) > (y2 - y1) * (cx - x1) ? -1 : 1) * 1e3 / Math.sqrt(dx ** 2 + dy ** 2); context.beginPath(); context.moveTo(cx, cy); context.lineTo(cx + k * dx, cy + k * dy); context.stroke(); yield context.canvas; } while ((node = node.next) !== delaunay.hull); }34:T872,function* poissonDiscSampler(x0, y0, x1, y1, radius) { const k = 30; // maximum number of samples before rejection const width = x1 - x0; const height = y1 - y0; const radius2 = radius * radius; const radius2_3 = 3 * radius2; const cellSize = radius * Math.SQRT1_2; const gridWidth = Math.ceil(width / cellSize); const gridHeight = Math.ceil(height / cellSize); const grid = new Array(gridWidth * gridHeight); const queue = []; // Pick the first sample. yield sample(width / 2 + Math.random() * radius, height / 2 + Math.random() * radius); // Pick a random existing sample from the queue. pick: while (queue.length) { const i = Math.random() * queue.length | 0; const parent = queue[i]; // Make a new candidate between [radius, 2 * radius] from the existing sample. for (let j = 0; j < k; ++j) { const a = 2 * Math.PI * Math.random(); const r = Math.sqrt(Math.random() * radius2_3 + radius2); const x = parent[0] + r * Math.cos(a); const y = parent[1] + r * Math.sin(a); // Accept candidates that are inside the allowed extent // and farther than 2 * radius to all existing samples. if (0 <= x && x < width && 0 <= y && y < height && far(x, y)) { yield sample(x, y); continue pick; } } // If none of k candidates were accepted, remove it from the queue. const r = queue.pop(); if (i < queue.length) queue[i] = r; } function far(x, y) { const i = x / cellSize | 0; const j = y / cellSize | 0; const i0 = Math.max(i - 2, 0); const j0 = Math.max(j - 2, 0); const i1 = Math.min(i + 3, gridWidth); const j1 = Math.min(j + 3, gridHeight); for (let j = j0; j < j1; ++j) { const o = j * gridWidth; for (let i = i0; i < i1; ++i) { const s = grid[o + i]; if (s) { const dx = s[0] - x; const dy = s[1] - y; if (dx * dx + dy * dy < radius2) return false; } } } return true; } function sample(x, y, parent) { queue.push(grid[gridWidth * (y / cellSize | 0) + (x / cellSize | 0)] = [x, y]); return [x + x0, y + y0]; } }35:[] 2e:{"id":"30f9b1b755c923f6","slug":"the-delaunays-dual","title":"The Delaunay’s Dual","thumbnail":null,"access_level":"public","create_time":"$D2018-03-21T19:22:42.146Z","update_time":"$D2021-04-23T21:53:55.873Z","view_time":null,"first_public_time":"$D2018-03-21T20:04:31.777Z","has_unpublished_edits":null,"fork":false,"stars":56,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"pro_2026"},"version":193,"publish_version":193,"role":null,"authored":false,"authors":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null}],"members":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":45,"collection":{"id":"b0b8183de839aa32","slug":"algorithms","title":"Algorithms","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"type":"notebook","body":{"titling":"auto","title":"The Delaunay’s Dual","cells":[{"id":0,"value":"md`# The Delaunay’s Dual`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"{\n const context = DOM.context2d(width, height);\n context.beginPath();\n delaunay.renderPoints(context);\n context.fill();\n context.beginPath();\n voronoi.render(context);\n context.stroke();\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"{\n replay1;\n const context = DOM.context2d(width, height);\n context.globalCompositeOperation = \"darken\";\n context.beginPath();\n delaunay.renderPoints(context);\n context.fillStyle = \"black\";\n context.fill();\n context.strokeStyle = \"lightgray\";\n yield visibility(context.canvas);\n for (let i = 0, n = delaunay.triangles.length / 3; i < n; ++i) {\n context.beginPath();\n delaunay.renderTriangle(i, context);\n context.stroke();\n yield context.canvas;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"viewof replay1 = html`