31:T42d,function naiveCircleGenerator(maxRadius, padding,x0, x1, y0, y1) { // No optimisation, pick anywhere in the plane from (x0,y0) to (x1,y1) const circles = []; return function(k) { var bestX, bestY, bestDistance = 0; // Generate k samples and return the furthest from any existing circle. for (let i = 0; i < k; ++i) { const x = (x1 - x0) * Math.random() + x0; const y = (y1 - y0) * Math.random() + y0; var minDistance = maxRadius; for (let j = 0; j < circles.length && minDistance > 0; ++j) { const dSquared = distanceSquared(x, y, circles[j][0], circles[j][1]); if (dSquared < circles[j][2] * circles[j][2]) minDistance = 0; // Inside an existing circle. const d = Math.sqrt(dSquared) - circles[j][2]; if (d < minDistance) minDistance = d; } // If that's the best one so far then update best... if (minDistance > bestDistance) bestX = x, bestY = y, bestDistance = minDistance; } const best = [bestX, bestY, bestDistance] circles.push(best); return best; } }32:T483,canvas = { await visibility(); replay1; const t1 = performance.now(); const context = DOM.context2d(width, height); context.canvas.style.background = 'hsl(216deg 100% 13%)'; const newCircle = naiveCircleGenerator( config.maxRadius, config.padding, config.margin.left, width - config.margin.right, config.margin.top, height - config.margin.bottom ) var n = config.nCircles; var tries = config.failAfter; var k = config.nCandidates; while (n > 0 && tries > 0) { const c = newCircle(config.nCandidates); if (c[2] > config.padding) { context.globalAlpha = 1; context.fillStyle = config.cm(Math.random()) context.beginPath(); context.arc(c[0], c[1], c[2] - config.padding, 0, 2 * Math.PI, false) context.fill() n--; } else { tries--; } if (n % config.nCirclesPerFrame === 0) yield context.canvas; if (k < 100) k *= 1.02; } if (tries == 0) console.log('ran out of spaces to put circles') if (n == 0) console.log('ran out of circles to place') yield context.canvas; const t2 = performance.now(); mutable timer1 = t2 - t1; }33:T678,function quadTreeCircleGenerator(maxRadius, padding,x0, x1, y0, y1) { const quadtree = d3.quadtree() .extent([[x0,y0],[x1,y1]]) const searchRadius = maxRadius * 2; function f(k) { var bestX, bestY, bestDistance = 0; // Generate k samples and return the furthest from any existing circle. for (let i = 0; i < k; ++i) { const x = (x1 - x0) * Math.random() + x0; const y = (y1 - y0) * Math.random() + y0; const xmin = x - searchRadius; const xmax = x + searchRadius; const ymin = y - searchRadius; const ymax = y + searchRadius; var minDistance = maxRadius; // Visit all nodes in the tree within our search radius. quadtree.visit((node, x1, y1, x2, y2) => { //console.log({quad}) if (!node.length) { var p = node.data; var dsquared = distanceSquared(x, y, p[0], p[1]); if (dsquared < p[2] * p[2] ) return minDistance = 0, true;// Within a circle. Can stop early since this sample is not viable. var d = Math.sqrt(dsquared) - p[2]; if (d < minDistance) minDistance = d; // Store radius of new circle. } //Return true for all nodes that DONT need to be visited. return !minDistance || x1 >= xmax || x2 <= xmin || y1 >= ymax || y2 <= ymin; }); // If that's the best one so far then update best... if ((minDistance > bestDistance) && (minDistance > 0)) { bestX = x; bestY = y; bestDistance = minDistance; } } const best = [bestX, bestY, bestDistance] quadtree.add(best) return best; } f.quadtree = quadtree; return f; }34:T489,canvas2 = { await visibility(); const t1 = performance.now(); replay2; const context = DOM.context2d(width, height); context.canvas.style.background = 'hsl(216deg 100% 13%)'; const newCircle = quadTreeCircleGenerator( config.maxRadius, config.padding, config.margin.left, width - config.margin.right, config.margin.top, height - config.margin.bottom ) var n = config.nCircles; var tries = config.failAfter; var k = config.nCandidates; while (n > 0 && tries > 0) { const c = newCircle(k); if (c[2] > config.padding) { context.globalAlpha = 1; context.fillStyle = config.cm(Math.random()) context.beginPath(); context.arc(c[0], c[1], c[2] - config.padding, 0, 2 * Math.PI, false) context.fill() n--; } else { tries--; } if (n % config.nCirclesPerFrame === 0) yield context.canvas; if (k < 500) k *= 1.01; } if (tries == 0) console.log('ran out of spaces to put circles') if (n == 0) console.log('ran out of circles to place') yield context.canvas; const t2 = performance.now(); mutable timer2 = t2 - t1; newCircle.quadtree }35:T44f,## 🤔 That Was supposed to be faster... Odd, our quadtree was supposed to require checking fewer circles for overlaps. Why was it so much slower? It turns out that my naive circle generator was _already_ fairly efficient. Because I opted to fill with the largest circles possible and fill in the gaps with progressively smaller ones, big circles appear first in the list. As we fill in more of the canvas, most guesses are likely to be within a big (and thus _early_) circle in the list and so will terminate before comparing to the whole list of circles. The quadtree's method for generating guesses is worse than this - it's only guaranteed to be faster than checking _every_ circle, and my naive method usually only has to check the first few for a lot of guesses. We can test this explanation - we should see an advantage for the quadtree generator if we were trying to place lots of circles of a similar size. In that case our naive method wouldn't have the benefit of checking large circles that covered a lot of the canvas first baked in. Let's try that out. ### Small Circles - Naive36:T463,canvas3 = { await visibility(); const t1 = performance.now(); replay3; const context = DOM.context2d(width, height); context.canvas.style.background = 'hsl(216deg 100% 13%)'; const newCircle = naiveCircleGenerator( 20, config.padding, config.margin.left, width - config.margin.right, config.margin.top, height - config.margin.bottom ) var n = config.nCircles; var tries = config.failAfter; var k = config.nCandidates; while (n > 0 && tries > 0) { const c = newCircle(k); if (c[2] > config.padding) { context.globalAlpha = 1; context.fillStyle = config.cm(Math.random()) context.beginPath(); context.arc(c[0], c[1], c[2] - config.padding, 0, 2 * Math.PI, false) context.fill() n--; } else { tries--; } if (n % config.nCirclesPerFrame === 0) yield context.canvas; if (k < 500) k *= 1.01; } if (tries == 0) console.log('ran out of spaces to put circles') if (n == 0) console.log('ran out of circles to place') yield context.canvas; const t2 = performance.now(); mutable timer3 = t2 - t1; }37:T466,canvas4 = { await visibility(); const t1 = performance.now(); replay4; const context = DOM.context2d(width, height); context.canvas.style.background = 'hsl(216deg 100% 13%)'; const newCircle = quadTreeCircleGenerator( 20, config.padding, config.margin.left, width - config.margin.right, config.margin.top, height - config.margin.bottom ) var n = config.nCircles; var tries = config.failAfter; var k = config.nCandidates; while (n > 0 && tries > 0) { const c = newCircle(k); if (c[2] > config.padding) { context.globalAlpha = 1; context.fillStyle = config.cm(Math.random()) context.beginPath(); context.arc(c[0], c[1], c[2] - config.padding, 0, 2 * Math.PI, false) context.fill() n--; } else { tries--; } if (n % config.nCirclesPerFrame === 0) yield context.canvas; if (k < 500) k *= 1.01; } if (tries == 0) console.log('ran out of spaces to put circles') if (n == 0) console.log('ran out of circles to place') yield context.canvas; const t2 = performance.now(); mutable timer4 = t2 - t1; }38:[] 2f:{"title":"Mitchell's Best Candidate Algorithm","cells":[{"id":0,"value":"# Mitchell's Best Candidate Algorithm\n\nLearning from Mike Bostock's [gist](https://gist.github.com/mbostock/1893974).\n\n> Mitchell’s best-candidate algorithm generates a new random sample by creating k candidate samples and picking the best of k. Here the “best” sample is defined as the sample that is farthest away from previous samples. The algorithm approximates Poisson-disc sampling, producing a much more natural appearance (better blue noise spectral characteristics) than uniform random sampling.","pinned":false,"hidden":false,"mode":"md"},{"id":224,"value":"I wanted to play with different algorithms for placing circles that don't overlap. My first, naive circle generator is pretty inefficient. It just tries random candidate places until it finds one a circle will fit in. ","pinned":false,"hidden":false,"mode":"md"},{"id":98,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":275,"value":"viewof replay1 = Inputs.button(\"replay\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":227,"value":"That took ${d3.format('.2f')(timer1/1000)} seconds to render.\n\nNot bad, but can we write a more efficient circle generator for finding empty spots with d3-quadtree? This will limit the number of circles we have to compare against for each candidate.","pinned":false,"hidden":false,"mode":"md"},{"id":230,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":283,"value":"viewof replay2 = Inputs.button(\"replay\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":234,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":356,"value":"Took ${d3.format('.2f')(timer2/1000)} seconds to render","pinned":false,"hidden":false,"mode":"md"},{"id":459,"value":"$35","pinned":false,"hidden":false,"mode":"md"},{"id":582,"value":"viewof replay3 = Inputs.button(\"replay\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":569,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":577,"value":"Took ${d3.format('.2f')(timer3/1000)} seconds to render\n\n## Small Circles - Quadtree","pinned":false,"hidden":false,"mode":"md"},{"id":588,"value":"viewof replay4 = Inputs.button(\"replay\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":591,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":596,"value":"Took ${d3.format('.2f')(timer4/1000)} seconds to render.\n\nThere we go. The quadtree method is faster when our naive method ends up checking most circles.","pinned":false,"hidden":false,"mode":"md"},{"id":427,"value":"## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"height = width / 2","pinned":false,"hidden":false,"mode":"ojs"},{"id":364,"value":"mutable timer1 = undefined;","pinned":false,"hidden":false,"mode":"ojs"},{"id":353,"value":"mutable timer2 = undefined;","pinned":false,"hidden":false,"mode":"ojs"},{"id":570,"value":"mutable timer3 = undefined;","pinned":false,"hidden":false,"mode":"ojs"},{"id":586,"value":"mutable timer4 = undefined;","pinned":false,"hidden":false,"mode":"ojs"},{"id":294,"value":"config = {\n const maxRadius = height / 3;\n return {\n maxRadius,\n padding: 1,\n margin: {top: -maxRadius, right: -maxRadius, bottom: -maxRadius, left: -maxRadius},\n nCircles: 1000,\n nCandidates: 100,\n nCirclesPerFrame:100,\n failAfter: 1000,\n cm: d3.scaleSequential().interpolator(d3.interpolateSpectral).domain([0, 1])\n } \n}\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":527,"value":"function distanceSquared(x0,y0,x1,y1) {\n return (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)\n}","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W38","stdlib":"1","titling":"auto"}