|
<!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> |