2d:null 2e:["$","title",null,{"children":"Marching Squares | Marius Hogräfer | Observable"}] 33:T742,function renderExampleCell() { d3.selectAll("svg.example").remove(); const w = 350; const h = 350; const pad = 15; const x = d3.create("svg") .attr("class", "example") .attr("width", w+2*pad) .attr("height", h+2*pad); const g = x.append("g") .attr("transform", `translate(${pad}, ${pad})`); const r = g.append("rect") .attr("width", w) .attr("height", h) .attr("fill", "transparent") .attr("stroke", "black"); const pts = [[0, 0.5], [0.5, 0], [0.5, 1], [1, 0.5]]; const p = g.selectAll("circle").data(pts).enter() .append("circle") .attr("r", 10) .attr("cx", d => d[0] * w) .attr("cy", d => d[1] * h) .attr("fill", "black"); p.append("title").text(d => `[${d[0]}, ${d[1]}]`); const l1 = g.append("g"); l1.append("line") .attr("x1", 0.5 * w) .attr("x2", 1 * w) .attr("y1", 0 * h) .attr("y2", 0.5 * h) .attr("stroke", "black") .attr("stroke-width", 5); l1.append("text") .attr("x", 0.5 * w) .attr("y", 0.4 * h) .attr("text-anchor", "middle") .attr("font-family", "monospace") .attr("font-size", 12) .text("renderSegment([...], 0.5, 0, 1, 0.5);"); const l2 = g.append("g").on("mouseover", () => { d3.select(this).select("text").style("display", "block"); }) .on("mouseout", () => { d3.select(this).select("text").style("display", "none"); }); l2.append("line") .attr("x1", 0 * w) .attr("x2", 0.5 * w) .attr("y1", 0.5 * h) .attr("y2", 1 * h) .attr("stroke", "black") .attr("stroke-width", 5); l2.append("text") .attr("x", 0.5 * w) .attr("y", 0.6 * h) .attr("text-anchor", "middle") .attr("font-family", "monospace") .attr("font-size", 12) .text("renderSegment([...], 0, 0.5, 0.5, 1);"); return x.node(); }34:[] 31:{"id":"59777cc7fc9ad2c0","slug":"marching-squares","title":"Marching Squares","thumbnail":"51b167f1f415e2d46b534d058657fddf4b06f44f7a2f829d0dfc5e08d677679e","access_level":"public","create_time":"$D2020-10-14T09:40:56.602Z","update_time":"$D2020-10-22T13:28:03.354Z","view_time":null,"first_public_time":"$D2020-10-22T13:19:37.378Z","has_unpublished_edits":null,"fork":false,"stars":0,"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":1198,"publish_version":1198,"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,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"65c721fe9b3c4eee","slug":"vis-algorithms","title":"Vis Algorithms","owner":{"id":"3adf8da5f114b89d","login":"mahog","name":"Marius Hogräfer"}},"type":"notebook","body":{"title":"Marching Squares","cells":[{"id":0,"value":"md`\n# Marching Squares\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"html`\n\n $\"AU$ \n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"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":10,"value":"md`\nIn this coding exercise, we will implement the [Marching Squares algorithm](https://en.wikipedia.org/wiki/Marching_squares), which is used in data visualization to compute so-called isolines over our data, indicating regions of equal data density.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1050,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1059,"value":"md`## Setup: Preparing the data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1045,"value":"md`\nTo begin with, we will first generate a two-dimensional field of [Perlin noise](https://en.wikipedia.org/wiki/Perlin_noise), which gives us \"smooth, but random\" noise, over which we can draw the isolines. We generate these values using an imported function and store them inside a simple, two-dimensional matrix:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"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 => noise(i / resolution, j / resolution)); \n});","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":444,"value":"cellTypesMatrix = d3.range(0, rows - 1).map(i => {\n return d3.range(0, columns - 1).map(j => { return {row: i, col: j, type: getCellType(i, j) }}); \n});","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1158,"value":"md`\nLet's have a look at our data before continuing:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1165,"value":"{\n const c = d3.create(\"svg\").attr(\"width\", width).attr(\"height\", height);\n renderDots(c);\n \n return c.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1169,"value":"md`\n_(Note that we have used a rather high-resolution grid of columns and rows, which is why the value distribution appears so smooth in this figure. You can set the resolution by modifying the columns and rows parameters in the Appendix)_\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1040,"value":"html`

`;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1055,"value":"md`\n## Exercise: Implement the algorithm\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":897,"value":"md`\nNext, we need to define a simple function that can check, whether a noisy value sits above a threshold value, in which case it returns 1, or below that threshold, in which case it returns 0.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":312,"value":"threshold = 0.15;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":320,"value":"// returns 1 if the value is above the threshold, 0 otherwise.\nfunction getIsoValue(value) {\n return +(value > threshold);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":943,"value":"md`\nThe Marching Squares algorithm creates line segments for a 2x2 neighborhood of cells in our matrix, based on the combination of cells that show a 1. Cells in the 2x2 neighborhood are assigned the labels a, b, c, and d in clockwise order, starting in the top-left corner. Then, the iso values of each cell are combined into the binary number abcd, representing the type of the cell.\n\nAs a first step, provide the code for the cell below, in which you compute the type of a cell in the matrix, given a row and column index.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":298,"value":"/**\n* Returns the type of a cell in the matrix (in decimal), based on what values sit on its corners.\n* @param{i} row index\n* @param{j} column index\n*/\nfunction getCellType(row, col) { \n const a = getIsoValue(matrix[row][col]);\n const b = getIsoValue(matrix[row][col+1]);\n const c = getIsoValue(matrix[row+1][col+1]);\n const d = getIsoValue(matrix[row+1][col]);\n \n return 8*a + 4*b + 2*c + d;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1070,"value":"md`\nNext, fill out the code for the function below, which renders the marching squares segments for each cell of our matrix. All rendering functionality is already provided by the _renderSegments()_ function. This function takes as parameters\n\n* a list of segment types that contain a particular line\n* coordinates of the particular line as x1, x2, y1, and y2\n\nThese coordinates are normalized along the size of a cell, i.e., on the interval between [0, 1]. Have a look at the image below to get a better idea of how to define these coordinates. You can hover over the dots to read off the normalized cell coordinates, and hover over the lines to read off the particular _renderSegments()_ command:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1147,"value":"renderExampleCell();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":948,"value":"/**\n* Renders a segment of the marching squares, from (x1, y1) to (x2, y2).\n* @param{types} list of allowed type numbers (in decimal)\n* @param{x1} starting x position\n* @param{x2} starting y position\n* @param{y1} ending x position\n* @param{y2} ending y position\n*/\nfunction renderLineSegment(types, x1, x2, y1, y2) {\n if (!(types instanceof Array)) {\n throw new TypeError('Parameter \"types\" of must be an array');\n }\n \n const segments = canvas.selectAll(\"g.segment\");\n segments.filter(d => types.indexOf(d.type) > -1).append(\"line\")\n .attr(\"x1\", x1 * spacing)\n .attr(\"x2\", x2 * spacing)\n .attr(\"y1\", y1 * spacing)\n .attr(\"y2\", y2 * spacing);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1152,"value":"md`\n Fill in the code in the cell below that renders the particular segments for each type of cell.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1016,"value":"/**\n* Renders the segments from the Marching Squares algorithm for each 2x2 neighborhood in the data, based on the \n* type of each cell.\n*/\nfunction renderSegments() {\n // diagonale top left \n renderLineSegment([5, 7, 8], 0, 0.5, 0.5, 0);\n \n // diagonale top right\n renderLineSegment([4, 10, 11], 0.5, 1, 0, 0.5);\n \n // diagonale bottom left\n renderLineSegment([1, 10, 14], 0, 0.5, 0.5, 1);\n \n // diagonale bottom right\n renderLineSegment([2, 5, 13], 0.5, 1, 1, 0.5);\n \n // vertical bar\n renderLineSegment([6, 9], 0.5, 0.5, 0, 1);\n \n // horizontal bar\n renderLineSegment([3, 12], 0, 1, 0.5, 0.5);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":840,"value":"// color of the line segments\nsegmentColor = \"red\";","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":192,"value":"pointChart.node()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":698,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"md`\n## Further Reading\n* [Video Tutorial on YouTube (but using Processing, not D3!)](https://www.youtube.com/watch?v=0ZONMNUKTfU)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":649,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"md`\n## Appendix\nThe cells below are importing libraries and functions into this notebook, which are used above.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":644,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":629,"value":"md`\n### Parameters\nBelow are some rendering parameters that you can specify to adjust the rendering.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":912,"value":"// specifies the gradient in the Perlin field. The lower, the steeper the local gradient.\nresolution = 32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":879,"value":"// number of levels that the Perlin noise can reach. The smaller, the \"rougher\" the appearance.\nperlinOctaves = 16;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"// number of columns of the matrix\ncolumns = 250;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"// number of rows of the matrix\nrows = 125;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":521,"value":"// if true, the type of each 2x2 neighborhood is rendered (mostly for debugging).\nshowGrid = false","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":523,"value":"// if true, renders the dots that represent the Perlin noise at a cell in the matrix.\nshowDots = true","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":519,"value":"// if true, renders the marching square lines.\nshowLines = true","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"// vertical size of the plot\nheight = 500;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":126,"value":"// size of each dot in px\ndotRadius = 3;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":706,"value":"// size of the line segments\nsegmentWidth = 3;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1137,"value":"html`\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":639,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":981,"value":"md`\n### Helper Functions\nListed below are the different functions that are used to render the image and to transform the matrix into a format that is easier to render.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":902,"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":528,"value":"/**\n* Draws square cells for each 2x2 neighborhood, with a label at the center representing the type of neighborhood.\n*/\nfunction renderCells(canv) {\n const cells = canv.selectAll(\"g.cell\").data(cellData).enter()\n .append(\"g\")\n .attr(\"class\", \"cell\")\n .attr(\"transform\", d => `translate(${d.col * spacing}, ${d.row * spacing})`);\n \n // cell boundaries\n cells.append(\"rect\")\n .attr(\"width\", spacing)\n .attr(\"height\", spacing)\n .attr(\"fill\", \"none\")\n .attr(\"stroke\", \"black\")\n .attr(\"stroke-width\", 1)\n .attr(\"stroke-opacity\", 0.3)\n .attr(\"width\", spacing)\n .attr(\"height\", spacing);\n \n // cell value label\n cells.append(\"text\")\n .attr(\"font-family\", \"sans-serif\")\n .attr(\"font-size\", fontSize)\n .attr(\"text-anchor\", \"middle\")\n .attr(\"dx\", spacing / 2)\n .attr(\"dy\", spacing / 1.5)\n .text(d => d.type);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":530,"value":"/**\n* Draws the dots that represent the Perlin noise from the matrix.\n*/\nfunction renderDots(canv) {\n const color = d3.scaleSequential(d3.interpolateGreys).domain([0, 1]);\n const points = canv.selectAll(\"circle.point\").data(data).enter()\n .append(\"circle\")\n .attr(\"class\", \"point\")\n .attr(\"r\", dotRadius)\n .attr(\"cx\", d => d.col * spacing)\n .attr(\"cy\", d => d.row * spacing)\n .attr(\"fill\", d => color(d.value))\n .attr(\"stroke\", \"none\");\n \n points.append(\"title\").text(d => d.value);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":547,"value":"/**\n* Creates the container for the segments, renders them, then styles them.\n*/\nfunction renderAllSegments(canv) {\n const segments = canv.selectAll(\"g.segment\").data(cellData).enter()\n .append(\"g\")\n .attr(\"class\", \"segment\")\n .attr(\"transform\", d => `translate(${d.col * spacing}, ${d.row * spacing})`);\n \n renderSegments();\n \n segments.selectAll(\"line\")\n .attr(\"stroke-width\", segmentWidth) \n .attr(\"stroke\", segmentColor);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":215,"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":1077,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":986,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":625,"value":"md`\n### Computed Variables\nThe variables below are derived variables that are necessary for generating the visualization.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":356,"value":"canvas = d3.create(\"svg\").attr(\"viewBox\", [0, 0, width, height]);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"data = linearizeMatrix(matrix);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":557,"value":"cellData = cellTypesMatrix.flat();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"pointChart = { \n canvas.selectAll(\"*\").remove();\n \n if (showGrid) {\n renderCells(canvas);\n }\n \n if (showDots) {\n renderDots(canvas);\n }\n \n if (showLines) {\n renderAllSegments(canvas);\n }\n \n return canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"fontSize = spacing * 0.5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":343,"value":"spacing = Math.min(verticalSpacing, horizontalSpacing);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":341,"value":"horizontalSpacing = width / columns;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":339,"value":"verticalSpacing = height / rows;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":617,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":869,"value":"md`\n### Imported Variables\nThe variables and function below are imported from external packages.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"d3 = require(\"d3@6\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":899,"value":"import {octave, perlin2} from \"@mbostock/perlin-noise\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 32:"$31:body"