25:["$","title",null,{"children":"Marching Squares | Luis Retondaro | Observable"}] 4b:T13c4,function marching_squares (m,level) { let chains = new Set(); var prev = [], curr = []; var iy = 0; var above = []; var width = m[0].length; var height = m.length; for (var ix = 0; ix < width; ix++) { prev[ix] = m[0][ix]; above [ix] = null; } for (var iy = 1; iy < height; iy++) { curr [0] = m [iy][0]; var left = null; for (var ix = 1; ix < width; ix++) { curr [ix] = m [iy][ix]; var nw = prev[ix-1], ne = prev[ix], sw = curr[ix-1], se = curr[ix]; var n = (nw < level) != (ne < level); var w = (nw < level) != (sw < level); var e = (ne < level) != (se < level); var s = (sw < level) != (se < level); var np = n ? Vec ( mapRange (level, nw, ne, ix-1,ix), iy-1) : null; var sp = s ? Vec ( mapRange (level, sw, se, ix-1,ix), iy) : null; var wp = w ? Vec (ix-1, mapRange (level, nw, sw, iy-1,iy)) : null; var ep = e ? Vec (ix, mapRange (level, ne, se, iy-1,iy)) : null; var below = null, right = null; if (s) { if (n) { if (joinSegmentChain (np, sp, above[ix])) { below = above[ix]; } if (!below) { below = [np, sp]; chains.add (below); } } else if (w) { if (joinSegmentChain (wp, sp, left)) { below = left; } if (!below) { below = [wp, sp]; chains.add (below); } } else if (e) { below = right = [ep,sp]; chains.add (right); } else { console.assert (false, "Singleton South"); } } if (e) { if (w) { if (joinSegmentChain (wp, ep, left)) { right = left; } if (!right) { right = [wp, ep]; chains.add (right); } } else if (n) { if (joinSegmentChain (np, ep, above[ix])) { right = above[ix]; } if (!right) { right = [np, ep]; chains.add (right); } } else { console.assert (s, "Singleton East"); } } if (n) { if (w && !e) { if (joinSegmentChain (wp,np,left)) { if (left != above[ix]) { var joined = joinChains (left, above[ix]); if (joined) { for (var i = 1; i < width; i++) { if (i != ix && above [i] == left) { above [i] = joined; } } if (below == left) below = joined; if (right == left) right = joined; chains.delete (left); } } } else if (joinSegmentChain (wp,np,above[ix])) { } else { var seg = [wp, np]; chains.add (seg); } } else { console.assert (s || e, "Singleton North"); } } if (w) { console.assert (n || e || s, "Singleton West"); } above[ix] = below; left = right; } prev = curr; curr = []; } var carray = []; for (let c of chains) { carray.push (c); } for (var iterations = 0, havejoined = true; havejoined; iterations++) { var joinCount = 0; for (var i = 0; i < carray.length; i++) { if (!carray [i]) continue; for (var j = i+1; j < carray.length; j++) { if (!carray[j]) continue; var joined = joinChains (carray[j], carray[i]); if (joined) { chains.delete(carray[j]); carray[j] = null; joinCount++; } } } havejoined = joinCount>0; } var result = []; for (var i = 0; i < carray.length; i++) { if (!carray [i]) continue; var c = new CurveLCR(); c.pts = carray[i]; c.closed = true; result.push(c); } return result; } 4c:T577,class GridSample { // Initializes for a given 2D range constructor (xmin,xmax,ymin,ymax) { this.xmin = xmin; this.xmax = xmax; this.ymin = ymin; this.ymax = ymax; var bigDist = 1e10; this.s = []; for (var i = 0; i < (ymax-ymin); i++) { var row = []; for (var j = 0; j < (xmax-xmin); j++) { row[j] = bigDist; } this.s[i] = row; } } addField (field, imin, jmin, imax, jmax) { let i = imin; let j = jmin let difx = imax-i; let dify = jmax-j; if (difx > field[0].length) i = i + (difx-field[0].length); if (dify > field.length) j = j + (dify-field.length); for (var x = i; x < imax; x++) { for (var y = j; y < jmax; y++) { if (y >=0 && x >= 0 && y < this.ymax && x < this.xmax) { var v = Math.min(this.s[y][x], field[y-j][x-i]); this.s[y][x] = v; } } } } extractField (xmin, xmax, ymin, ymax) { let result = []; for (var i = ymin; i < (ymax); i++) { var row = []; for (var j = xmin; j < (xmax); j++) { row[j-xmin] = this.s[i][j]; } result[i-ymin] = row; } return result; } } 4d:[] 47:{"id":"af0b5403d490b308","slug":"marching-squares","title":"Marching Squares","thumbnail":"8df19f0496d5430f63a43746e8c9129cb6bfb53dd46bbba1db6da588e81bc342","access_level":"public","create_time":"$D2019-07-15T17:33:42.031Z","update_time":"$D2021-07-20T13:36:31.491Z","view_time":null,"first_public_time":"$D2019-07-15T18:00:25.158Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"71e5ea5268419c5a","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":"starter_2024","bio":".","followed_by_you":false,"follows_you":false},"version":186,"publish_version":186,"role":null,"authored":false,"authors":[{"type":"individual","id":"146ee3f34bbcc61d","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":null,"bio":".","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"146ee3f34bbcc61d","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"e35da0991f30f391","slug":"computer-graphics","title":"Computer Graphics","owner":{"id":"71e5ea5268419c5a","login":"lretondaro","name":"Luis Retondaro"}},"type":"notebook","body":{"titling":"auto","title":"Marching Squares","cells":[{"id":0,"value":"md `# Marching Squares`\n\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"md `Marching squares is a classical computer graphics algorithm that generates contours for a two-dimensional scalar field (rectangular array of individual numerical values).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"md ` The idea is to obtain a vector representation of curves delimiting interesting features in m, a matrix that contains a sampling of a scalar field z = f(x,y), stored by rows, i.e. m[i][j] contains f(j,i). `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"md `## The function *marching_squares(m, level)*\n\nReturns an array of curves that approximate f(x,y) = level`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"$4b","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"md `## The function *map(value, a, b, c, d)*\n\nLinearly maps value from the range (a..b) to (c..d)\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"function mapRange (value, a, b, c, d) {\n // first map value from (a..b) to (0..1)\n value = (value - a) / (b - a);\n // then map it from (0..1) to (c..d) and return it\n return c + value * (d - c);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"md `## The function *joinSegmentChain(a,b,p)* \n\nJoins a new segment a-b to chain p.\nReturns the modified chain if successful, or false otherwise.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"function joinSegmentChain (a, b, p) {\n if (!p) return false;\n var c = p[0], d = p[p.length-1];\n if (a.x == c.x && a.y == c.y) {\n p.reverse(); p.push (b); return p;\n }\n if (b.x == c.x && b.y == c.y) {\n p.reverse(); p.push (a); return p;\n }\n if (a.x == d.x && a.y == d.y) {\n p.push (b); return p;\n }\n if (b.x == d.x && b.y == d.y) {\n p.push (a); return p;\n }\n return false;\n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"md `## The function *joinChains(l,p)*\n\nJoins chain l to chain p if they have a common endpoint, returning the modified chain p. Otherwise, returns false`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"joinChains = function (l, p) {\n if (!l) return false;\n if (!p) return false;\n console.assert (l!=p, \"Can't join chain with itself\");\n var a = l[0], b = l[l.length-1];\n var c = p[0], d = p[p.length-1];\n if (a.x == c.x && a.y == c.y) {\n p.reverse(); \n }\n else if (b.x == c.x && b.y == c.y) {\n p.reverse(); l.reverse(); \n }\n else if (a.x == d.x && a.y == d.y) {\n }\n else if (b.x == d.x && b.y == d.y) {\n l.reverse();\n }\n else {\n return false;\n }\n for (var i = 1; i < l.length; i++) {\n p.push(l[i]);\n }\n return p;\n}\n\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"md `## The class GridSample\n\nRepresents a grid sampling of some field\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"$4c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"class MasterGrid { //test\n\n // Initializes for a given 2D range\n constructor (xmin,xmax,ymin,ymax) {\n this.xmin = xmin;\n this.xmax = xmax;\n this.ymin = ymin;\n this.ymax = ymax;\n var bigDist = 1e10; // A Big number\n this.s = [];\n for (var i = 0; i < (ymax-ymin); i++) {\n var row = [];\n for (var j = 0; j < (xmax-xmin); j++) {\n row[j] = bigDist;\n }\n this.s[i] = row;\n }\n }\n \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"md `## Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"import {CurveLCR} from \"@lretondaro/curve\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"import { Vector, Vec} from \"@esperanc/2d-geometry-utils\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4d","stdlib":"1"}} 24:null