2c:null 2d:["$","title",null,{"children":"VoronoiMap2D | Fil | Observable"}] 32:T638,{ const context = DOM.context2d(width, height, 1); const isSite = new Uint8Array(width * height); function draw() { const timer = performance.now(); isSite.fill(0); for (const [x, y] of sites) isSite[x + width * y] = 1; const map = computeVoronoiMap(width, height, isSite); const time = performance.now() - timer; const data = context.getImageData(0, 0, width, height); let rgb, prev; for (let i = 0; i < map.length; i++) { if (display) { context.fillStyle = i === map[i] ? "white" : colorDistance( Math.hypot( (i % width) - (map[i] % width), Math.floor(i / width) - Math.floor(map[i] / width) ) ); } else { context.fillStyle = i === map[i] ? "white" : color(map[i]); } if (context.fillStyle !== prev) { prev = context.fillStyle; rgb = d3.rgb(context.fillStyle); data.data[4 * i + 0] = rgb.r; data.data[4 * i + 1] = rgb.g; data.data[4 * i + 2] = rgb.b; } else { data.data[4 * i + 0] = rgb.r; data.data[4 * i + 1] = rgb.g; data.data[4 * i + 2] = rgb.b; } data.data[4 * i + 3] = 255; } context.putImageData(data, 0, 0); context.clearRect(0, 0, 150, 14); context.fillStyle = "black"; context.fillText(time.toFixed(2) + "ms", 10, 10); } draw(); d3.select(context.canvas).on("click", function() { sites.push(d3.mouse(this).map(Math.round)); draw(); }); return context.canvas; }33:Tafd,function computeVoronoiMap(w, h, isSite) { const n = w * h, voromap = new Int32Array(n), infty = n + 1; function index(x, y) { return x + y * w; } function getX(pos) { return pos % w; } function getY(pos) { return Math.floor(pos / w); } // At point (x,y) which one between siteA and siteB is the closest? function closest(x, y, siteA, siteB) { const sAx = getX(siteA), sAy = getY(siteA), sBx = getX(siteB), sBy = getY(siteB); return ( (x - sAx) * (x - sAx) + (y - sAy) * (y - sAy) > (x - sBx) * (x - sBx) + (y - sBy) * (y - sBy) ); } // On a vertical slab "slabX", do sites A and C hide the site B ? // (if true, the cell of C does not intersect the slab) function hiddenBy(A, B, C, slabX) { const sAx = getX(A), sAy = getY(A), sBx = getX(B), sBy = getY(B), sCx = getX(C), sCy = getY(C), a = sBy - sAy, b = sCy - sBy, c = a + b, dA = (sAx - slabX) * (sAx - slabX), dB = (sBx - slabX) * (sBx - slabX), dC = (sCx - slabX) * (sCx - slabX); return c * dB - b * dA - a * dC - a * b * c > 0; } // First scan along the rows // #pragma omp parallel for schedule(dynamic) for (let y = 0; y < h; ++y) { let prev = infty; let firstSite = true; for (let x = 0; x < w; ++x) { voromap[index(x, y)] = Math.min(infty, index(prev, y)); if (isSite[index(x, y)]) { const site = index(x, y); voromap[index(x, y)] = site; if (firstSite) { firstSite = false; for (let xx = 0; xx < x; ++xx) voromap[index(xx, y)] = site; } // rewrite else for (let xx = Math.floor((prev + x) / 2) + 1; xx < x; ++xx) voromap[index(xx, y)] = site; prev = x; } } } // Second scan along the columns // #pragma omp parallel for schedule(dynamic) for (let x = 0; x < w; ++x) { // Looking for the sites with non empty intersection between // their voronoi cell and the vertical slab at "x" var sites = []; for (let y = 0; y < h; ++y) if (voromap[index(x, y)] != infty) { while ( sites.length >= 2 && hiddenBy( sites[sites.length - 2], sites[sites.length - 1], voromap[index(x, y)], x ) ) sites.pop(); sites.push(voromap[index(x, y)]); } // Rewrite let pos = 0; if (sites.length == 1) for (let y = 0; y < h; ++y) voromap[index(x, y)] = sites[0]; else for (let y = 0; y < h; ++y) { while ( pos < sites.length - 1 && closest(x, y, sites[pos], sites[pos + 1]) ) pos++; voromap[index(x, y)] = sites[pos]; } } return voromap; }34:[] 30:{"id":"513cb26d387f3545","slug":"voronoimap2d","title":"VoronoiMap2D","thumbnail":"8d275f871f632807d39860b2538c572e642043b505f4d00cb06fa4284c8a3dcb","access_level":"public","create_time":"$D2020-07-13T18:35:23.137Z","update_time":"$D2020-07-14T21:02:41.096Z","view_time":null,"first_public_time":"$D2020-07-14T20:06:03.405Z","fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"da2a32154638c457","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":"starter_2024"},"version":284,"publish_version":284,"role":null,"authored":false,"authors":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}],"members":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null,"role":"editor"}],"comments":[{"id":"cfb68dc0b2887545","reply_to_id":null,"content":"thanks for the resource! I've been looking for cool ideas to play with WASM, I think I'll try port this code using pthreads https://emscripten.org/docs/porting/pthreads.html just as an experiment and see how it performs!","create_time":"$D2020-07-16T19:06:01.430Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"06bc2aaa9d8c4a54","login":"radames","name":"Radamés Ajna","avatar_url":"https://avatars-next.observableusercontent.com/7e61199ed2efe90aec8d897ac8b17a3fd0a129bff12a46a4048ddd0f73a2c43e","tier":null}}],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":2,"collection":{"id":"7f51a09dd1333537","slug":"algorithms","title":"Algorithms","owner":{"id":"da2a32154638c457","login":"fil","name":"Fil"}},"type":"notebook","body":{"title":"VoronoiMap2D","cells":[{"id":0,"value":"md`# VoronoiMap2D\n\nJavaScript port of [@dcoeurjo/VoronoiMap2D](https://github.com/dcoeurjo/VoronoiMap2D/blob/master/example.cpp), without the parallelism (darn JS!). For a primer on the algorithm, see David Coeurjolly’s [write-up](https://perso.liris.cnrs.fr/david.coeurjolly/courses/voronoimap2d/).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":216,"value":"viewof reset = html`