K-Means as a force

Computing K-Means within a d3.forceSimulation loop.

Forked from mbostock's block: Collision Detection

<!DOCTYPE html>
<meta charset="utf-8">
<canvas width="960" height="960"></canvas>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>

var canvas = document.querySelector("canvas"),
    context = canvas.getContext("2d"),
    width = canvas.width,
    height = canvas.height,
    tau = 2 * Math.PI;

var nodes = d3.range(1000).map(function(i) {
  return {
    r: Math.random() * 14 + 4
  };
});

var K = 20,
      centers = d3.range(K).map(i => [0,0]),
      colorscale = d3.scaleOrdinal(d3.schemeCategory20c);
  
var simulation = d3.forceSimulation(nodes)
    .velocityDecay(0.2)
    .force("x", d3.forceX().strength(0.002))
    .force("y", d3.forceY().strength(0.002))
    .force('kmeans', function(){

// a central point to re-init empty groups
          var m = [d3.mean(centers.map(d => d[0] || 0)),
                   d3.mean(centers.map(d => d[1] || 0))];
      
          // the order is important: move the centers before re-making the groups
          // so that the centers follow the general movement and keep "their"
          // points, instead of having points pass through them

// 1. move K-centers towards the barycenter of their group
          centers.forEach((c,i) => {
            c[0] = d3.mean(nodes.filter(d => d.group == i).map(d => d.x)) || m[0]; 
            c[1] = d3.mean(nodes.filter(d => d.group == i).map(d => d.y)) || m[1]; 
          });

// 2. group each point according to its closest K-center
          nodes.forEach(d => { 
             d.group = d3.scan(centers.map(c => {
               var dx = d.x - c[0],
                   dy = d.y - c[1];
               return  (dx*dx + dy*dy);
             }));
          });
      
        }
      )

.force("collide", d3.forceCollide().radius(function(d) { return d.r + 0.5; }).iterations(2))
/*
    .force("circle", function(alpha){
      nodes.forEach(d => {
        let k = Math.sqrt(d.y*d.y + d.x * d.x);
        d.vx += d.y/k * 5 * alpha;
        d.vy -= d.x/k * 5 * alpha;
      })
    })
    */
    .on("tick", ticked);

function ticked() {
  context.clearRect(0, 0, width, height);
  context.save();
  context.translate(width / 2, height / 2);

nodes.forEach(function(d) {
  context.beginPath();

context.moveTo(d.x + d.r, d.y);
    context.arc(d.x, d.y, d.r, 0, tau); 
  context.fillStyle = colorscale(d.group);
  context.fill();
  context.strokeStyle = "#333";
  context.stroke();

});

context.restore();
}

</script>

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