03 June, 2015
by fabiovalse

Non-overlapping circles through collision detection

This exercise allows to displace circles in a non-overlapping way. The collision detection introduced in this gist has been used in order to guarantee a certain padding between circles. The slider on the top allows to change the padding distance between circles.

index.css
.node {
  fill: steelblue;
}

.axis .domain {
  fill: none;
  stroke: #000;
  stroke-opacity: .3;
  stroke-width: 10px;
  stroke-linecap: round;
}

.axis .halo {
  fill: none;
  stroke: #ddd;
  stroke-width: 8px;
  stroke-linecap: round;
}

.slider .handle {
  fill: #fff;
  stroke: #000;
  stroke-opacity: .5;
  stroke-width: 1.25px;
  cursor: crosshair;
}
index.html
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <script src="http://d3js.org/d3.v3.min.js"></script>
    <link rel="stylesheet" type="text/css" href="index.css">
    <title>Collision detection with force layout</title>
  </head>
  <body>
    <script src="index.js"></script>
  </body>
</html>
index.js
var width = 960,
    height = 500,
    padding = 10,
    min_padding = 0,
    max_padding = 50,
    maxRadius = 10,
    n = 200;

var nodes = d3.range(n).map(function(i) {
  var r = Math.sqrt(1 / 1 * -Math.log(Math.random())) * maxRadius,
        d = {id: i, radius: r, cx: width/2+Math.random()*150-75, cy: height/2+Math.random()*150-75};
  return d;
});

nodes.forEach(function(d) { d.x = d.cx; d.y = d.cy; });

var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);

var circle = svg.selectAll("circle")
    .data(nodes);

var enter_circle = circle.enter().append("circle")
    .attr('class', 'node');

enter_circle
  .attr("r", function(d) { return d.radius; })
  .attr("cx", function(d) { return d.cx; })
    .attr("cy", function(d) { return d.cy; });

var force = d3.layout.force()
    .nodes(nodes)
    .size([width, height])
    .gravity(.02)
    .charge(0)
    .on("tick", tick)
    .start();

force.alpha(.05);

function tick(e) {
  //force.alpha(.01);

    circle
    .each(gravity(.2 * e.alpha))
    .each(collide(.5))
    .attr("cx", function(d) { return d.x; })
    .attr("cy", function(d) { return d.y; });
}

/*  SLIDER
*/
var x = d3.scale.linear()
    .domain([min_padding, max_padding])
    .range([0, width/2])
    .clamp(true);

svg.append("g")
    .attr("class", "x axis")
    .attr("transform", "translate(10, 10)")
    .call(d3.svg.axis()
      .scale(x)
      .ticks(0)
      .tickSize(0))
  .select(".domain")
  .select(function() { return this.parentNode.appendChild(this.cloneNode(true)); })
    .attr("class", "halo");

var brush = d3.svg.brush()
    .x(x)
    .extent([0, 0])
    .on("brush", brushed);

var slider = svg.append("g")
    .attr("class", "slider")
    .call(brush);

slider.selectAll(".extent,.resize")
    .remove();

var handle = slider.append("circle")
    .attr("class", "handle")
    .attr("transform", "translate(10, 10)")
    .attr("r", 9);

slider
    .call(brush.event);

function brushed() {
  var value = brush.extent()[0];

  if (d3.event.sourceEvent) {
    value = x.invert(d3.mouse(this)[0]);
    brush.extent([value, value]);

    force.alpha(.01);
  }

  handle.attr("cx", x(value));

  padding = value;
}

// Resolve collisions between nodes.
function collide(alpha) {
  var quadtree = d3.geom.quadtree(nodes);
  return function(d) {
    var r = d.radius + maxRadius + padding,
        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 + padding;
        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;
    });
  };
}

//  Move nodes toward cluster focus.
function gravity(alpha) {
  return function(d) {
    d.y += (d.cy - d.y) * alpha;
    d.x += (d.cx - d.x) * alpha;
  };
}
thumbnail.png
File not shown (binary encoding).