2f:[] 2d:{"title":"Extended Shepard's Interpolation","cells":[{"id":0,"value":"md`\n# Extended Shepard's Interpolation\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"html`\n\n $\"AU$ \n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"md`This notebook is part of the tutorial series following the Data Visualization lecture at Aarhus University.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"md`\nIn this coding exercise, we will implement the [Shepard's Interpolation](https://en.wikipedia.org/wiki/Inverse_distance_weighting), which in data visualization is often used to reduce the number of displayed data points by computing a representative for a neighborhood of data points.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":993,"value":"md`\nIn this notebook, we will have a look at **the extended version of the algorithm** discussed in [the original paper](https://doi.org/10.1145/800186.810616). An implementation of the basic version can be found in [another notebook](https://observablehq.com/d/f5f1384317e085b6).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1299,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":997,"value":"md`\n## Setup: Preparing the data and grid\nWe will begin by generating the dataset that we will work with in this notebook. For this, we will generate randomly distributed data points and assign them a value from a [Perlin noise field](https://en.wikipedia.org/wiki/Perlin_noise). We use Perlin noise to ensure that our visual output looks relatively natural, rather than just entirely random.\n\nThe cell below takes care of that for us, generating dataPoints=${dataPoints} random points:\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":218,"value":"randomData = d3.range(dataPoints).map(d => {\n const dx = Math.random();\n const dy = Math.random();\n \n return {\n dx, \n dy,\n z: noise(dx * resolution, dy * resolution)\n };\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":219,"value":"dataPoints = 5000;","pinned":true,"hidden":false,"mode":"ojs"},{"id":1005,"value":"md`\nThis is what our randomly distributed data looks like, when drawing it on a canvas (the fill color indicates the value from the Perlin field):\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":79,"value":"showDots();","pinned":false,"hidden":false,"mode":"ojs"},{"id":1129,"value":"md`\nThe idea of Shepard's Interpolation is now to \"reduce the resolution\" of this data, while maintaining its overall value distribution. To do so, we need to first find a good data sample.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1058,"value":"md`\nTo keep things simple, we will use the center points of a regular grid as sampling points. So for the center point of each grid cell, we will compute an interpolated value.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":43,"value":"columns = 20;","pinned":true,"hidden":false,"mode":"ojs"},{"id":41,"value":"rows = 10;","pinned":true,"hidden":false,"mode":"ojs"},{"id":1168,"value":"md`\nIn the cell below, we create an array representing a _columns_ x _rows_ grid of center points.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":335,"value":"// generates a rows x columns matrix, using values from a Perlin noise field.\nmatrix = d3.range(0, rows).map(i => {\n return d3.range(0, columns).map(j => { \n const P = getCellCenterInViewSpaceCoords(j, i);\n return P;\n }); \n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":1078,"value":"md`\nIn accordance with the original paper, we will refer to an individual center point as _P_ from now on. \n\nEvery point P has an x and y coordinate defined in **view space**, i.e., coordinates on the screen. Our random data is defined in **data space**, i.e., values on abstract axes between 0 and 1. Therefore, whenever we want to measure the distance from a point on our screen to the center point of a grid cell, we need to first transform its data coordinates into screen coordinates.\n\nThe cell below takes care of that for us, adding x and y coordinates to the data that correspond to their view space location:\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1090,"value":"{\n randomData.forEach(d => {\n d.x = scaleX(d.dx);\n d.y = scaleY(d.dy);\n });\n \n return randomData;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1159,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1139,"value":"md`\n## Exercise: Implement the algorithm\nWith the setup out of the way, it is now your turn to implement the Shepard's interpolation by filling in the cell below. All rendering functionality is already taken care of, all you need to worry about is the actual algorithm that computes the interpolated value for a center point P. If you are interested, you may have a look under the hood in the appendix. \n\nThe rendering routine expects _getShepardsInterpolatedValue(P)_ to return a value between -0.5 and 0.5. Feel free to create as many variables and new cells as you like. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1148,"value":"md`\nIn your implementation, you can make use of the two variables below: K (representing the number of _k_-nearest neighbors that are used for interpolation) and powerParameter (which is used to emphasize close points).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":858,"value":"K = dataPoints * 0.1;","pinned":true,"hidden":false,"mode":"ojs"},{"id":812,"value":"powerParameter = 16;","pinned":true,"hidden":false,"mode":"ojs"},{"id":1311,"value":"function getWi_(Di, P) {\n const dist = distance(Di, P);\n \n return 1 / (dist ** powerParameter);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":705,"value":"function getShepardsInterpolatedValue(P) {\n const distancesToP = getDistancesToP(P);\n \n if (distancesToP[0].distanceP === 0) {\n return distancesToP[0].point.z;\n }\n \n const cPrime = getCPrime(P);\n \n const numerator = cPrime\n .map(Di => {\n const wi = getWi(Di, P);\n const deltaZi = getDeltaZi(Di, P);\n \n return wi * (Di.z + deltaZi);\n })\n .reduce(sum);\n \n const denominator = cPrime\n .map(Di => {\n return getWi(Di, P);\n })\n .reduce(sum);\n \n const shepardsInterpolatedValue = denominator === 0 ? 0 : numerator / denominator;\n return shepardsInterpolatedValue;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1224,"value":"md`The cell below renders the grid, using the output of _getShephardsInterpolatedValue_ to determine the value for each cell. It will update automatically as you update the code for that function.\n\n_Note: You can also use the **show()** function to visualize the data distributed ontop of the grid._`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1220,"value":"showGrid();","pinned":false,"hidden":false,"mode":"ojs"},{"id":392,"value":"function distance(P, Q) {\n return Math.sqrt((P.x - Q.x) ** 2 + (P.y - Q.y) ** 2);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":644,"value":"function getDistancesToP(P) {\n // distance of all data points to center point of cell\n // TODO: this is horribly inefficient\n const distancesToP = randomData\n .map(Di => {\n return {\n point: Di,\n distanceP: distance(P, Di)\n };\n })\n .sort((a, b) => a.distanceP - b.distanceP);\n \n return distancesToP;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":798,"value":"C_PRIME = new Map();","pinned":true,"hidden":false,"mode":"ojs"},{"id":1250,"value":"function getCPrime(P) {\n if (C_PRIME.has(P)) {\n return C_PRIME.get(P);\n }\n\n const distancesToP = getDistancesToP(P);\n \n // all points within radius distance of the center point of a cell\n const cP = distancesToP\n .filter(Di => Di.distanceP <= radius);\n \n const cPP = [];\n \n if (cP.length <= 4) {\n // return the four nearest neighbors\n cPP.push(...distancesToP.slice(0, 4).map(d => d.point));\n } else if (cP.length <= 10) {\n // return all points within the radius\n cPP.push(...cP.map(d => d.point));\n } else {\n // return the ten nearest neighbors\n cPP.push(...distancesToP.slice(0, 10).map(d => d.point));\n }\n \n C_PRIME.set(P, cPP);\n return cPP;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1252,"value":"R_PRIME = new Map();","pinned":true,"hidden":false,"mode":"ojs"},{"id":1253,"value":"function getRPrime(P) {\n if (R_PRIME.has(P)) {\n return R_PRIME.get(P);\n }\n \n const distancesToP = getDistancesToP(P);\n \n // all points within radius distance of the center point of a cell\n const cP = distancesToP\n .filter(Di => Di.distanceP <= radius);\n \n let rPrime = -1;\n \n if (cP.length <= 4) {\n rPrime = distancesToP[4].distanceP;\n } else if (cP.length <= 10) {\n rPrime = radius;\n } else {\n rPrime = distancesToP[10].distanceP;\n }\n \n R_PRIME.set(P, rPrime);\n return rPrime;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1255,"value":"SI_P = new Map();","pinned":true,"hidden":false,"mode":"ojs"},{"id":1257,"value":"function getSi(Di, P) {\n let s = -1;\n \n const d = distance(Di, P);\n const rPrime = getRPrime(P);\n \n if (d <= rPrime / 3) {\n s = 1/d;\n } else if (d <= rPrime) {\n s = 27 / (4 * rPrime)\n } else {\n s = 0;\n }\n \n return s;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1259,"value":"function getTi(Di, P) {\n const cPPrime = getCPrime(P);\n \n const numerator = cPPrime\n .map(Dj => {\n const sj = getSi(Dj, P);\n const di = distance(P, Di);\n const dj = distance(P, Dj);\n const cos = ((P.x - Di.x)*(P.x - Dj.x) + (P.y - Di.y)*(P.y - Dj.y)) / di*dj;\n\n return sj*(1 - cos);\n })\n .reduce(sum);\n \n const denominator = cPPrime\n .map(Dj => getSi(Dj, P))\n .reduce(sum);\n \n const ti = denominator === 0 ? 0 : numerator / denominator;\n return ti;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1261,"value":"W = new Map();","pinned":true,"hidden":false,"mode":"ojs"},{"id":1263,"value":"function getWi(Di, P) {\n if (W.has(P)) {\n const map = W.get(P);\n if (map.has(Di)) {\n return map.get(Di);\n }\n } else {\n W.set(P, new Map());\n }\n \n const si = getSi(Di, P);\n const ti = getTi(Di, P);\n const wi = ti ** 2 * (1 + ti);\n \n if (!W.has(P)) {\n W.set(P, new Map());\n }\n \n const map = W.get(P);\n map.set(Di, wi);\n return wi;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1265,"value":"C_DOUBLE_PRIME = new Map();","pinned":true,"hidden":false,"mode":"ojs"},{"id":1267,"value":"function getCDoublePrime(Di, P) {\n if (C_DOUBLE_PRIME.has(P)) {\n const map = C_DOUBLE_PRIME.get(P);\n if (map.has(Di)) {\n return map.get(Di);\n }\n } else {\n C_DOUBLE_PRIME.set(P, new Map());\n }\n \n // use copy of cPrime (which is cached in C_PRIME), because splice is used later that would destroy cPrime\n const cPrime = getCPrime(P).map(d => d);\n \n const indexInCPrime = cPrime.indexOf(Di);\n \n if (indexInCPrime > -1) {\n cPrime.splice(indexInCPrime, 1);\n }\n \n return cPrime;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":801,"value":"sum = (a, b) => a + b;","pinned":true,"hidden":false,"mode":"ojs"},{"id":1269,"value":"function getAi(Di, P) {\n const cDoublePrime = getCDoublePrime(Di, P);\n \n const numerator = cDoublePrime\n .map(Dj => {\n const wj = getWi(Dj, P);\n\n return (Dj.z - Di.z)*(Dj.x - Di.x) / (distance(Dj, Di)**2);\n })\n .reduce((newValue, oldValue) => newValue + oldValue);\n \n const denominator = cDoublePrime\n .map(Dj => {\n return getWi(Dj, P); \n })\n .reduce(sum);\n \n const Ai = denominator === 0 ? 0 : numerator / denominator;\n return Ai;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1272,"value":"function getBi(Di, P) {\n const cDoublePrime = getCDoublePrime(Di, P);\n \n const numerator = cDoublePrime\n .map(Dj => {\n const wj = getWi(Dj, P);\n\n return (Dj.z - Di.z)*(Dj.y - Di.y) / (distance(Dj, Di)**2);\n })\n .reduce(sum);\n \n const denominator = cDoublePrime\n .map(Dj => {\n return getWi(Dj, P); \n })\n .reduce(sum);\n \n const Ai = denominator === 0 ? 0 : numerator / denominator;\n return Ai;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1274,"value":"V = new Map();","pinned":true,"hidden":false,"mode":"ojs"},{"id":1276,"value":"function getV(P) {\n if (V.has(P)) {\n return V.get(P);\n }\n \n const cPrime = getCPrime(P);\n \n const z = cPrime.map(d => d.z);\n const maxZ = Math.max(...z);\n const minZ = Math.min(...z);\n \n const ASquaredPlusBSquared = cPrime.map(Di => {\n const ASquared = getAi(Di, P) ** 2;\n const BSquared = getBi(Di, P) ** 2;\n\n return ASquared + BSquared;\n });\n \n const maxASquaredPlusBSquared = Math.max(...ASquaredPlusBSquared);\n \n const v = maxASquaredPlusBSquared === 0\n ? 0\n : 0.1*(maxZ - minZ) / Math.sqrt(maxASquaredPlusBSquared);\n \n V.set(P, v);\n return v;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1278,"value":"function getDeltaZi(Di, P) {\n const Ai = getAi(Di, P);\n const Bi = getBi(Di, P);\n const v = getV(P);\n const di = distance(P, Di);\n \n const a = (Ai*(P.x - Di.x) + Bi*(P.y - Di.y));\n const b = v + di === 0 ? 0 : v / (v + di);\n \n return a * b;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1288,"value":"show()","pinned":true,"hidden":false,"mode":"ojs"},{"id":189,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"md`\n## Appendix\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":194,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":121,"value":"md`\n### Parameters\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":33,"value":"height = 500;","pinned":true,"hidden":false,"mode":"ojs"},{"id":258,"value":"margin = 10;","pinned":true,"hidden":false,"mode":"ojs"},{"id":75,"value":"dotRadius = 3;","pinned":true,"hidden":false,"mode":"ojs"},{"id":63,"value":"resolution = 4;","pinned":true,"hidden":false,"mode":"ojs"},{"id":74,"value":"perlinOctaves = 8;","pinned":true,"hidden":false,"mode":"ojs"},{"id":197,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":169,"value":"md`\n### Helper Functions\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":410,"value":"scaleX = d3.scaleLinear().domain([0, 1]).range([margin, width - margin]);","pinned":false,"hidden":false,"mode":"ojs"},{"id":411,"value":"scaleY = d3.scaleLinear().domain([0, 1]).range([margin, height - margin]);","pinned":false,"hidden":false,"mode":"ojs"},{"id":722,"value":"color = d3.scaleLinear().domain([minValue, maxValue]).range([\"white\", \"black\"]);","pinned":false,"hidden":false,"mode":"ojs"},{"id":291,"value":"function renderGrid(canvas) {\n const grid = canvas.select(\"g.grid\")\n .attr(\"transform\", `translate(${margin}, ${margin})`);\n \n grid.selectAll(\"*\").remove();\n \n // generates a rows x columns matrix, using values from a Perlin noise field.\n const linearizedMatrix = linearizeMatrix(matrix);\n \n const cells = grid.selectAll(\"g.cell\").data(linearizedMatrix).enter()\n .append(\"g\")\n .attr(\"class\", \"cell\")\n .attr(\"transform\", d => `translate(${d.col * spacing}, ${d.row * spacing})`);\n \n const boundary = cells.append(\"rect\")\n .attr(\"class\", \"boundary\")\n .attr(\"width\", spacing)\n .attr(\"height\", spacing)\n .attr(\"stroke\", \"transparent\")\n .attr(\"fill\", d => color(getShepardsInterpolatedValue(d.value)))\n .on(\"click\", (event, d) => {\n });\n \n return canvas;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":31,"value":"/**\n* Draws the dots that represent the Perlin noise from the matrix.\n*/\nfunction renderDots(canvas) { \n const points = canvas.select(\"g.points\");\n points.selectAll(\"*\").remove();\n \n const point = points.selectAll(\"circle.point\").data(randomData).enter()\n .append(\"circle\")\n .attr(\"class\", \"point\")\n .attr(\"r\", dotRadius)\n .attr(\"cx\", d => scaleX(d.dx))\n .attr(\"cy\", d => scaleY(d.dy))\n .attr(\"fill\", d => color(d.z))\n .attr(\"stroke\", \"#ccc\");\n \n point.append(\"title\").text(d => d.value);\n \n return canvas;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":456,"value":"function getCellCenterInViewSpaceCoords(column, row) {\n const x = (column + 0.5) * spacing + margin;\n const y = (row + 0.5) * spacing + margin;\n return {x, y};\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":302,"value":"/**\n* Transforms a two-dimensional array of numbers into a list of objects, that encode the original position in the \n* array and its original value.\n* @param{m} number[][] matrix of values in the range [0, 1].\n*/\nfunction linearizeMatrix(m) {\n return m.map((row, i) => {\n return row.map((cell, j) => { \n return { \n row: i,\n col: j,\n value: cell\n };\n })\n }).flat();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":270,"value":"/** \n* Generator function for Perlin noise at a certain position in normalized space.\n* @params see https://observablehq.com/@mbostock/perlin-noise\n*/\nnoise = octave(perlin2, perlinOctaves);","pinned":false,"hidden":false,"mode":"ojs"},{"id":235,"value":"function show() {\n renderDots(canvas);\n renderGrid(canvas);\n \n \n canvas.on(\"mouseover\", () => {\n canvas.select(\"g.grid\").transition().duration(250).style(\"opacity\", 0.7);\n canvas.select(\"g.points\").transition().duration(250).style(\"opacity\", 0.1);\n });\n canvas.on(\"mouseout\", () => {\n canvas.select(\"g.grid\").transition().duration(250).style(\"opacity\", 0.1);\n canvas.select(\"g.points\").transition().duration(250).style(\"opacity\", 1);\n });\n \n return canvas.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1191,"value":"function showDots() {\n renderDots(dotCanvas);\n \n return dotCanvas.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1192,"value":"function showGrid() {\n renderGrid(gridCanvas);\n \n return gridCanvas.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":200,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"md`\n### Computed Variables\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":50,"value":"canvas = {\n const canvas = d3.create(\"svg\")\n .attr(\"viewBox\", [0, 0, width, height]);\n \n canvas.append(\"g\").attr(\"class\", \"grid\");\n \n canvas.append(\"g\").attr(\"class\", \"points\");\n\n return canvas;\n};","pinned":false,"hidden":false,"mode":"ojs"},{"id":1181,"value":"dotCanvas = {\n const c = d3.create(\"svg\")\n .attr(\"viewBox\", [0, 0, width, height]);\n \n c.append(\"g\").attr(\"class\", \"points\");\n\n return c;\n};","pinned":false,"hidden":false,"mode":"ojs"},{"id":1186,"value":"gridCanvas = {\n const c = d3.create(\"svg\")\n .attr(\"viewBox\", [0, 0, width, height]);\n \n c.append(\"g\").attr(\"class\", \"grid\");\n\n return c;\n};","pinned":false,"hidden":false,"mode":"ojs"},{"id":844,"value":"minValue = Math.min(...randomData.map(d => d.z));","pinned":false,"hidden":false,"mode":"ojs"},{"id":845,"value":"maxValue = Math.max(...randomData.map(d => d.z))","pinned":false,"hidden":false,"mode":"ojs"},{"id":345,"value":"radius = Math.sqrt(2) * spacing / 2;","pinned":false,"hidden":false,"mode":"ojs"},{"id":285,"value":"spacing = Math.min(verticalSpacing, horizontalSpacing);","pinned":false,"hidden":false,"mode":"ojs"},{"id":280,"value":"horizontalSpacing = (width - 2*margin) / columns;","pinned":false,"hidden":false,"mode":"ojs"},{"id":281,"value":"verticalSpacing = (height - 2*margin) / rows;","pinned":false,"hidden":false,"mode":"ojs"},{"id":203,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"md`\n### Imported Variables\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"d3 = require(\"d3@6\");","pinned":false,"hidden":false,"mode":"ojs"},{"id":19,"value":"import {octave, perlin2} from \"@mbostock/perlin-noise\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W2f","stdlib":"1","titling":"auto"}