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.