search

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

Collide force doesn't handle identical initial positions well #199

Open Nate-Wessel opened 3 years ago

Nate-Wessel commented 3 years ago

I'm working on a fixed force layout with collision and X and Y positioning. It's being rendered by React, and so I'm trying to optimize and speed up the force layout to reduce the expense of the simulation as my component may be resized, panned, and thus rerendered/resimulated quite often.

I found that initializing the node positions with the x and y properties greatly reduces the number of ticks needed to get the layout looking the way I want it. But it also causes some problems where the initial position is the same for several points, as in this map where I'm trying to cluster points around polygon centroids.

Screenshot 2021-07-15 at 12-28-29 Risk Demo

With another 40-50 ticks, it will settle down into something like this which is what I expect. (Possibly just due to floating point error?)

Screenshot 2021-07-15 at 12-36-36 Risk Demo

I can get the same effect with a shorter simulation by applying a deterministic (seeded) random jitter to the initial positions, but I thought it would be nice if D3 could handle this itself similar to the way the phyllotaxis arrangement around 0,0 does this for the default initial positions.

Fil commented 3 years ago

Respecting user-defined initial positions seems like the expected behavior. In fact, adding jitter to user-defined initial positions might cause problems in some cases (for example if you need all the initial x values to be exactly 0). A possibility might be to define a force that jitters positions on initialization, but I don't see how this would be easier to use than jittering the initial positions?

Nate-Wessel commented 3 years ago

I guess my suggestion is less that initial positions should be jittered (that was just my own solution and I agree that overriding users' explicit intentions would not be good) and more that the direction of the force applied by forceCollide should be. It seems to send all points outward along a common axis, rather than sending them in all directions as I would expect. I suppose there must already be some way of deciding which way to send the points in this case, but it seems to apply to all points with the shared position rather than picking a random direction separately for each.

Anyway, just a friendly suggestion. Thanks for your contributions to such an awesome library.

Fil commented 3 years ago

It should already be the case https://github.com/d3/d3-force/blob/475ec96f1afad3bab5442d614af67fa0ce7c9785/src/collide.js#L50

oh, I see… it seems to be because, once the two first dots have been "randomly" separated, the other coincident points are not anymore within 0 of those points, and so the force is in the direction set by the first random jitter. A bug!

curran commented 3 years ago

Oh wow nice catch @Fil ! That's subtle.

Fil commented 3 years ago

I have a fix here https://observablehq.com/d/dd1bcd29c2b1b850; it breaks the symmetry of the original solution for 2 coincident nodes, which is not a requirement but was kinda nice.

Nate-Wessel commented 2 years ago

Any update on this? I just realized that it's been nearly a year. I actually have a few other use-cases now were it would be really nice to have this resolved. Happy to try and create a pull request if it helps!

Fil commented 1 year ago

Sorry I don't know why I had never pushed this branch from my laptop. Now PR #214.