2d:null 2e:["$","title",null,{"children":"Delaunay Voronoi | Mike Bostock | Observable"}] 33:T7b3,class Cell { constructor() { this._S = []; this._vx0 = 0; this._vy0 = 0; this._vx1 = 0; this._vy1 = 0; } connect(i, j) { let S = this._S; for (let n = S.length, a = 0; a < n; ++a) { let sa = S[a]; if (sa[0] === j) { for (let b = a + 1; b < n; ++b) { let sb = S[b]; if (sb[sb.length - 1] === i) { S.splice(b, 1); S[a] = sa = sb.concat(sa); return; } } sa.unshift(i); return; } if (sa[sa.length - 1] === i) { for (let b = a + 1; b < n; ++b) { let sb = S[b]; if (sb[0] === j) { S.splice(b, 1); S[a] = sa = sa.concat(sb); return; } } sa.push(j); return; } } S.push([i, j]); } extendStart(x, y) { this._vx0 = x; this._vy0 = y; } extendEnd(x, y) { this._vx1 = x; this._vy1 = y; } path(context) { let s = this._S[0]; if (!s) return; // Coincident point. if (s[0] === s[s.length - 1]) { const cx0 = circumcenters[s[0] * 2 + 0]; const cy0 = circumcenters[s[0] * 2 + 1]; context.moveTo(cx0, cy0); for (let i = 1; i < s.length; ++i) { const cx1 = circumcenters[s[i] * 2 + 0]; const cy1 = circumcenters[s[i] * 2 + 1]; context.lineTo(cx1, cy1); } } else { const l0 = 1e3 / Math.sqrt(this._vx0 ** 2 + this._vy0 ** 2); // TODO Clip infinite edge. const l1 = 1e3 / Math.sqrt(this._vx1 ** 2 + this._vy1 ** 2); // TODO Clip infinite edge. let cx = circumcenters[s[0] * 2 + 0]; let cy = circumcenters[s[0] * 2 + 1]; context.moveTo(cx + l0 * this._vx0, cy + l0 * this._vy0); for (const i of s) { cx = circumcenters[i * 2 + 0]; cy = circumcenters[i * 2 + 1]; context.lineTo(cx, cy); } context.lineTo(cx + l1 * this._vx1, cy + l1 * this._vy1); } } }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:[] 31:{"id":"2039b4f20e4f9724","slug":"delaunay-voronoi","title":"Delaunay Voronoi","thumbnail":"b1ce29410b99092098f62d6cabd115ff5e74bdc7f23439155c4ab43c154e9dbc","access_level":"public","create_time":"$D2017-11-26T23:12:57.660Z","update_time":"$D2018-05-09T23:52:28.864Z","view_time":null,"first_public_time":"$D2017-11-26T23:21:10.499Z","fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"pro_2026"},"version":421,"publish_version":421,"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":0,"collection":null,"type":"notebook","body":{"title":"Delaunay Voronoi","cells":[{"id":0,"value":"md`# Delaunay Voronoi`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"{\n const context = DOM.context2d(width, height);\n const canvas = context.canvas; \n context.beginPath();\n for (const [x, y] of points) {\n context.moveTo(x + 2, y);\n context.arc(x, y, 2, 0, 2 * Math.PI);\n }\n context.fill();\n for (const cell of cells) {\n context.beginPath();\n cell.path(context);\n context.fillStyle = cell._vx0 || cell.vy0 ? \"rgba(0,0,255,0.05)\" : \"rgba(255,0,0,0.05)\";\n context.fill();\n context.strokeStyle = cell._vx0 || cell.vy0 ? \"blue\" : \"red\";\n context.stroke();\n }\n return canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":406,"value":"md`First we compute the Delaunay triangulation of the points.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"delaunay = new delaunator(points)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":408,"value":"md`Next we compute the circumcenters of the Delaunay triangles.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"circumcenters = {\n const {coords, triangles, trianglesLen} = delaunay;\n const circumcenters = new Float64Array(trianglesLen / 3 * 2);\n for (let i = 0, j = 0, n = trianglesLen; i < n; i += 3, j += 2) {\n const x1 = coords[triangles[i + 0] * 2 + 0];\n const y1 = coords[triangles[i + 0] * 2 + 1];\n const x2 = coords[triangles[i + 1] * 2 + 0];\n const y2 = coords[triangles[i + 1] * 2 + 1];\n const x3 = coords[triangles[i + 2] * 2 + 0];\n const y3 = coords[triangles[i + 2] * 2 + 1];\n const a2 = x1 - x2;\n const a3 = x1 - x3;\n const b2 = y1 - y2;\n const b3 = y1 - y3;\n const d1 = x1 * x1 + y1 * y1;\n const d2 = d1 - x2 * x2 - y2 * y2;\n const d3 = d1 - x3 * x3 - y3 * y3;\n const ab = (a3 * b2 - a2 * b3) * 2;\n circumcenters[j + 0] = (b2 * d3 - b3 * d2) / ab;\n circumcenters[j + 1] = (a3 * d2 - a2 * d3) / ab;\n }\n return circumcenters;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":410,"value":"md`Next we connect the circumcenters of adjacent triangles.\n\nTriangles on the hull (exterior) have no adjacent triangles. These triangles correspond to the infinite edges of Voronoi cells, which we represent as vectors extending from the normal (finite) edges.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":202,"value":"cells = {\n const {coords, halfedges, triangles, hull} = delaunay;\n\n const cells = new Array(coords.length / 2);\n for (let i = 0, n = cells.length; i < n; ++i) {\n cells[i] = new Cell;\n }\n\n for (let i = 0, m = halfedges.length; i < m; ++i) {\n const j = halfedges[i];\n if (j < 0) continue;\n cells[triangles[i]].connect(Math.floor(i / 3), Math.floor(j / 3));\n }\n\n {\n let node = hull;\n do {\n const {x: x1, y: y1, t: i, next: {x: x2, y: y2, t: j}} = node;\n const cx = circumcenters[Math.floor(i / 3) * 2 + 0];\n const cy = circumcenters[Math.floor(i / 3) * 2 + 1];\n const dx = (x1 + x2) / 2 - cx;\n const dy = (y1 + y2) / 2 - cy;\n const k = (x2 - x1) * (cy - y1) > (y2 - y1) * (cx - x1) ? -1 : 1;\n cells[triangles[i]].extendEnd(k * dx, k * dy);\n cells[triangles[j]].extendStart(k * dx, k * dy);\n } while ((node = node.next) !== hull);\n }\n\n return cells;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":196,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"radius = 12","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"points = [...poissonDiscSampler(width / 8, height / 8, width * 7 / 8, height * 7 / 8, radius)]\n// points = (await fetch(\"https://gist.githubusercontent.com/mbostock/5597ed942ce2fa2b6ba5eb5e24355ad8/raw/31b4a7aacc3d6b97829de009f79e7d6cef616c7a/points.json\")).json()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"delaunator = require(\"delaunator@1\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"