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