D3
OG
Old school D3 from simpler times
All examples
By author
By category
About
mbostock
Full window
Github gist
Mitchell’s Best-Candidate III
<!DOCTYPE html> <meta charset="utf-8"> <body> <script src="//d3js.org/d3.v3.min.js"></script> <script> var width = 960, height = 500; var sample = bestCandidateSampler(width, height, 10, 3000); var svg = d3.select("body").append("svg") .attr("width", width) .attr("height", height); d3.timer(function() { for (var i = 0; i < 10; ++i) { var s = sample(); if (!s) return true; svg.append("circle") .attr("cx", s[0]) .attr("cy", s[1]) .attr("r", 0) .transition() .attr("r", 2); } }); function bestCandidateSampler(width, height, numCandidates, numSamplesMax) { var numSamples = 0; var quadtree = d3.geom.quadtree() .extent([[0, 0], [width, height]]) ([[Math.random() * width, Math.random() * height]]); return function() { if (++numSamples > numSamplesMax) return; var bestCandidate, bestDistance = 0; for (var i = 0; i < numCandidates; ++i) { var c = [Math.random() * width, Math.random() * height], d = distance(search(c[0], c[1]), c); if (d > bestDistance) { bestDistance = d; bestCandidate = c; } } quadtree.add(bestCandidate); return bestCandidate; }; function distance(a, b) { var dx = a[0] - b[0], dy = a[1] - b[1]; return dx * dx + dy * dy; }; // Find the closest node to the specified point. function search(x, y) { var x0 = 0, y0 = 0, x3 = width, y3 = width, minDistance2 = Infinity, closestPoint; (function find(node, x1, y1, x2, y2) { var point; // stop searching if this cell can’t contain a closer node if (x1 > x3 || y1 > y3 || x2 < x0 || y2 < y0) return; // visit this point if (point = node.point) { var dx = x - point[0], dy = y - point[1], distance2 = dx * dx + dy * dy; if (distance2 < minDistance2) { var distance = Math.sqrt(minDistance2 = distance2); x0 = x - distance, y0 = y - distance; x3 = x + distance, y3 = y + distance; closestPoint = point; } } // bisect the current node var children = node.nodes, xm = (x1 + x2) * .5, ym = (y1 + y2) * .5, right = x > xm, below = y > ym; // visit closest cell first if (node = children[below << 1 | right]) find(node, right ? xm : x1, below ? ym : y1, right ? x2 : xm, below ? y2 : ym); if (node = children[below << 1 | !right]) find(node, right ? x1 : xm, below ? ym : y1, right ? xm : x2, below ? y2 : ym); if (node = children[!below << 1 | right]) find(node, right ? xm : x1, below ? y1 : ym, right ? x2 : xm, below ? ym : y2); if (node = children[!below << 1 | !right]) find(node, right ? x1 : xm, below ? y1 : ym, right ? xm : x2, below ? ym : y2); })(quadtree, x0, y0, x3, y3); return closestPoint; } } </script>
https://d3js.org/d3.v3.min.js