2b:null 2c:["$","title",null,{"children":"Basic Shepard's Interpolation | Marius Hogräfer | Observable"}] 31:[] 2f:{"id":"f5f1384317e085b6","slug":"basic-shepards-interpolation","title":"Basic Shepard's Interpolation","thumbnail":"107385b101a6143dfcf69d2ae39589b31c8eeebf0df5bee3fe2eece889102542","access_level":"public","create_time":"$D2020-10-15T09:26:47.713Z","update_time":"$D2020-10-27T10:05:46.336Z","view_time":null,"first_public_time":"$D2020-10-19T11:29:56.435Z","fork":false,"stars":5,"starred":false,"owner":{"type":"team","id":"3adf8da5f114b89d","login":"mahog","name":"Marius Hogräfer","avatar_url":"https://avatars-next.observableusercontent.com/89ae96d8530754fb6ed75fdeb4226d4278c2bfc782de259df99b2ac34bd420aa","tier":"starter_2024"},"version":1298,"publish_version":1298,"role":null,"authored":false,"authors":[{"type":"individual","id":"f14bf17e190cd922","login":"mahog","name":"Marius Hogräfer","avatar_url":"https://avatars-next.observableusercontent.com/89ae96d8530754fb6ed75fdeb4226d4278c2bfc782de259df99b2ac34bd420aa","tier":null}],"members":[{"type":"individual","id":"f14bf17e190cd922","login":"mahog","name":"Marius Hogräfer","avatar_url":"https://avatars-next.observableusercontent.com/89ae96d8530754fb6ed75fdeb4226d4278c2bfc782de259df99b2ac34bd420aa","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":3,"collection":{"id":"65c721fe9b3c4eee","slug":"vis-algorithms","title":"Vis Algorithms","owner":{"id":"3adf8da5f114b89d","login":"mahog","name":"Marius Hogräfer"}},"type":"notebook","body":{"title":"Basic Shepard's Interpolation","cells":[{"id":0,"value":"md`\n# Basic Shepard's Interpolation\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"html`\n\n $\"AU$ \n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":993,"value":"md`\nIn this notebook, we will have a look at **the basic implementation of this interpolation**, following the algorithm discussed on [Wikipedia](https://en.wikipedia.org/wiki/Inverse_distance_weighting). An extended version following the algorithm discussed in [the original paper](https://doi.org/10.1145/800186.810616) can be found in [another notebook](https://observablehq.com/d/5a354fcf2a80ae65).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1254,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1268,"value":"md`## Setup: Preparing the data and grid`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":997,"value":"md`\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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":218,"value":"randomData = d3.range(dataPoints).map(d => {\n const dx = Math.random();\n const dy = Math.random();\n \n return {\n x: dx * width, \n y: dy * height,\n z: noise(dx * resolution, dy * resolution)\n };\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"dataPoints = 5000;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"showDots();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1129,"value":"md`\nThe idea of Shephard'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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"columns = 45;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"rows = 25;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1159,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1263,"value":"md`## Exercise: Implement the algorithm`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1139,"value":"md`\nWith the setup out of the way, it is now your turn to implement the Shephard'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 _getShephardsInterpolatedValue(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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":858,"value":"K = dataPoints * 0.1;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":812,"value":"powerParameter = 16;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":705,"value":"function getShephardsInterpolatedValue(P) {\n const distancesToP = getDistancesToP(P);\n \n if (distancesToP[0].distanceP === 0) {\n return distancesToP[0].point.z;\n }\n \n const kNN = distancesToP.slice(0, K).map (d => d.point);\n \n const numerator = kNN\n .map(Di => {\n const wi = getWi(Di, P);\n const ui = Di.z;\n return wi*ui;\n })\n .reduce(sum, 0);\n \n const denominator = kNN\n .map(Di => getWi(Di, P))\n .reduce(sum, 0);\n \n const shephardsInterpolatedValue = numerator / denominator;\n \n return shephardsInterpolatedValue;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1220,"value":"showGrid();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":392,"value":"function distance(P, Di) {\n return Math.sqrt((P.x - Di.x) ** 2 + (P.y - Di.y) ** 2);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":798,"value":"function getWi(Di, P) {\n const wi = 1 / (distance(P, Di) ** powerParameter);\n \n return wi;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":801,"value":"sum = (a, b) => a + b;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1289,"value":"md`\n## Further Reading\n\n* The original [paper by Shepard](https://doi.org/10.1145/800186.810616)\n* Notebook on the [modified Shepard's method by @fil](https://observablehq.com/@fil/modified-shepards-method)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1286,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"md`\n## Appendix\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"html`

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

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":169,"value":"md`\n### Helper Functions\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":722,"value":"color = d3.scaleLinear().domain([minValue, maxValue]).range([\"white\", \"black\"]);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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(getShephardsInterpolatedValue(d.value)))\n .on(\"click\", (event, d) => {\n });\n \n return canvas;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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 => d.x)\n .attr(\"cy\", d => d.y)\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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1191,"value":"function showDots() {\n renderDots(dotCanvas);\n \n return dotCanvas.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1192,"value":"function showGrid() {\n renderGrid(gridCanvas);\n \n return gridCanvas.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":200,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"md`\n### Computed Variables\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":844,"value":"minValue = Math.min(...randomData.map(d => d.z));","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":845,"value":"maxValue = Math.max(...randomData.map(d => d.z))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"radius = Math.sqrt(2) * spacing / 2;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":285,"value":"spacing = Math.min(verticalSpacing, horizontalSpacing);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":280,"value":"horizontalSpacing = (width - 2*margin) / columns;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":281,"value":"verticalSpacing = (height - 2*margin) / rows;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":203,"value":"html`

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