Beeswarm plot with force-directed layout in javascript/d3

Question

Here is an article on creating beeswarm plots in R.

There is also R package for beeswarm plot. Next two pictures illustrate some of possibilities that that package offers:

However, I'm now trying to make it using the force-directed layout of d3.js.

My plan is to have custom gravity pull the points towards a vertical line and their proper y value, and collision detection keep the points off each other.

I've got a semi-working prototype:

Unfortunately, I can't find a way around two problems -- which I suspect are really the same problem:

1. My points keep overlapping, at least a bit.

2. There's an ongoing "shuffle" after the points have piled up in the center of the layout, as the anti-collision forces and the "come to the center" forces fight.

I'd like the points to pretty quickly come to an agreement about where they should live, and wind up not overlapping.

The force code I'm using (in case you want to see it here and not on bl.ocks.org) is:

force.on("tick", function(e) {
  var q,
    node,
    i = 0,
    n = nodes.length;

  var q = d3.geom.quadtree(nodes);

  while (++i < n) {
    node = nodes[i];
    q.visit(collide(node));
    xerr = node.x - node.true_x;
    yerr = node.y - node.true_y;
    node.x -= xerr*0.005;
    node.y -= yerr*0.9;
  }

  svg.selectAll("circle")
      .attr("cx", function(d) { return d.x; })
      .attr("cy", function(d) { return d.y; });
});

function collide(node) {
  var r = node.radius,
    nx1,
    nx2,
    ny1,
    ny2,
    xerr,
    yerr;

  nx1 = node.x - r;
  nx2 = node.x + r;
  ny1 = node.y - r;
  ny2 = node.y + r;

  return function(quad, x1, y1, x2, y2) {
    if (quad.point && (quad.point !== node)) {
      var x = node.x - quad.point.x,
          y = node.y - quad.point.y,
          l = Math.sqrt(x * x + y * y),
          r = node.radius + quad.point.radius;
      if (l < r) {
        // we're colliding.
        var xnudge, ynudge, nudge_factor;
        nudge_factor = (l - r) / l * .4;
        xnudge = x*nudge_factor;
        ynudge = y*nudge_factor;
        node.x -= xnudge;
        node.y -= ynudge;
        quad.point.x += xnudge;
        quad.point.y += ynudge;
      }
    }
    return x1 > nx2
        || x2 < nx1
        || y1 > ny2
        || y2 < ny1;
  };
}

This is my first foray into force-directed layouts, so apologies if this is noobish...

Answer 1

Your results look pretty good to me. But, if you want to reduce the likelihood of overlap, there are a few things to try.

1. Add some padding between nodes. In particular, your circles have a stroke, and half of this stroke will extend beyond the radius of the circle. So if you want to avoid overlapping strokes, you'll need at least one pixel of padding when you compute r by adding the two radii together. (This assumes that you have one pixel stroke on each circle, which adds 0.5 pixels to each radius.)

2. Use .5 rather than .4 when computing the nudge_factor. This makes the overlap resolution stronger, by pushing any overlapping circles enough apart so they no longer overlap. If you use a value less than .4, the solution is a bit more stable, but it converges more slowly as circles still overlap a bit even after the nudge.

3. Run the collision resolution multiple times per tick. You're currently running the collision resolution and then applying the custom gravity (towards true_x and true_y). If you run the collision resolution multiple times per tick, it makes the collision resolution stronger relative to gravity.

Also, if you just want a static layout, you might also consider letting the force layout run a fixed number of iterations (or stabilize) and then render once at the end, rather than rendering iteratively. This makes the layout much faster, though it can cause a temporary hiccup in rendering if you run too many iterations.

Answer 2

Simple implementation

Here is another implementation: http://bl.ocks.org/4732279

I initially tried to implement this with force layout, but the force layout simulation naturally tries to reach its equilibrium by pushing data points along both axes, which can be disruptive to the ordering of the data (if that is important to you like it is for me).

This implementation could be improved by replacing the normally distributed random jittering with an intelligent strategy. But for my purpose, this sufficed.

1. The total number of iterations over the collision visitor directly affects the probability of collisions in the end state.
2. Bumping the standard deviation of the normal distribution up can help the visualization converge on a no-collision solution more quickly as well, but of course may require more vertical space in the end.

A little more fully featured, but more complex...

Here it is a little more flushed out (with an axis, zooming, etc.): http://bl.ocks.org/4734864

GIF animation: