Skip to content

Instantly share code, notes, and snippets.

@Fil
Last active September 9, 2017 02:09
Show Gist options
  • Save Fil/ef8e0be0147a69bb1d2adc77c66a80b6 to your computer and use it in GitHub Desktop.
Save Fil/ef8e0be0147a69bb1d2adc77c66a80b6 to your computer and use it in GitHub Desktop.
K-Means as a force
license: gpl-3.0
height: 960
<!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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment