2d:null 2e:["$","title",null,{"children":"Delaunay Circumcenters | Mike Bostock | Observable"}] 33: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]; } }34:[] 31:{"id":"7949a1f59a7f63ce","slug":"delaunay-circumcenters","title":"Delaunay Circumcenters","thumbnail":"78a5b2033de23d150a06bea1dcf2c4737f56cad6330f25d4ff2bd8d6627eb3dc","access_level":"public","create_time":"$D2017-11-26T15:02:21.690Z","update_time":"$D2018-05-09T23:52:12.526Z","view_time":null,"first_public_time":"$D2017-11-26T17:47:23.730Z","fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"pro_2026"},"version":90,"publish_version":90,"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 Circumcenters","cells":[{"id":0,"value":"md`# Delaunay Circumcenters`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"{\n const dpi = window.devicePixelRatio || 1;\n const canvas = DOM.canvas(width * dpi, height * dpi);\n const context = canvas.getContext(\"2d\");\n canvas.style.width = `${width}px`;\n context.scale(dpi, dpi);\n for (let i = 0; i < triangles.length; i += 3) {\n\tconst [x1, y1] = points[triangles[i + 0]];\n\tconst [x2, y2] = points[triangles[i + 1]];\n\tconst [x3, y3] = points[triangles[i + 2]];\n\tcontext.beginPath();\n\tcontext.moveTo(x1, y1);\n\tcontext.lineTo(x2, y2);\n\tcontext.lineTo(x3, y3);\n\tcontext.closePath();\n\tcontext.strokeStyle = \"black\";\n\tcontext.stroke();\n\tconst [cx, cy] = circumcenters[i / 3];\n context.beginPath();\n context.moveTo(cx + 2, cy);\n context.arc(cx, cy, 2, 0, 2 * Math.PI);\n context.fillStyle = \"red\";\n context.fill();\n context.beginPath();\n context.moveTo(cx, cy), context.lineTo(x1, y1);\n context.moveTo(cx, cy), context.lineTo(x2, y2);\n context.moveTo(cx, cy), context.lineTo(x3, y3);\n context.strokeStyle = \"red\";\n context.stroke();\n\tyield canvas;\n }\n}","pinned":false,"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 = 40","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"points = [...poissonDiscSampler(-radius, -radius, width + radius, height + radius, radius)]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"triangles = new delaunator(points).triangles","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"circumcenters = {\n const circumcenters = new Array(triangles.length / 3);\n for (let i = 0; i < circumcenters.length; ++i) circumcenters[i] = circumcenter(i * 3);\n return circumcenters;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"function circumcenter(i) {\n const [x1, y1] = points[triangles[i + 0]];\n const [x2, y2] = points[triangles[i + 1]];\n const [x3, y3] = points[triangles[i + 2]];\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 const xa = (b2 * d3 - b3 * d2) / ab;\n const ya = (a3 * d2 - a2 * d3) / ab;\n return [xa, ya];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"delaunator = require(\"delaunator@1\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 32:"$31:body"