CODEWITHSUNDEEP
mathd3.jsvisualizationdata-visualization
Kevin
Kevin

Reputation: 685

d3js Cluster Force Layout IV block by Mike

I am new to d3js and I'm just starting out.

I am trying the cluster layout example written by Mike in one of his blocks. https://bl.ocks.org/mbostock/7882658

I got it to work on my machine with my code but I really don't like just blindly copying code without understanding it.

However I am having a tough time understanding the math behind the 'cluster()' and 'collide()' functions and as to how they function.

Could anyone please explain it? Thanks for your help !!

Upvotes: 0

Views: 236

Answers (1)

Mark
Mark

Reputation: 108567

Let's look at each method and I'll comment it as best I can.

Cluster

First the caller:

 function tick(e) {
  node
    .each(cluster(10 * e.alpha * e.alpha)) //for each node on each tick call function returned by cluster function
                                           //pass in alpha cooling parameter to collide
  ...

I won't rehash an explanation here about how the tick event works. The documentation is clear.

The function:

// returns a closure wrapping the cooling
// alpha (so it can be used for every node on the tick)
function cluster(alpha) {
  return function(d) { // d here is the datum on the node 
    var cluster = clusters[d.cluster]; // clusters is a hash-map, the key is an index of the 10 clusters, the value is an object where d.cluster is the center node in that cluster
    if (cluster === d) return;  // if we are on the center node, do nothing
    var x = d.x - cluster.x, // distance on x of node to center node
        y = d.y - cluster.y, // distance on y of node to center node
        l = Math.sqrt(x * x + y * y), // distance of node to center node (Pythagorean theorem)
        r = d.radius + cluster.radius; // radius of node, plus radius of center node (the center node is always the largest one in the cluster)
    if (l != r) { // if the node is not adjacent to the center node
      l = (l - r) / l * alpha; //find a length that is slightly closer, this provides the illusion of it moving towards the center on each tick
      d.x -= x *= l; // move node closer to center node
      d.y -= y *= l; 
      cluster.x += x; // move center node closer to node
      cluster.y += y;
    }
  };
}

Collide

The collide function is a bit more complicated. Before we dive into it, you need to understand what a QuadTree is and why Bostock is using it. If you want to determine if two elements are colliding the naive algorithm would be to loop the elements both outer and inner to compare each one against every other one. This is, of course, computationally expensive especially on every tick. This is the problem QuadTrees are trying to solve:

A quadtree recursively partitions two-dimensional space into squares, dividing each square into four equally-sized squares. Each distinct point exists in a unique leaf node; coincident points are represented by a linked list. Quadtrees can accelerate various spatial operations, such as the Barnes–Hut approximation for computing many-body forces, collision detection, and searching for nearby points.

What does that mean? First, take a look at this excellent explanation. In my own simplified words it means this: take a 2-d space and divide it into four quadrants. If any quadrant contains 4 or less nodes stop. If the quadrant contains more than four nodes, divide it again into four quadrants. Repeat this until each quadrant/sub-quadrant contains 4 or less nodes. Now when we look for collisions, our inner loop no longer loops nodes, but instead quadrants. If the quadrant doesn't collide then move to the next one. This is a big optimization.

Now onto the code:

// returns a closure wrapping the cooling
// alpha (so it can be used for every node on the tick)
// and the quadtree
function collide(alpha) {
  // create quadtree from our nodes
  var quadtree = d3.geom.quadtree(nodes);
  return function(d) { // d is the datum on the node
    var r = d.radius + maxRadius + Math.max(padding, clusterPadding), // r is the radius of the node circle plus padding
        nx1 = d.x - r, // nx1, nx2, ny1, ny2 are the bounds of collision detection on the node
        nx2 = d.x + r,
        ny1 = d.y - r,
        ny2 = d.y + r;
    quadtree.visit(function(quad, x1, y1, x2, y2) { // visit each quadrant
      if (quad.point && (quad.point !== d)) { // if the quadrant is a point (a node and not a sub-quadrant) and that point is not our current node
        var x = d.x - quad.point.x, // distance on x of node to quad node
            y = d.y - quad.point.y, // distance on y of node to quad node
            l = Math.sqrt(x * x + y * y), // distance of node to quad node (Pythagorean theorem)
            r = d.radius + quad.point.radius + (d.cluster === quad.point.cluster ? padding : clusterPadding); // radius of node in quadrant
        if (l < r) { // if there is a collision
          l = (l - r) / l * alpha; // re-position nodes
          d.x -= x *= l;  
          d.y -= y *= l;
          quad.point.x += x;
          quad.point.y += y;
        }
      }
      // This is important, it determines if the quadrant intersects
      // with the node.  If it does not, it returns false
      // and we no longer visit and sub-quadrants or nodes
      // in our quadrant, if true it descends into it
      return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
    });
  };
}

Upvotes: 1

Related Questions