Skip to content

Instantly share code, notes, and snippets.

@mbostock

mbostock/.block

Last active February 9, 2016 01:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save mbostock/42b6096fe66e978a3b77 to your computer and use it in GitHub Desktop.
Save mbostock/42b6096fe66e978a3b77 to your computer and use it in GitHub Desktop.
Download ZIP
Mitchell’s Best-Candidate IV
Raw
.block
license: gpl-3.0
Raw
README.md
Raw
index.html
<!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, 10000),
samples = [],
s;
while (s = sample()) samples.push(s);
var voronoi = d3.geom.voronoi()
.clipExtent([[0, 0], [width, height]]);
var canvas = d3.select("body").append("canvas")
.attr("width", width)
.attr("height", height);
var context = canvas.node().getContext("2d");
var image = new Image;
image.src = "starry-night.jpg";
image.onload = start;
function start() {
context.drawImage(image, 0, 0);
image = context.getImageData(0, 0, width, height);
voronoi(samples).forEach(function(cell) {
var x = Math.floor(cell.point[0]),
y = Math.floor(cell.point[1]),
i = (y * width + x) << 2;
context.fillStyle = d3.rgb(image.data[i + 0], image.data[i + 1], image.data[i + 2]) + "";
context.beginPath();
context.moveTo(cell[0][0], cell[0][1]);
for (var i = 1, n = cell.length; i < n; ++i) context.lineTo(cell[i][0], cell[i][1]);
context.closePath();
context.fill();
});
}
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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment