[Solved]-Collision detection for nodes of varying sizes not working as expected-d3.js

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.

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.

How is this related to your special problem?

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.

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

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:

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.

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.