d3 / d3-force

Force-directed graph layout using velocity Verlet integration.
https://d3js.org/d3-force
ISC License
1.81k stars 376 forks source link

Fix spring force in forceLink. #185

Closed rogerdehe closed 3 years ago

rogerdehe commented 3 years ago

Here is the thing, I think forceLink is mean to implement a spring force, if so, now code of the force has a issue.

  1. Prove the implementation is spring force

    I just give some reason to prove this is a implementation of spring force, you can skip this part if you alredy believe this.

    According to Hooke's law:

    F = k * dl // here F is the spring force,k is a positive real number, characteristic of the spring, dl is the delta length of spring.

    And according to Newton's laws:

    F = m * a // here F is force, m is the mass of object, a is acceleration of object

    So we can get a = k * dl / m, we can set strength = k / m, then get this:

    a = strength * dl

    Then we get delta x and delta y like this:

    // if we alread computed delta x as x, delta y as y
    l = Math.sqrt(x * x + y * y);

    dl = (l - distance); acceleration = strength dl; // => strength (l - distance) dv = acceleration dt; // => strength (l - distance) dt // next (x / l) means get delta in x axis dvx = dv dt x / l; // => x (l - distance) strength dt dt / l // next (y / l) means get delta in y axis dvy = dv dt y / l; // => y (l - distance) strength dt * dt / l

    Here we do some change to the variable.

    l = Math.sqrt(x * x + y * y);
    l = (l - distances[i]) / l * strengths[i] * (dt * dt);
    x *= l, y *= l;

    You can see the only difference with here forceLink code is dt * dt and alpha.

  2. My problem with compute delta x and delta y

    My problem is here:

    x = target.x - source.x; // instead of target.x + target.vx - source.x - source.vx
    y = target.y - source.y; // insrtead of target.y + target.vy - source.y - source.vy

    If we add target.vx - source.vx (call this dvx) or target.vy - source.vy (call this dvy), image that,

Fil commented 3 years ago

This is addressed in https://github.com/d3/d3-force#forces:

forces may also “peek ahead” to the anticipated next position of the node,

rogerdehe commented 3 years ago

@Fil Sorry, I ignored this.