mike 的 d3js Cluster Force Layout IV 块

Question

我是 d3js 的新手，我才刚刚起步。

我正在尝试 Mike 在他的一个区块中编写的群集布局示例。 https://bl.ocks.org/mbostock/7882658

我用我的代码让它在我的机器上工作，但我真的不喜欢在不理解它的情况下盲目地复制代码。

然而，我很难理解 'cluster()' 和 'collide()' 函数背后的数学原理以及它们的功能。

谁能解释一下？感谢您的帮助！！

Answer 1

让我们看看每种方法，我会尽我所能对其进行评论。

集群

首先来电者：

 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
  ...

我不会在这里重新解释 tick 事件的工作原理。 documentation清楚了。

函数：

// 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;
    }
  };
}

碰撞

碰撞函数有点复杂。在我们深入研究之前，您需要了解四叉树是什么以及 Bostock 为什么使用它。如果你想确定两个元素是否发生碰撞，天真的算法就是循环外部和内部的元素以将每个元素与其他元素进行比较。当然，这在计算上是昂贵的，尤其是在每次报价时。这是四叉树试图解决的问题：

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.

这是什么意思？首先，看看这个excellent explanation。用我自己的简化的话来说，它的意思是：取一个二维 space 并将其分成四个象限。如果任何象限包含 4 个或更少的节点，则停止。如果象限包含四个以上的节点，则将其重新划分为四个象限。重复此操作，直到每个 quadrant/sub-quadrant 包含 4 个或更少的节点。现在，当我们寻找碰撞时，我们的内部循环不再循环节点，而是循环象限。如果象限没有发生碰撞，则移动到下一个象限。这是一个很大的优化。

现在进入代码：

// 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;
    });
  };
}

mike 的 d3js Cluster Force Layout IV 块

d3js Cluster Force Layout IV block by Mike

math

visualization

data-visualization

d3.js