Computing K-Means within a d3.forceSimulation loop.
Forked from mbostock's block: Collision Detection
Last active
September 9, 2017 02:09
-
-
Save Fil/ef8e0be0147a69bb1d2adc77c66a80b6 to your computer and use it in GitHub Desktop.
K-Means as a force
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| license: gpl-3.0 | |
| height: 960 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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