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/a7495ca3d5b322a6697530feb62fceef to your computer and use it in GitHub Desktop.
Save Fil/a7495ca3d5b322a6697530feb62fceef to your computer and use it in GitHub Desktop.
Painting Manhattan-distance 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.

See also Painting Euclidian 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 = manhattandistance;
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 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!');
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();
if (elapsed > 30000) interval.stop();
});
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment