不同尺寸节点的碰撞检测不能按预期工作

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

控制台上没有错误,但是当相互推入时节点仍然重叠.所以,我无法弄清楚将其归因于什么或如何调试它.

下面是小提琴

Answer 1

这是一个有趣的问题,每隔一段时间就会出现各种各样的问题.我记得最后一次回答其中一个是Gerardo Furtado的"d3.forceCollide()与d3.forceX/Y()之间的冲突,具有高强度()值".一开始可能很难掌握,但一旦完全沉入,几乎是显而易见的.所以请耐心等待,因为我会先用简单的话来说明这一点.

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

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

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

在进行碰撞检测时,您正在推动某些节点,以避免违反互斥约束.主要取决于算法的聪明程度,在尝试避开第三个节点时,存在将一个节点推入另一个节点的风险.同样,根据您进行计算的方式,在模拟的下一个滴答之前,可能无法解决此诱导违规.如果在碰撞检测之后计算的力将节点推到违反碰撞避免(或任何其他约束)的位置,则可能发生相同的情况.这甚至可能导致在其他节点上与其他力量或相同力量相关的一系列问题.

最常见的方法是在一个刻度内多次应用碰撞避免算法,从而迭代地接近真正的解决方案,希望如此.当我第一次遇到这种方法时,它看起来如此无助和可怜,我感到震惊,它应该是我们最好的镜头......但它的工作并没有那么糟糕.

既然你提供了自己的碰撞检测实现,即函数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自己的碰撞检测算法d3.forceCollide().该力的实现具有已经内置的上述迭代.您可以通过设置它来控制迭代次数collide.iterations().除此之外,该实现还配备了一些更聪明的优化:

通过迭代松弛解决重叠节点.对于每个节点,确定预期在下一个滴答处重叠的其他节点(使用预期位置⟨x + vx,y + vy⟩ ); 然后修改节点的速度以将节点推出每个重叠节点.力的变化受到力的强度的抑制,使得同时重叠的分辨率可以混合在一起以找到稳定的解.

调整你的simulation看起来像这样(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
  );

正如您所看到的,仍然存在重叠的节点,并且可能值得利用力的参数进行更多的操作以产生令人愉悦的结果.鉴于节点数量众多,它们相当大的圆圈和你应用的力的数量,我不希望它没有任何碰撞.