| license: mit |
This is an experiment in moving and shaping voronoi polygons to normalize the dispersion of points. The idea arose while mapping emergency calls logged by the San Francisco Fire Department, and was also inspired by Noah Veltman's Voronoi relaxation.
To do this, I kind of combined aspects of Lloyd's algorithm and k-means clustering.
forked from alexmacy's block: K-Means Voronoi Relaxation
| <!DOCTYPE html> | |
| <html lang="en"> | |
| <head> | |
| <meta charset="utf-8" /> | |
| <style> | |
| body {margin:0;} | |
| polygon {stroke: black; fill-opacity: .5;} | |
| circle {stroke: none; fill-opacity: .5;} | |
| text {stroke: black;} | |
| </style> | |
| <script src="https://d3js.org/d3.v4.min.js"></script> | |
| </head> | |
| <body> | |
| <svg></svg> | |
| <div> | |
| <button onclick="stop = false; start()">start</button> | |
| <button onclick="stop = true">stop</button> | |
| <button onclick="stop = true; redraw()">redraw</button> | |
| <b id="specs"></b><b id="average"></b><b id="deviation"></b><b id="steps"> - Steps: 0</b> | |
| </div> | |
| </body> | |
| <script> | |
| var width = 960, | |
| height = 470; | |
| var stop = false; | |
| var pointCount = 20000, | |
| polygonCount = 100, | |
| steps = 0; | |
| var voronoi = d3.voronoi().extent([[0, 0],[width, height]]); | |
| var colorScale = d3.scaleLinear().range(["white", "green", "black"]) | |
| var pointCoords = randomPoints(pointCount), | |
| voronoiPoints = randomPoints(polygonCount), | |
| populations = []; | |
| d3.select("#specs").html(" " + d3.format(",")(pointCount) + " points, " + polygonCount + " polygons") | |
| d3.select("#average").html(" - Average: " + pointCount/polygonCount) | |
| var svg = d3.select("svg") | |
| .attr("width", width) | |
| .attr("height", height) | |
| var points = svg.selectAll("circle") | |
| .data(pointCoords) | |
| .enter().append("circle") | |
| .attr("r", 1) | |
| .attr("cx", function(d) {return d[0]}) | |
| .attr("cy", function(d) {return d[1]}) | |
| var polygons = svg.selectAll("polygon") | |
| .data(voronoi(voronoiPoints).polygons()) | |
| .enter().append("polygon") | |
| .attr("points", function(d) {return d}) | |
| var centroids = svg.selectAll("text") | |
| .data(voronoiPoints) | |
| .enter().append("text") | |
| .attr("x", function(d) {return d[0]}) | |
| .attr("y", function(d) {return d[1]}) | |
| .attr("text-anchor", "middle") | |
| voronoiPoints.forEach(function(d, i) {return populations[i] = [];}) | |
| var diagram = d3.voronoi()(voronoiPoints); | |
| pointCoords.forEach(function(d) { | |
| populations[diagram.find(d[0],d[1]).index].push(d);} | |
| ) | |
| d3.select("#deviation").html(" - Deviation: " + d3.deviation(populations, function(d) {return d.length}).toFixed(2)) | |
| var extent = d3.extent(populations, function(d) {return d.length}); | |
| colorScale.domain([extent[0],pointCount/polygonCount,extent[1]]) | |
| centroids.html(function(d, i) {return populations[i].length}) | |
| polygons.attr("fill", function(d, i) {return colorScale(populations[i].length)}) | |
| function start(){ | |
| if (stop) { | |
| console.log("stopping") | |
| return stop = false; | |
| } | |
| groupPoints(); | |
| var stopVal = 0; | |
| for (i=0; i<voronoiPoints.length; i++) { | |
| var newPoint = getNewCenter(i) | |
| stopVal += (voronoiPoints[i][0] == newPoint[0] && voronoiPoints[i][1] == newPoint[1]) ? 1 : 0; | |
| voronoiPoints[i] = newPoint; | |
| if (stopVal == voronoiPoints.length) {stop = true}; | |
| } | |
| if (stop) { | |
| console.log("stopping") | |
| return stop = false; | |
| } | |
| d3.select("#steps").html(" - Steps: " + ++steps) | |
| centroids.data(voronoiPoints) | |
| .attr("x", function(d) {return d[0]}) | |
| .attr("y", function(d) {return d[1]}) | |
| polygons.data(voronoi(voronoiPoints).polygons()) | |
| .attr("points", function(d) {return d}) | |
| d3.timeout(start, 50); | |
| } | |
| function groupPoints() { | |
| voronoiPoints.forEach(function(d, i) {return populations[i] = [];}) | |
| var diagram = d3.voronoi()(voronoiPoints); | |
| pointCoords.forEach(function(d) { | |
| populations[diagram.find(d[0],d[1]).index].push(d);} | |
| ) | |
| d3.select("#deviation").html(" - Deviation: " + d3.deviation(populations, function(d) {return d.length}).toFixed(2)) | |
| centroids.html(function(d, i) {return populations[i].length}) | |
| polygons.attr("fill", function(d, i) {return colorScale(populations[i].length)}) | |
| } | |
| function getNewCenter(n) { | |
| var centerX = d3.sum(populations[n], function(d) {return d[0]})/populations[n].length; | |
| var centerY = d3.sum(populations[n], function(d) {return d[1]})/populations[n].length; | |
| return [centerX, centerY]; | |
| } | |
| function randomPoints(count) { | |
| return d3.range(count) | |
| .map(function() { | |
| var angle = Math.random() * 2 * Math.PI, | |
| r = Math.random(); | |
| return [r * Math.sin(angle) * width/2 + width/2 + Math.round(1-2*Math.random()) * 280, r * Math.cos(angle) * height/2 + height/2];}) | |
| } | |
| function redraw() { | |
| voronoiPoints = randomPoints(polygonCount); | |
| steps = 0; | |
| polygons.data(voronoi(voronoiPoints).polygons()) | |
| .attr("points", function(d) {return d}) | |
| centroids.data(voronoiPoints) | |
| .attr("x", function(d) {return d[0]}) | |
| .attr("y", function(d) {return d[1]}) | |
| d3.select("#steps").html(" - Iteration: " + steps) | |
| groupPoints(); | |
| } | |
| </script> |