31:T926,blur = { const { floor, max, min, round } = Math; function blurTransfer(V, r, n, vertical) { if (!r) return; // radius 0 is a noop const [source, target] = V, rc = Math.ceil(r), frac = (rc - r) / rc, frac_1 = r / rc, m = floor(source.length / n), w = 2 * rc + 1, w1 = 1 / w, ki = vertical ? m : 1, kj = vertical ? 1 : n, W = w * ki, R = rc * ki; for (let j = 0; j < m; ++j) { const k0 = kj * j, kn = k0 + ki * (n - 1); // faster loop for integer radius if (!frac) { for (let i = 0, sr = w * source[k0]; i < n + rc; ++i) { const k = ki * i + kj * j; sr += source[min(k, kn)] - source[max(k - W, k0)]; target[max(k - R, k0)] = sr * w1; } } else { for (let i = 0, sr = w * source[k0]; i < n + rc; ++i) { const k = ki * i + kj * j, index = max(k - R, k0); sr += source[min(k, kn)] - source[max(k - W, k0)]; target[index] = frac_1 * sr * w1 + frac * source[index]; } } } V.reverse(); // target becomes V[0] and will be used as source in the next iteration } return function blur() { var radius = 5, accessor, width, iterations = 3, direction = null; function blur(data) { const n = width || data.length, m = floor(data.length / n), V = [ accessor ? Float32Array.from(data, accessor) : Float32Array.from(data), new Float32Array(data.length) ]; for (var i = 0; i < iterations; i++) { if (direction !== "y" && n > 1) { blurTransfer(V, radius, n, false); } if (direction !== "x" && m > 1) { blurTransfer(V, radius, m, true); } } V[0].width = n; V[0].height = m; return V[0]; } blur.radius = _ => (_ === undefined ? radius : ((radius = +_), blur)); blur.width = _ => (_ === undefined ? width : ((width = round(+_)), blur)); blur.iterations = _ => _ === undefined ? iterations : ((iterations = +_), blur); blur.direction = _ => _ === undefined ? direction : ((direction = _), blur); blur.value = _ => typeof _ === "function" ? ((accessor = _), blur) : accessor; return blur; }; }32:T89e,// original code from D3 mmblur1 = { function blurX(source, target, r) { var n = source.width, m = source.height, w = (r << 1) + 1; for (var j = 0; j < m; ++j) { for (var i = 0, sr = 0; i < n + r; ++i) { if (i < n) { sr += source.data[i + j * n]; } if (i >= r) { if (i >= w) { sr -= source.data[i - w + j * n]; } target.data[i - r + j * n] = sr / Math.min(i + 1, n - 1 + w - i, w); } } } } // TODO Optimize edge cases. // TODO Optimize index calculation. // TODO Optimize arguments. function blurY(source, target, r) { var n = source.width, m = source.height, w = (r << 1) + 1; for (var i = 0; i < n; ++i) { for (var j = 0, sr = 0; j < m + r; ++j) { if (j < m) { sr += source.data[i + j * n]; } if (j >= r) { if (j >= w) { sr -= source.data[i + (j - w) * n]; } target.data[i + (j - r) * n] = sr / Math.min(j + 1, m - 1 + w - j, w); } } } } return function blur(source, r, n) { if (n === undefined) n = source.length; const m = source.length / n; var values0 = Float32Array.from(source), values1 = new Float32Array(n * m); blurX( { width: n, height: m, data: values0 }, { width: n, height: m, data: values1 }, r ); blurY( { width: n, height: m, data: values1 }, { width: n, height: m, data: values0 }, r ); blurX( { width: n, height: m, data: values0 }, { width: n, height: m, data: values1 }, r ); blurY( { width: n, height: m, data: values1 }, { width: n, height: m, data: values0 }, r ); blurX( { width: n, height: m, data: values0 }, { width: n, height: m, data: values1 }, r ); blurY( { width: n, height: m, data: values1 }, { width: n, height: m, data: values0 }, r ); return Object.assign(values0, { width: n, height: m }); }; // this is the true function in d3 /* function blur(source, r) { const k = 2; return blur(source, r >> k); }; */ }33:[] 2e:{"title":"Moving average blur","cells":[{"id":0,"value":"md`# Moving average blur`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"md`To compute its [density contours](https://github.com/d3/d3-contour/blob/master/README.md#contourDensity), D3 uses a moving-average [blur](https://github.com/d3/d3-contour/blob/master/src/blur.js), which alternates blurring rows then columns, [3 times each](https://github.com/d3/d3-contour/blob/master/src/density.js#L46). Let’s try and see if we can use it for flat data (1D), and speed it up a bit.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":736,"value":"md`First, the source is a flat array representing numerical values in a rectangle width × height. In our case width = ${n} and height = ${m}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":741,"value":"n = 400","pinned":false,"hidden":false,"mode":"ojs"},{"id":742,"value":"m = 300","pinned":false,"hidden":false,"mode":"ojs"},{"id":71,"value":"source = Float32Array.from({ length: n * m }, Math.random)","pinned":true,"hidden":false,"mode":"ojs"},{"id":189,"value":"show(\n blur()\n .width(n)\n .radius(5)\n) // new code","pinned":true,"hidden":false,"mode":"ojs"},{"id":266,"value":"show(source => mmblur1(source, 5, n)) // calls the code extracted from d3-contour, for comparison","pinned":true,"hidden":false,"mode":"ojs"},{"id":878,"value":"md`The moving average procedure also works in 1-D, resulting in a smooth approximation of data (here, a random walk). Note that this diverges a little from a previous [“Moving average” notebook](https://observablehq.com/@d3/moving-average): in our case the averaged data is defined everywhere on the domain (instead of losing the extremities), and the values are centered instead of being pushed at the end of the interval they average.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":848,"value":"embed(\n {\n title: \"1D smoothing of a random walk\",\n width: Math.max(300, width * 0.7),\n height: 250,\n layer: [\n {\n mark: \"line\",\n data: {\n values: [\n values.map((y, i) => ({\n x: i,\n y,\n type: \"source\"\n })),\n Array.from(blurred, (y, i) => ({\n x: i,\n y,\n type: \"blurred\"\n })),\n [\n { x: 0, y: 0, type: \"interval\" },\n { x: 2 * radius, y: 0, type: \"interval\" }\n ]\n ].flat()\n },\n encoding: {\n x: {\n field: \"x\",\n type: \"quantitative\"\n },\n y: {\n field: \"y\",\n type: \"quantitative\"\n },\n stroke: { field: \"type\", sort: null }\n }\n }\n ]\n },\n { actions: false }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":867,"value":"viewof radius = slider({\n min: 0,\n max: 15,\n value: 5,\n step: 0.01,\n description: \"radius (default: 5)\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1058,"value":"viewof iterations = slider({\n min: 1,\n max: 10,\n value: 3,\n step: 1,\n description: \"iterations (default: 3)\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":862,"value":"// random walk\nvalues = {\n let x = 1;\n return Array.from({ length: 300 }, () => (x += Math.sin(1e6 * x)));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":883,"value":"blurred = blur()\n .radius(radius)\n .iterations(iterations)(values)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1132,"value":"PROFILE = md`## Profile\n\nThe chart below shows how one Dirac signal (value 1 in position 0) is blurred with radius ${profile_radius} and ${profile_iterations} iterations. Note that the computation time is in ${tex`\\mathcal{O}`}(iterations) and independent of the radius—so you do want to keep it to the strict minimum (3 for a nice-looking bell-shaped curve).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1141,"value":"embed(\n {\n title: `Blurring profile for radius=${profile_radius} with ${profile_iterations} iterations`,\n width: Math.max(300, width * 0.7),\n height: 270,\n layer: [\n {\n mark: \"bar\",\n data: {\n values: Array.from(profile).map((y, i) => ({\n x: i - 29,\n y,\n type: \"profile\"\n }))\n },\n encoding: {\n x: {\n field: \"x\",\n type: \"quantitative\"\n },\n y: {\n field: \"y\",\n type: \"quantitative\",\n scale: { nice: false }\n }\n //stroke: { field: \"type\", sort: null }\n }\n }\n ]\n },\n { actions: false }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1145,"value":"viewof profile_radius = slider({\n min: 0,\n max: 15,\n value: 5,\n description: \"radius (default: 5)\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1149,"value":"viewof profile_iterations = slider({\n min: 0,\n max: 10,\n value: 3,\n step: 1,\n description: \"iterations (default: 3)\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1133,"value":"profile = blur()\n .iterations(profile_iterations)\n .radius(profile_radius)(Float32Array.from({ length: 59 }, (d, i) => i === 29))","pinned":true,"hidden":false,"mode":"ojs"},{"id":1237,"value":"d3.sum(profile)","pinned":true,"hidden":false,"mode":"ojs"},{"id":923,"value":"md`## API\n\nThe current API of this test version is:\n~~~{js}\nconst B = blur()\n .value([accessor = d => d])\n .radius([radius = 5])\n .iterations([iterations = 3])\n .width([width = 1])\n .direction([direction = null|\"x\"|\"y\"])\nB(data);\n~~~\n\nThe final API is still pending.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":457,"value":"blur()([0, 1, 2, 3, 8, 10, 12, 27])","pinned":true,"hidden":false,"mode":"ojs"},{"id":624,"value":"blur()\n .radius(2)\n .iterations(1)\n .width(4)([0, 1, 2, 3, 8, 10, 12, 27])","pinned":true,"hidden":false,"mode":"ojs"},{"id":1036,"value":"md`A *value* accessor allows complex input data and intermediate computations:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1017,"value":"data = Array.from(values, (d, i) => ({ value: d, index: i }))","pinned":true,"hidden":false,"mode":"ojs"},{"id":1008,"value":"blur().value(d => Math.sin(d.value))(data)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1050,"value":"md`And the function accepts iterables:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1046,"value":"blur()(new Set(values.slice().sort()))","pinned":true,"hidden":false,"mode":"ojs"},{"id":1216,"value":"md`### Playing with 2D data`","pinned":false,"hidden":false,"mode":"ojs"},{"id":671,"value":"md`The graphs below show 1D blurring applied to 2D data (don't ask), and the {iterations, direction} options that the new function allows:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":629,"value":"show(blur()) // 1D horizontal","pinned":true,"hidden":false,"mode":"ojs"},{"id":714,"value":"show(\n blur()\n .width(n)\n .direction(\"y\")\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1076,"value":"// compose a heavy \"x\" blur with a light \"y\" blur\nshow(data =>\n blur()\n .width(n)\n .radius(1)\n .iterations(1)\n .direction(\"y\")(\n blur()\n .width(n)\n .radius(20)\n .iterations(4)\n .direction(\"x\")(data)\n )\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1379,"value":"md`### Fractional blurring`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1122,"value":"show(\n blur()\n .width(n)\n .radius(.5)\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":284,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":264,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":111,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":870,"value":"import { slider } from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":847,"value":"embed = require(\"vega-embed@6\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":844,"value":"html``","pinned":true,"hidden":false,"mode":"ojs"},{"id":110,"value":"function show(blur, { nn = n, runs = 10 } = {}) {\n const m = source.length / nn;\n const scale = Math.pow(2, -Math.ceil(Math.log2(Math.max(nn, m) / 400)));\n\n const w = scale * n,\n h = scale * m;\n const x = d3.scaleLinear([0, nn], [0, w]),\n y = d3.scaleLinear([0, m], [0, h]);\n const c = d3.scaleSequential(d3.interpolateGreys);\n\n const context = DOM.context2d(width, h);\n\n let blurred;\n let t = performance.now();\n for (let i = 0; i < runs; i++) blurred = blur(source);\n t = (performance.now() - t) / runs;\n\n // a rather inefficient way to show the output :-)\n function draw(array) {\n for (let k = 0; k < array.length; k++) {\n const i = k % nn,\n j = Math.floor(k / nn);\n context.fillStyle = c(array[i + n * j]);\n context.fillRect(x(i), y(j), x(i + 1) - x(i), y(j + 1) - y(j));\n }\n }\n\n draw(source);\n context.translate(x(nn) + 50, 0);\n context.fillStyle = \"red\";\n context.fillText(`${+t.toFixed(1)}ms`, -40, 10);\n draw(blurred);\n\n return context.canvas;\n}","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}