Avoid collision between nodes and edges in D3 force layout

Question

In this example: http://bl.ocks.org/mbostock/1747543:

...Mike shows us how to avoid collision among nodes so that no two nodes overlap each other.

I wonder if it is possible to avoid collision between nodes and edges so that no node 'clips' or overlaps an edge unless it is connected by that edge.

The following example using D3 force-direct shows that node L overlaps with the edge connecting I and A, and similarly, node M overlaps with the edge connecting L and D. How do we prevent such cases?

Answer 1

If your graph doesn't have too many nodes, you can fake it. Just insert one or more nodes for each link, and set their position along the link in the tick handler. Check out http://bl.ocks.org/couchand/7190660 for an example, but the changes to Mike Bostock's version amount to basically just:

var linkNodes = [];

graph.links.forEach(function(link) {
  linkNodes.push({
    source: graph.nodes[link.source],
    target: graph.nodes[link.target]
  });
});

and

// force.on('tick', function() {
linkNodes.forEach(function(node) {
  node.x = (node.source.x + node.target.x) * 0.5;
  node.y = (node.source.y + node.target.y) * 0.5;
});

This will introduce a pretty serious performance overhead if you have very many nodes and edges, but if your graph doesn't get much larger than your example it would hardly be noticed.

You may also want to fiddle with the relative force of the real nodes versus the link nodes.

Take this one step further and you get the nice curved links of http://bl.ocks.org/mbostock/4600693.