不同尺寸节点的碰撞检测不能按预期工作 [英] Collision detection for nodes of varying sizes not working as expected

问题描述

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

I have a fully functional d3.js force directed graph. Trying to add collision detection so that the nodes do not overlap. But the caveat is my nodes having a varying radius calculated on the basis of its d.inDegree and 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;
  });

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

Now I am trying to use this varying radius in the function for collision detection

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

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

There is no error on the console , but the nodes are still overlapping when pushed into each other. So , I am not able to figure out what to attribute this to or how to debug it.

下面是小提琴

推荐答案

这是一个有趣的问题，经常以各种口味提出。我记得最后一次回答其中一个是Gerardo Furtado的 d3.forceCollide（）与d3.forceX / Y（）之间的冲突，具有高强度（）值 。一开始可能很难掌握，但一旦完全沉入，几乎是显而易见的。所以请耐心等待，因为我会先用简单的语言说明这一点。

This is an interesting question, which every so often is brought up in various flavors. The last time I remember having answered one of these was Gerardo Furtado's "Conflict between d3.forceCollide() and d3.forceX/Y() with high strength() value". It may be hard to grasp at first, but once it has fully sunken in, it is almost obvious. So bear with me as I will try to put this down in plain words first.

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

When using d3.forceSimulation() it is important to always keep in mind, that it is just that: a simulation, no more, no less. And its inner workings are far from being a realisitic replica of nature's forces. One major drawback is the fact, that forces are applied sequentially instead of simultaneously. And even the calculations for a single force will be applied to one node after another instead of all nodes at once. This is by no means a problem special to D3, but an issue any computer-driven simulation faces and has to find a solution for. Even worse, there will never be a real solution to the problem, but rather a trade-off between the performance of the calculations and the degree it lives up to the viewers expectations.

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

Contrary to nature, in our simulation a constraint can easily violate another constraint or the same constraint for another node without causing the annihilation of the essence of being. Often, these results might come unexpected when compared to forces you are accustomed to and are thus expecting.

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

When doing collision detection you are pushing around some nodes to avoid violating the constraint of mutual exclusion. Mainly depending on how clever your algorithm is, there is a risk of pushing one node into the realm of another while trying to avoid a third node. Again, depending on the way you do the calculations, this induced violation might not be resolved until the next tick of the simulation. The same may happen if a force, which is calculated after the collision detection, pushes a node to a position where it violates the collision avoidance (or any other constraint). This may even give rise to a bunch of problems further down the road dealing with the other forces or the same force on other nodes.

最常见的方法是在一个刻度内多次应用碰撞避免算法，从而迭代地接近真正的解决方案，希望如此。当我第一次遇到这种方法时，它看起来如此无助和可怜，我感到震惊，它应该是我们最好的拍摄…但它不能 坏。

The most common way around this is to apply the collision avoidance algorithm multiple times within one tick, whereby iteratively getting closer to a real solution, hopefully. When I first came across this approach, it seemed so helpless and pathetic, that I was astounded, that it should be our best shot… But it works not that bad.

因为你提供了自己的碰撞检测实现，即函数碰撞（），让我们先尝试改进。通过将整个计算重新组合成一个循环（例如十次），输出将显着改善（ JSFiddle ）：

Since you provided your own implementation for a collision detection, namely the function collide(), let us first try to improve that. By wrapping your entire calculations into a loop repeating it, say, ten times, the output will significantly improve (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（） 。除此之外，该实现还配备了一些更聪明的优化：

Although this works out pretty well, one notices nodes still overlapping, if not that many as before. To further improve on this, I suggest you ditch your own implementation in favor of D3's own collision detection algorithm which is available as d3.forceCollide(). This force's implementation has the above mentioned iterations already built in. You can control the number of iterations by setting it via collide.iterations(). Apart from that, the implementation is equipped with some more clever optimizations:

通过迭代放松解决重叠节点。对于每个节点，确定预期在下一个时刻重叠的其他节点（使用预期位置⟨ x + vx ， y + vy ⟩）;然后修改节点的速度以将节点推出每个重叠节点。速度的变化受到力的强度的影响，使得同时重叠的分辨率可以混合在一起以找到稳定的解。

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 ） ：

Tweaking your simulation could look like this (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
  );

正如您所看到的，仍有重叠的节点，可能值得玩这些参数更多的力量产生令人愉悦的结果。鉴于节点数量众多，它们相当大的圆圈和你应用的力的数量，我不希望它没有任何碰撞。

As you can see, there are still overlapping nodes, and it might be worth playing around with the parameters of the forces some more to yield an outcome which is pleasing to the eye. Given the large number of nodes, their rather large circles and the number of forces you apply, however, I would not expect it to be free of any collisions.

这篇关于不同尺寸节点的碰撞检测不能按预期工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！