Skip to content

Instantly share code, notes, and snippets.

@mbostock
Forked from mbostock/.block
Last active April 24, 2023 22:16
Show Gist options
  • Save mbostock/7881887 to your computer and use it in GitHub Desktop.
Save mbostock/7881887 to your computer and use it in GitHub Desktop.
Clustered Force Layout III
license: gpl-3.0

This variation of a clustered force layout uses an entry transition and careful initialization to minimize distracting jitter as the force simulation converges on a stable layout.

By default, D3’s force layout randomly initializes node positions. You can prevent this by setting each node’s x and y properties before starting the layout. In this example, because custom forces cluster nodes by color, most of the initial jitter is caused by the initial random placement overlapping clusters. We can reduce the jitter by initially placing nodes of the same color near other.

The number of clusters in this example is defined by the variable m; the local variable i is the node’s cluster number. To initialize clusters in a circle of radius 200px around the canvas center, we can define x and y like so:

x: Math.cos(i / m * 2 * Math.PI) * 200 + width / 2 + Math.random(),
y: Math.sin(i / m * 2 * Math.PI) * 200 + height / 2 + Math.random()

Each node is slightly offset from the corresponding cluster’s center using Math.random. Without this offset, same-colored nodes would be coincident, which would cause divide-by-zero problems for our custom forces.

This initialization strategy is arbitrary but effective. Many other approaches would work, such as D3’s circle-packing layout, so feel free to experiment! A good strategy is one that is simple to implement, accelerates convergence, and avoids undesirable artifacts on the final layout. For example, a slightly simpler strategy is to initialize each cluster’s x-position along a line. However, this causes striations in the final layout.

As the force layout converges, its internal temperature cools; nodes move more slowly as the layout stabilizes. We can further reduce jitter by delaying the second custom force — collision prevention. This is done using a simple transition:

node.transition()
    .duration(750)
    .delay(function(d, i) { return i * 5; })
    .attrTween("r", function(d) {
      var i = d3.interpolate(0, d.radius);
      return function(t) { return d.radius = i(t); };
    });

As the circles expand, the displayed radius (the "r" attribute) increases along with the internal radius data property that is used by the collision detection force.

<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>
var width = 960,
height = 500,
padding = 1.5, // separation between same-color nodes
clusterPadding = 6, // separation between different-color nodes
maxRadius = 12;
var n = 200, // total number of nodes
m = 10; // number of distinct clusters
var color = d3.scale.category10()
.domain(d3.range(m));
// The largest node for each cluster.
var clusters = new Array(m);
var nodes = d3.range(n).map(function() {
var i = Math.floor(Math.random() * m),
r = Math.sqrt((i + 1) / m * -Math.log(Math.random())) * maxRadius,
d = {
cluster: i,
radius: r,
x: Math.cos(i / m * 2 * Math.PI) * 200 + width / 2 + Math.random(),
y: Math.sin(i / m * 2 * Math.PI) * 200 + height / 2 + Math.random()
};
if (!clusters[i] || (r > clusters[i].radius)) clusters[i] = d;
return d;
});
var force = d3.layout.force()
.nodes(nodes)
.size([width, height])
.gravity(.02)
.charge(0)
.on("tick", tick)
.start();
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var node = svg.selectAll("circle")
.data(nodes)
.enter().append("circle")
.style("fill", function(d) { return color(d.cluster); })
.call(force.drag);
node.transition()
.duration(750)
.delay(function(d, i) { return i * 5; })
.attrTween("r", function(d) {
var i = d3.interpolate(0, d.radius);
return function(t) { return d.radius = i(t); };
});
function tick(e) {
node
.each(cluster(10 * e.alpha * e.alpha))
.each(collide(.5))
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
}
// Move d to be adjacent to the cluster node.
function cluster(alpha) {
return function(d) {
var cluster = clusters[d.cluster];
if (cluster === d) return;
var x = d.x - cluster.x,
y = d.y - cluster.y,
l = Math.sqrt(x * x + y * y),
r = d.radius + cluster.radius;
if (l != r) {
l = (l - r) / l * alpha;
d.x -= x *= l;
d.y -= y *= l;
cluster.x += x;
cluster.y += y;
}
};
}
// Resolves collisions between d and all other circles.
function collide(alpha) {
var quadtree = d3.geom.quadtree(nodes);
return function(d) {
var r = d.radius + maxRadius + Math.max(padding, clusterPadding),
nx1 = d.x - r,
nx2 = d.x + r,
ny1 = d.y - r,
ny2 = d.y + r;
quadtree.visit(function(quad, x1, y1, x2, y2) {
if (quad.point && (quad.point !== d)) {
var x = d.x - quad.point.x,
y = d.y - quad.point.y,
l = Math.sqrt(x * x + y * y),
r = d.radius + quad.point.radius + (d.cluster === quad.point.cluster ? padding : clusterPadding);
if (l < r) {
l = (l - r) / l * alpha;
d.x -= x *= l;
d.y -= y *= l;
quad.point.x += x;
quad.point.y += y;
}
}
return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
});
};
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment