31:T5d4,render(function* () { const [W, H] = dimensions; const N = generators.length; const res = Array(N).fill(0); let nd = 0; // initialization const V = Array(H); for (let j = 0; j < H; j++) V[j] = Array(W); const setCell = function ({ x: x0, y: y0, value }, dx, dy) { const [x, y] = [x0 + dx, y0 + dy]; if (x < 0 || x >= W || y < 0 || y >= H) return 0; if (V[y][x] != undefined) return 0; V[y][x] = value; return 1; }; let n = N; let r = 0; // As long as there are active generators while (n > 0) { r++; let x = r - 1; let y = 0; let dx = 1; let dy = 1; let err = dx - (r << 1); while (x >= y) { for (let i = 0; i < N; i++) { if (res[i] != -1) { const gen = generators[i]; res[i] += setCell(gen, +x, +y) + setCell(gen, +y, +x) + setCell(gen, -y, +x) + setCell(gen, -x, +y) + setCell(gen, -x, -y) + setCell(gen, -y, -x) + setCell(gen, +y, -x) + setCell(gen, +x, -y); } } if (err <= 0) { y++; err += dy; dy += 2; } if (err > 0) { x--; dx += 2; err += dx - (r << 1); } } // Count remaining active generators and reset them n = 0; for (let i = 0; i < N; i++) { if (res[i] > 0) { n++; res[i] = 0; } else { res[i] = -1; } } yield V; } })32:T619,render(function* () { const [W, H] = dimensions; const N = generators.length; const res = Array(N).fill(0); let nd = 0; // initialization const V = Array(H); for (let j = 0; j < H; j++) V[j] = Array(W); for (const { x, y, value } of generators) V[y][x] = value; const setCell = function ({ x: x0, y: y0, value }, dx, dy) { const [x, y] = [x0 + dx, y0 + dy]; if (x < 0 || x >= W || y < 0 || y >= H) return 0; if (V[y][x] != undefined) return 0; V[y][x] = value; return 1; }; let n = N; let r = 0; // As long as there are active generators while (n > 0) { r++; let x = 0; let y = r; let d = r - 1; while (y >= x) { for (let i = 0; i < N; i++) { if (res[i] != -1) { const gen = generators[i]; res[i] += setCell(gen, +x, +y) + setCell(gen, +y, +x) + setCell(gen, -y, +x) + setCell(gen, -x, +y) + setCell(gen, -x, -y) + setCell(gen, -y, -x) + setCell(gen, +y, -x) + setCell(gen, +x, -y); } } if (d >= 2 * x) { d = d - 2 * x - 1; x++; } else if (d < 2 * (r - y)) { d = d + 2 * y - 1; y--; } else { d = d + 2 * (y - x - 1); y--; x++; } } // Count remaining active generators and reset them n = 0; for (let i = 0; i < N; i++) { if (res[i] > 0) { n++; res[i] = 0; } else { res[i] = -1; } } yield V; } })33:T639,render(function* () { const [W, H] = dimensions; const N = generators.length; const D = Array(H); const V = Array(H); for (let j = 0; j < H; j++) { D[j] = Array(W); V[j] = Array(W); for (let i = 0; i < W; i++) D[j][i] = +Infinity; } for (const { x, y, value } of generators) { V[y][x] = value; D[y][x] = 0; } const res = Array(N).fill(0); const setCell = function ({ x: x0, y: y0, value }, dx, dy, d2) { const [x, y] = [x0 + dx, y0 + dy]; if (x < 0 || x >= W || y < 0 || y >= H) return 0; if (V[y][x] == undefined || d2 < D[y][x]) { V[y][x] = value; D[y][x] = d2; return 1; } else { return 0; } }; let n = N; let r = 0; let nd = 0; // As long as there are active generators while (n > 0) { r++; let x = 0; let y = r; while (y >= x) { const d2 = x * x + y * y; nd++; for (let i = 0; i < N; i++) { if (res[i] != -1) { const gen = generators[i]; res[i] += setCell(gen, x, y, d2) + setCell(gen, x, -y, d2) + setCell(gen, y, x, d2) + setCell(gen, y, -x, d2) + setCell(gen, -x, y, d2) + setCell(gen, -x, -y, d2) + setCell(gen, -y, -x, d2) + setCell(gen, -y, x, d2); } } x++; y--; } // Count remaining active generators and reset them n = 0; for (let i = 0; i < N; i++) { if (res[i] > 0) { n++; res[i] = 0; } else { res[i] = -1; } } yield V; } })34:T611,render(function* () { const [W, H] = dimensions; const N = generators.length; const D = Array(H); const V = Array(H); for (let j = 0; j < H; j++) { D[j] = Array(W); V[j] = Array(W); for (let i = 0; i < W; i++) D[j][i] = +Infinity; } for (const { x, y, value } of generators) { V[y][x] = value; D[y][x] = 0; } const res = Array(N).fill(0); const setCell = function ({ x: x0, y: y0, value }, dx, dy, d2) { const [x, y] = [x0 + dx, y0 + dy]; if (x < 0 || x >= W || y < 0 || y >= H) return 0; if (V[y][x] == undefined || d2 < D[y][x]) { V[y][x] = value; D[y][x] = d2; return 1; } else { return 0; } }; let n = N; let r = 0; let nd = 0; // As long as there are active generators while (n > 0) { r++; let x = 0; let y = r; while (y >= x) { nd++; for (let i = 0; i < N; i++) { if (res[i] != -1) { const gen = generators[i]; res[i] += setCell(gen, x, y, r) + setCell(gen, x, -y, r) + setCell(gen, y, x, r) + setCell(gen, y, -x, r) + setCell(gen, -x, y, r) + setCell(gen, -x, -y, r) + setCell(gen, -y, -x, r) + setCell(gen, -y, x, r); } } x++; y--; } // Count remaining active generators and reset them n = 0; for (let i = 0; i < N; i++) { if (res[i] > 0) { n++; res[i] = 0; } else { res[i] = -1; } } yield V; } })35:[] 2f:{"title":"Discrete Voronoi diagrams generation strategies","cells":[{"id":0,"value":"md`# Discrete Voronoi diagrams generation strategies`","pinned":false,"hidden":false,"mode":"ojs"},{"id":203,"value":"md`[Voronoi diagrams](https://en.wikipedia.org/wiki/Voronoi_diagram) are elegant, and incredibly useful. There are [optimized methods](https://en.wikipedia.org/wiki/Fortune%27s_algorithm) to construct them as a list of vertices and edges, but here I will compare *discrete* Voronoi diagrams computation methods: algorithms that directly *approximate* a formal Voronoi tessellation on a 2D array, storing in each cell the nearest generator.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":60,"value":"dimensions = [width, 300]","pinned":false,"hidden":false,"mode":"ojs"},{"id":62,"value":"nbGenerators = 500","pinned":false,"hidden":false,"mode":"ojs"},{"id":485,"value":"md`Pseudo relaxation simulates [Voronoi relaxation](https://en.wikipedia.org/wiki/Lloyd%27s_algorithm) by choosing generators as a regular grid of points, then slightly displacing each of the points. When the option is selected, the actual number of generators will probably be inferior to the *nbGenerators* value`","pinned":false,"hidden":false,"mode":"ojs"},{"id":469,"value":"viewof pseudoRelaxed = checkbox({ options: [{ label: \"pseudo relaxed\" }] })","pinned":false,"hidden":false,"mode":"ojs"},{"id":558,"value":"gens = ([W, H], nb) => {\n const rand = max => (max * Math.random()) | 0;\n return array(nb, i => ({ x: rand(W), y: rand(H), value: i }));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":524,"value":"pseudoGens = ([W, H], nb) => {\n const d = Math.sqrt((W * H) / nb);\n const [Nw, Nh] = [Math.floor(W / d), Math.floor(H / d)];\n const [f1, f2] = [0.4, Math.min(W / Nw, H / Nh)];\n const rlx = index => ((index + 0.5 + (Math.random() * 2 - 1) * f1) * f2) | 0;\n const rand = max => (max * Math.random()) | 0;\n const gen = (i, j) => ({ x: rlx(i), y: rlx(j), value: rand(nbGenerators) });\n return array(Nw, i => array(Nh, j => gen(i, j))).flat();\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":56,"value":"generators = (pseudoRelaxed ? pseudoGens : gens)(dimensions, nbGenerators)","pinned":true,"hidden":false,"mode":"ojs"},{"id":74,"value":"colors = d3\n .quantize(d3.interpolateHcl(\"#fafa6e\", \"#2A4858\"), nbGenerators)\n .map(d3.color)\n .map(({ r, g, b }) => [r, g, b])","pinned":false,"hidden":false,"mode":"ojs"},{"id":386,"value":"md`Below are different approaches to the problem, each one demoed based on the same set of generators. Clicking on a canvas restart the corresponding algorithm.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":208,"value":"md`The simple naive algorithm compares for each cell the distance to every generator and keeps the smallest. This represents ${tex`width \\times height \\times nb_{generators}`} distance computations and comparisons, which can be quite significative (${dimensions[0]*dimensions[1]*nbGenerators} with this notebook's current parameters).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":676,"value":"render(function*() {\n const [W, H] = dimensions;\n const V = array(H, j => Array(W));\n const d2 = (dx, dy) => dx * dx + dy * dy;\n const minPair = (pair1, pair2) => (pair1.d2 < pair2.d2 ? pair1 : pair2);\n const pair = ({ x, y, value }, i, j) => ({ d2: d2(x - i, y - j), value });\n const min = (i, j) => (current, gen) => minPair(current, pair(gen, i, j));\n const closest = (i, j) => generators.reduce(min(i, j), { d2: +Infinity });\n const rows = array(H, j => j);\n for (let row of rows) {\n V[row] = array(W, i => closest(i, row).value);\n yield V;\n }\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":230,"value":"md`A less naive approach is to simultaneously grow convex shapes from each generator and set the pixels reached with the corresponding distance. A generator shape stops growing when all new grown pixels have shorter distance to other generators. This way each generator's zone of influence doesn't extend to the whole canvas and the result is reached far more rapidly.\n\nIf the shape is a circle, then by construction every pixel is nearest from the generator whose disk reaches it first, so no distance computation or comparison are performed. But this requires to compute circles of pixels whose radius grow by one at each step. The [midpoint circle algorithm](https://en.wikipedia.org/wiki/Midpoint_circle_algorithm) would be a fast way to do this, but this method leaves some pixels unset and breaks the algorithm, as can be seen in the following demo.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":287,"value":"md`The [Andres algorithm (in french)](https://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d%27Andres) improves the result with a similar approach. In both case though, there remain artefacts caused by the growing disc approach.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":283,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":236,"value":"md`Using growing right-angles diamonds instead leaves no pixel unset nor artefacts, but since the distance is no longer directly corresponding to the algorithmic step, it has to be computed, though many times less than in the naive approach due to diamond's 8-fold symetry and shapes limited expansion.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":332,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":407,"value":"md`Note: If you're using the [Manhattan distance](https://en.wikipedia.org/wiki/Taxicab_geometry) with growing right angles diamonds, no distance computation is necessary since diamonds are Taxicab geometry circles (the method though seems to generate glitches in some cases, may be a bug).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":409,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":525,"value":"array = (size, mapper) => [...Array(size)].map((_, i) => mapper(i))","pinned":false,"hidden":false,"mode":"ojs"},{"id":665,"value":"render = algo => {\n // create canvas context\n const ctx = DOM.context2d(...dimensions, 1);\n // async click events on the canvas\n const clicks = domEvents(ctx.canvas, \"click\");\n // async data triggered by clicks\n const data = mapWithIter(startWith(clicks, 0), algo);\n // renderer: renders array values into preexisting canvas\n const color = val => (val != undefined ? colors[val] : [0, 0, 0]);\n const renderer = ctx => arr => canvas(ctx, (i, j) => color(arr[j][i]));\n // bind data source to renderer\n return map(data, renderer(ctx));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":72,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":769,"value":"import { canvas } from \"@ehouais/utils\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":508,"value":"import {checkbox} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":569,"value":"import { map, mapWithIter, domEvents, startWith } from \"71bde4d5b2990b69\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}