5

I need to do some graph layout drawing and have been looking at using something like the Spring layout algorithm as implemented here and discussed here

However my nodes all have a width and height (is an entity diagram). Can anyone explain how I might incorporate this into the equation?

Community
  • 1
  • 1
Mark
  • 1,509
  • 1
  • 15
  • 28

2 Answers2

0

Taking the Graph JavaScript Framework as a starting point, you could do the following. I assume that the class Node has been extended by attributes width and height. Then, in the function layoutRepulsive, the expression for calculating the distances of nodes has to be changed to respect those sizes:

var dx = Math.max(0, Math.abs(node2.layoutPosX - node1.layoutPosX) - 0.5*(node2.width+node1.width));
var dy = Math.max(0, Math.abs(node2.layoutPosY - node1.layoutPosY) - 0.5*(node2.height+node1.height));

The maximum function enforces 0 as the lowest possible value for the distance, even when their bounding boxes overlap.

ojdo
  • 8,280
  • 5
  • 37
  • 60
0

looking inside the first link you procided, there is line 240:

var repulsiveForce = this.k * this.k / d;

which represent the repulsive potential (that's physics). The larger that number, the less likely is the geometric state. d is the distance between two nodes, and this.k is the spring stiffness. This potential becomes infinite for distance d = 0.

You want to translate this potential by a certain length (the size of your boxes), so replace d by d - length. That means, the repulsive force becomes infinite at the distance length. There still remains the problem, that the repulsive forces then decrease for distances, smaller then length, which must be covered by some conditional:

if (d + 0.0001 < length) repulsiveForce = bigbigNumber;

I added 0.0001 so that the repulsive force never becomes infinite, but only big, because computers don't handle infiniteness very well.

spiehr
  • 411
  • 2
  • 10