Skip to content

Instantly share code, notes, and snippets.

@Fil
Last active October 17, 2016 13:49
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Fil/f0fc1cf9afc96b591e3615563ece04cd to your computer and use it in GitHub Desktop.
Save Fil/f0fc1cf9afc96b591e3615563ece04cd to your computer and use it in GitHub Desktop.
Painting Euclidian Voronoi
license: mit

By far the simplest of Voronoi algorithms is to paint pixels according to the color of their closest site. Such a shader will work with any definition of distance, weighted or not. Speed is awfully slow, in O(n*x*y). The results are pixels (canvas), not an abstract layout — we overlay it at the end.

See also Painting Manhattan-distance Voronoi.

<!DOCTYPE html>
<head>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<style>
body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
canvas { margin: 20px; border: solid black 2px; }
</style>
</head>
<body>
<canvas width=600 height=400>
<script>
function manhattandistance(a, b) {
var dx = b[0] - a[0],
dy = b[1] - a[1];
return Math.abs(dx) + Math.abs(dy);
}
function euclideandistance(a, b) {
var dx = b[0] - a[0],
dy = b[1] - a[1];
return dx*dx + dy*dy;
}
var distance = euclideandistance;
var canvas = d3.select('canvas').node(),
context = canvas.getContext("2d"),
width = canvas.width,
height = canvas.height;
var sites = d3.range(400).map(function (d) {
return [width * Math.random(), height * Math.random()];
});
var polygons = d3.voronoi().extent(
[[-1,-1],[width+1,height+1]]
).polygons(sites);
var color = d3.scaleOrdinal(d3.schemeCategory20b);
function drawsites() {
sites.forEach(function (d, i) {
context.lineWidth = 10;
context.beginPath();
context.strokeStyle = color(i);
var x = d[0],
y = d[1];
context.moveTo(x - 5, y);
context.lineTo(x + 5, y);
context.stroke();
context.lineWidth = 4;
context.beginPath();
context.strokeStyle = '#fff';
var x = d[0],
y = d[1];
context.moveTo(x - 2, y);
context.lineTo(x + 2, y);
context.stroke();
});
}
var p = 0;
var interval = d3.interval(function (elapsed) {
var n = 1000;
while (n-- > 0) {
var x = p % width,
y = ((p - x) / width) % height;
p++;
if (p > width * height) {
interval.stop();
console.log('finished!');
drawvoronoi();
break;
} else {
var i = d3.scan(sites.map(function (d) {
return distance(d, [x, y]);
}));
context.beginPath();
context.fillStyle = color(i);
context.rect(x, y, 1, height);
context.fill();
}
}
drawsites();
//drawvoronoi();
if (elapsed > 30000) interval.stop();
});
function drawvoronoi(){
context.lineWidth = 1;
context.beginPath();
for (var i = 0, n = polygons.length; i < n; ++i) drawCell(polygons[i]);
context.strokeStyle = "#fff";
context.stroke();
}
function drawCell(cell) {
if (!cell) return false;
context.moveTo(cell[0][0], cell[0][1]);
for (var j = 1, m = cell.length; j < m; ++j) {
context.lineTo(cell[j][0], cell[j][1]);
}
context.closePath();
return true;
}
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment