K-Means Voronoi Relaxation

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.

<!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] = [];})

pointCoords.forEach(function(d) {populations[findClosest(d)].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] = [];})

pointCoords.forEach(function(d) {populations[findClosest(d)].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 randomPoints(count) {
        return d3.range(count)
            .map(function() {return [Math.random() * width, Math.random() * height];})    
    }

function findClosest(coords) {      
        var closestDist = Infinity,
            closestPoint;

for (i=0; i<voronoiPoints.length; i++) {
            var thisDist = calcDistance(coords, voronoiPoints[i]);
            if (thisDist < closestDist) {
                closestDist = thisDist;
                closestPoint = i;
            }
        }

function calcDistance(coord1, coord2) {
            var distX = coord2[0] - coord1[0];
            var distY = coord2[1] - coord1[1];
            return Math.sqrt(distX * distX + distY * distY);
        }

return closestPoint
    }

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>

https://d3js.org/d3.v4.min.js