javascript - 不同大小节点的碰撞检测未按预期工作

Question

我有一个功能齐全的 d3.js 力定向图。尝试添加碰撞检测以使节点不重叠。但需要注意的是，我的节点根据其 d.inDegree 和 d.outDegree

计算出不同的半径

    node.attr("r", function(d) {
    var weight = d.inDegree ? d.inDegree : 0 + d.outDegree ? d.outDegree : 0;
    weight = weight > 20 ? 20 : (weight < 5 ? 5 : weight);
    return weight;
  });

现在我正尝试在碰撞检测函数中使用这个变化的半径

    var padding = 1;
    var radius = function(d) { var weight = d.inDegree ? d.inDegree : 0 + d.outDegree ? d.outDegree : 0;
    weight = weight > 20 ? 20 : (weight < 5 ? 5 : weight);
    return weight;}
function collide(alpha) {
  var quadtree = d3.quadtree(d3GraphData.nodes);
  return function(e) {

    var rb = 2*radius + padding,
        nx1 = e.x - rb,
        nx2 = e.x + rb,
        ny1 = e.y - rb,
        ny2 = e.y + rb;
    quadtree.visit(function(quad, x1, y1, x2, y2) {
      if (quad.point && (quad.point !== e)) {
        var x = e.x - quad.point.x,
            y = e.y - quad.point.y,
            l = Math.sqrt(x * x + y * y);
          if (l < rb) {
          l = (l - rb) / l * alpha;
          e.x -= x *= l;
          e.y -= y *= l;
          quad.point.x += x;
          quad.point.y += y;
        }
      }
      return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
    });
  };
}

控制台没有报错，但是节点相互插入的时候还是重叠了。所以，我无法弄清楚将其归因于什么或如何调试它。

下面是fiddle

Answer 1

这是一个有趣的问题，经常以各种不同的方式提出。我记得最后一次回答其中一个问题是 Gerardo Furtado 的 "Conflict between d3.forceCollide() and d3.forceX/Y() with high strength() value" .一开始可能很难把握，但一旦完全陷入其中，就几乎是显而易见的了。所以请耐心等待，因为我会先尝试用简单的语言将其记录下来。

使用 d3.forceSimulation() 时重要的是要始终牢记，这只是那个:一个模拟，不多也不少。它的内部运作方式远非自然力量的真实复制品。一个主要缺点是，力是按顺序而不是同时施加的。甚至单个力的计算也会一个接一个地应用于一个节点，而不是一次应用于所有节点。这绝不是 D3 特有的问题，而是任何计算机驱动的模拟都面临并必须找到解决方案的问题。更糟糕的是，这个问题永远不会有真正的解决方案，而是在计算性能和它达到观众期望的程度之间进行权衡。

与自然相反，在我们的模拟中，一个约束可以很容易地违反另一个约束或另一个节点的相同约束，而不会导致存在本质的湮灭。通常，与您习惯并因此期望的力量相比，这些结果可能出乎意料。

这与您的特殊问题有什么关系？

在进行碰撞检测时，您会插入一些节点以避免违反互斥约束。主要取决于您的算法有多聪明，存在将一个节点插入另一个节点的风险，同时试图避免第三个节点。同样，根据您进行计算的方式，这种引发的违规可能要等到模拟的下一个滴答声才能解决。如果在碰撞检测之后计算的力将节点推到违反碰撞避免(或任何其他约束)的位置，则可能会发生同样的情况。这甚至可能会在处理其他力或其他节点上的相同力的过程中引发一系列问题。

解决此问题的最常见方法是在一个 tick 内多次应用碰撞避免算法，从而迭代地接近真实的解决方案，希望如此。当我第一次遇到这种方法时，它显得如此无助和可悲，令我震惊，这应该是我们最好的选择……但它的效果还不错。

由于您提供了自己的碰撞检测实现，即函数 collide()，让我们首先尝试改进它。通过将整个计算包装到一个循环中，重复十次，输出将显着改善 ( JSFiddle ):

for (let i=10; i>0; i--) {   // approximation by iteration
  quadtree.visit(function(quad, x1, y1, x2, y2) {
      // heavy lifting omitted for brevity
  });
}

虽然效果很好，但人们注意到节点仍然重叠，即使没有以前那么多。为了进一步改进这一点，我建议您放弃自己的实现，转而使用 D3 自己的 collision detection。可用的算法 d3.forceCollide() .此力的实现已经内置了上述迭代次数。您可以通过 collide.iterations() 设置来控制迭代次数。 .除此之外，该实现还配备了一些更巧妙的优化:

Overlapping nodes are resolved through iterative relaxation. For each node, the other nodes that are anticipated to overlap at the next tick (using the anticipated positions ⟨x + vx,y + vy⟩) are determined; the node’s velocity is then modified to push the node out of each overlapping node. The change in velocity is dampened by the force’s strength such that the resolution of simultaneous overlaps can be blended together to find a stable solution.

调整您的模拟可能看起来像这样(JSFiddle):

var simulation = d3.forceSimulation()
  .force("link",
    d3.forceLink()
      .id(function(d) { return d.id; })
      .distance(50)
      .strength(.5)            // weaken link strength
  )
  .force("charge", d3.forceManyBody())
  .force("center", d3.forceCenter(width / 2, height / 2))
  .force("gravity", gravity(0.25))
  .force("collide",
    d3.forceCollide()
      .strength(.9)            // strong collision avoidance
      .radius(radius)          // set your radius function
      .iterations(10)          // number of iterations per tick
  );

如您所见，仍然存在重叠节点，可能值得尝试更多地调整力的参数以产生令人赏心悦目的结果。然而，考虑到大量节点、它们相当大的圆圈和您施加的力的数量，我不希望它没有任何碰撞。