30: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; }31: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; }32:[] 2e:{"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"},{"id":216,"value":"viewof reset = html`