2c:null 2d:["$","title",null,{"children":"Bridson’s Algorithm | Mike Bostock | Observable"}] 32:T878,function* poissonDiscSampler(width, height, radius) { const k = 30; // maximum number of samples before rejection 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 {add: sample(width / 2 + Math.random() * radius, height / 2 + Math.random() * radius, null)}; // 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 {add: sample(x, y), parent}; 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; yield {remove: parent}; } 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) { const s = grid[gridWidth * (y / cellSize | 0) + (x / cellSize | 0)] = [x, y]; queue.push(s); return s; } }33:[] 30:{"id":"b968ef8147786375","slug":"poisson-disc-distribution","title":"Bridson’s Algorithm","thumbnail":"203d269f640c679c49c325897f7b23a42d0fed149b781eb5db5e7ecf994057b9","access_level":"public","create_time":"$D2017-11-19T13:45:34.786Z","update_time":"$D2020-06-29T02:32:14.434Z","view_time":null,"first_public_time":"$D2017-11-19T14:44:03.973Z","has_unpublished_edits":null,"fork":false,"stars":36,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"pro_2026"},"version":260,"publish_version":260,"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":19,"collection":{"id":"b0b8183de839aa32","slug":"algorithms","title":"Algorithms","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"type":"notebook","body":{"titling":"auto","title":"Bridson’s Algorithm","cells":[{"id":1,"value":"md`# Bridson’s Algorithm\n\nThis algorithm efficiently generates [poisson-disc samples](https://dl.acm.org/citation.cfm?id=1278807).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":236,"value":"viewof replay = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"chart = {\n const height = 600;\n const svg = d3.create(\"svg\").attr(\"viewBox\", [0, 0, width, height]);\n \n replay;\n \n for (const event of poissonDiscSampler(width, height, 10)) {\n if (event.add) {\n event.parent && svg.insert(\"line\", \"circle\")\n .attr(\"x1\", event.parent[0])\n .attr(\"y1\", event.parent[1])\n .attr(\"x2\", event.add[0])\n .attr(\"y2\", event.add[1])\n .attr(\"stroke\", \"#999\");\n\n svg.append(\"circle\")\n .attr(\"id\", `point-${event.add.map(Math.round).join(\"-\")}`)\n .attr(\"r\", 0)\n .attr(\"cx\", event.add[0])\n .attr(\"cy\", event.add[1])\n .transition()\n .ease(d3.easeLinear)\n .attr(\"r\", 3)\n .transition()\n .attr(\"fill\", \"#f00\");\n } else if (event.remove) {\n svg.select(`#point-${event.remove.map(Math.round).join(\"-\")}`)\n .transition()\n .ease(d3.easeLinear)\n .attr(\"fill\", \"#999\")\n .attr(\"r\", 2);\n }\n \n yield svg.node();\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1"}} 31:"$30:body"