2e:null 2f:["$","title",null,{"children":"2D point distributions | Fil | Observable"}] 34:Tb33,// Code by Jason Davies, Mike Bostock, Martin Roberts, and Jacob Rus // see https://observablehq.com/@fil/poisson-distribution-generators for details function* DiscSampler(width, height, radius) { const k = 13; // maximum number of samples before rejection const m = 4; // a number mutually prime to k const radius2 = radius * radius; const cellSize = 1 / (radius * Math.SQRT1_2); const gridWidth = Math.ceil(width * cellSize) + 4; // pad grid by 2 on each side const gridHeight = Math.ceil(height * cellSize) + 4; const grid = new Float64Array(2 * gridWidth * gridHeight).fill(Infinity); const queue = []; const rotx = Math.cos((2 * Math.PI * m) / k); const roty = Math.sin((2 * Math.PI * m) / k); // Pick the first sample. yield sample(0.1 * width * (4.5 + rng()), 0.1 * height * (4.5 + rng()), null); // Pick a random existing sample from the queue. pick: while (queue.length) { const i = (rng() * queue.length) | 0; const parent = queue[i]; const t = tanpi_2(2 * rng() - 1), q = 1 / (1 + t * t); const epsilon = 1e-6; let dw, dx, dy; dx = q ? (1 - t * t) * q : -1; // [dx, dy] = random unit vector dy = q ? 2 * t * q : 0; // Make a new candidate. for (let j = 0; j < k; ++j) { dw = dx * rotx - dy * roty; // temporary name for dx dy = dx * roty + dy * rotx; dx = dw; const rand0 = rng(); const rand1 = rng(); const r = (radius + epsilon) * (1 + 0.65 * rand0 * rand1); const x = parent[0] + r * dx; const y = parent[1] + r * dy; // 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; // yield {remove: parent}; } // fast approximation of tan(πx/2) function tanpi_2(a) { let b = 1 - a * a; return a * (-0.0187108 * b + 0.31583526 + 1.27365776 / b); } function far(x, y) { const j0 = (y * cellSize) | 0; const i0 = (x * cellSize) | 0; for (let j = j0; j < j0 + 5; ++j) { const index0 = 2 * (j * gridWidth + i0); for (let i = index0; i < index0 + 10; i += 2) { const dx = grid[i] - x; const dy = grid[i + 1] - y; if (dx * dx + dy * dy < radius2) return false; } } return true; } function sample(x, y, parent) { const s = [x, y]; // offset grid cell by 2 in each direction to account for border const i = (x * cellSize + 2) | 0; const j = (y * cellSize + 2) | 0; const index = 2 * (gridWidth * j + i); grid[index] = x; grid[index + 1] = y; queue.push(s); return s; } }35:[] 32:{"id":"5b808e36e78ae77c","slug":"2d-point-distributions","title":"2D point distributions","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2019-10-07T10:45:53.601Z","update_time":"$D2026-06-12T13:46:56.262Z","view_time":null,"first_public_time":"$D2019-10-07T11:49:49.190Z","has_unpublished_edits":null,"fork":false,"stars":22,"starred":false,"owner":{"type":"team","id":"da2a32154638c457","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":"starter_2024"},"version":527,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}],"members":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":4,"collection":{"id":"7f51a09dd1333537","slug":"algorithms","title":"Algorithms","owner":{"id":"da2a32154638c457","login":"fil","name":"Fil"}},"type":"notebook","body":{"title":"2D point distributions","cells":[{"id":58,"value":"md`# 2D point distributions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"## Pick API\n\npick2d returns about _N_ points in the rectangle _width_ × _height_ with the distribution of _type_ = [_random_](#Random), [_poissonDisc_](#PoissonDisc), [_blue_](#_blue), [_pseudoblue_](#pseudob), [*grid*](#Grid), [_hexgrid_](#Hexgrid) or [_normal_](#Normal):\n\n~~~{javascript}\nimport { pick2d } from \"@fil/2d-point-distributions\"\npick2d(width, height, N, type);\n~~~\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":72,"value":"N = 4000","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"pick2d(width, height, N, \"random\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"Random = md`## Random\n\nIndependent draws of a random uniform x and a random uniform y.\n\nUsage:\n~~~{javascript}\nimport { random2d } from \"@fil/2d-point-distributions\"\nrandom2d(width, height, N);\n~~~\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":105,"value":"{\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n let i = 0;\n const radius = Math.sqrt((0.63 * (width * height)) / N);\n for (const p of random2d(width, height, N)) {\n context.beginPath();\n context.arc(p[0], p[1], radius / 2, 0, 2 * Math.PI);\n context.stroke();\n if (i++ % 20 === 0) yield context.canvas;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"random2d(width, height, N)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"function random2d(width, height, N) {\n const points = [];\n for (let i = 0; i < N; i++) points.push([width * rng(), height * rng()]);\n return points;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"PoissonDisc = md`## Poisson-disc sampling\n\nSee https://observablehq.com/@fil/poisson-distribution-generators\n\nUsage:\n~~~{javascript}\nimport { DiscSampler } from \"@fil/2d-point-distributions\"\n[...DiscSampler(width, height, radius)];\n~~~\nor\n~~~{javascript}\nimport { poissonDisc2d } from \"@fil/2d-point-distributions\"\npoissonDisc2d(width, height, N);\n~~~\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"{\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n let i = 0;\n const radius = Math.sqrt((0.63 * (width * height)) / N);\n for (const p of poissonDisc2d(width, height, N)) {\n context.beginPath();\n context.arc(p[0], p[1], radius / 2, 0, 2 * Math.PI);\n context.stroke();\n if (i++ % 20 === 0) yield context.canvas;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"function poissonDisc2d(width, height, N) {\n const radius = Math.sqrt((0.63 * (width * height)) / N);\n return DiscSampler(width, height, radius);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":355,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":444,"value":"// keep for ascending compatibility\nfunction poissonDiscSampler(width, height, radius) {\n return Array.from(poissonDisc2d(width, height, N));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":151,"value":"Hexgrid = md`## Hexgrid\n\nUsage:\n~~~{javascript}\nimport { hexgrid2d } from \"@fil/2d-point-distributions\"\nhexgrid2d(width, height, N);\n~~~\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"{\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n let i = 0;\n const radius = Math.sqrt((width * height) / N / 2.5);\n for (const p of hexgrid2d(width, height, N)) {\n context.beginPath();\n context.arc(p[0], p[1], radius / 2, 0, 2 * Math.PI);\n context.stroke();\n if (i++ % 20 === 0) yield context.canvas;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":154,"value":"function hexgrid2d(width, height, N) {\n const h = Math.sqrt((width * height * (Math.sqrt(5) / 2)) / N),\n v = h * (2 / Math.sqrt(5)),\n a = [];\n for (let i = 0; i < width / h; i++)\n for (let j = 0.5; j < height / v; j++)\n a.push([(i - (j % 2) / 2) * h, j * v]);\n return a;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":501,"value":"## Blue noise","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"_blue","database":"$undefined"},{"id":499,"value":"{\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n let i = 0;\n const radius = Math.sqrt((0.3 * (width * height)) / N);\n for (const p of blue2d(width, height, N)) {\n context.beginPath();\n context.arc(p[0], p[1], radius / 2, 0, 2 * Math.PI);\n context.stroke();\n if (i++ % 20 === 0) yield context.canvas;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":449,"value":"## Pseudo-blue noise","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"pseudob","database":"$undefined"},{"id":451,"value":"{\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n let i = 0;\n const radius = Math.sqrt((0.3 * (width * height)) / N);\n for (const p of pseudoblue2d(width, height, N)) {\n context.beginPath();\n context.arc(p[0], p[1], radius / 2, 0, 2 * Math.PI);\n context.stroke();\n if (i++ % 20 === 0) yield context.canvas;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":457,"value":"function pseudoblue2d(width, height, N) {\n const a = [];\n const r = N / (width * height);\n for (let i = 0; i < width; i++)\n for (let j = 0.5; j < height; j++) if (pseudoblue(i, j) < r) a.push([i, j]);\n return a;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":505,"value":"function blue2d(width, height, N) {\n const a = [];\n const r = N / (width * height);\n for (let i = 0; i < width; i++)\n for (let j = 0.5; j < height; j++) if (blue(i, j) < r) a.push([i, j]);\n return a;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":455,"value":"import { sorted_1024 as blue, pseudoblue } from \"@fil/blue\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":180,"value":"Grid = md`## Square grid\n\nUsage:\n~~~{javascript}\nimport { grid2d } from \"@fil/2d-point-distributions\"\ngrid2d(width, height, N);\n~~~\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":185,"value":"{\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n let i = 0;\n const radius = Math.sqrt((width * height) / N / 2.5);\n for (const p of grid2d(width, height, N)) {\n context.beginPath();\n context.arc(p[0], p[1], radius / 2, 0, 2 * Math.PI);\n context.stroke();\n if (i++ % 20 === 0) yield context.canvas;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":183,"value":"function grid2d(width, height, N) {\n const radius = Math.sqrt((width * height) / N);\n const points = [];\n for (let i = 0; i < width / radius; i++)\n for (let j = 0; j < height / radius; j++)\n points.push([i * radius, j * radius]);\n return points;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":224,"value":"Normal = md`## Normal\n\nUsage:\n~~~{javascript}\nimport { normal2d } from \"@fil/2d-point-distributions\"\nnormal2d(width, height, N);\n~~~\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":230,"value":"{\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n let i = 0;\n const radius = Math.sqrt((width * height) / N / 2.5);\n for (const p of normal2d(width, height, N)) {\n context.beginPath();\n context.arc(p[0], p[1], radius / 2, 0, 2 * Math.PI);\n context.stroke();\n if (i++ % 20 === 0) yield context.canvas;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"function normal2d(width, height, N) {\n const random = d3.randomNormal(0, Math.min(width, height) / 6);\n const points = [];\n for (let i = 0; i < N; i++)\n points.push([width / 2 + random(), height / 2 + random()]);\n return points;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":138,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":117,"value":"function pick2d(width, height, N, type) {\n switch (type) {\n case \"poisson\":\n case \"poissonDisc\":\n return poissonDisc2d(width, height, N);\n case \"pseudoblue\":\n return pseudoblue2d(width, height, N);\n case \"hex\":\n case \"hexagons\":\n case \"hexgrid\":\n return hexgrid2d(width, height, N);\n case \"square\":\n case \"grid\":\n return grid2d(width, height, N);\n case \"normal\":\n return normal2d(width, height, N);\n case \"random\":\n case \"uniform\":\n default:\n return random2d(width, height, N);\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"rng = Math.random","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"height = 500","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":247,"value":"// adapt this code for your application\nviewof distributionType = Inputs.select([\n \"poisson\",\n \"pseudoblue\",\n \"hex\",\n \"grid\",\n \"random\",\n \"normal\"\n])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":250,"value":"pick2d(width, height, N, distributionType)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"d3 = import(\"d3-random@3\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":441,"value":"Note that Jacob has also published a [spherical version](https://observablehq.com/@jrus/spheredisksample).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 33:"$32:body"