forceCollide ignores fixed positions

[belukha]

I try to force circles to the point, and resolve collisions. But if some of these circles have fixed position, other circles behave like there're no circles with fixed positions.

demo: https://codesandbox.io/s/d3-forces-collide-ignore-fixed-position-w2qbkg?file=/src/index.ts

[Fil]

Not sure if this is a bug or works as intended—in any case, forceCollide doesn't check if the nodes are fixed or not, see

d3-force/src/collide.js

Line 53 in 475ec96

node.vx += (x *= l) * (r = (rj *= rj) / (ri2 + rj));

Maybe try to change some parameters, by making the collision force slower, and solving in many more ticks:

.strength(0.03);

simulation.tick(1000)

[belukha]

It looks good for this demo, but I think I can't use it in my project. Because I call collision resolution simulation on every zoom event and 1000 iterations on each such event call is too much and laggy. Do you have any ideas how can I patch forceCollide to make it consider fixed positions?

[Fil]

You'd need to make two additional tests, I think:

• if node is fixed, back off
• if data is fixed, move only the node

[rioj7]

@Fil It is a bit more complicated

You can have a fixed X or fixed Y or both.

---

The other forces of the simulation change the vx and vy of the fixed nodes.
The collision force will use a wrong position of the fixed nodes

d3-force/src/collide.js

Lines 36 to 37 in c3e73cf

	xi = node.x + node.vx;
	yi = node.y + node.vy;

Thus the moving nodes collide to a wrong circumference of the fixed node.

The construction of the quadtree uses the functions x() and y()

d3-force/src/collide.js

Lines 5 to 11 in c3e73cf

	function x(d) {
	return d.x + d.vx;
	}
	function y(d) {
	return d.y + d.vy;
	}

to place the node in the QuadTree. It is the wrong position for (partial) fixed nodes. So some tests may fail and a collision is not checked.

---

In the apply() function the nodes data and node

d3-force/src/collide.js

Line 45 in c3e73cf

if (data.index > node.index) {

can be moveable or (partially) fixed. If both are XY-fixed do nothing

[rioj7]

@belukha The 2 empty spaces are caused by the "collision" of the 2 fixed nodes. they get a vx,vy component

d3-force/src/collide.js

Lines 53 to 56 in c3e73cf

	node.vx += (x *= l) * (r = (rj *= rj) / (ri2 + rj));
	node.vy += (y *= l) * r;
	data.vx -= x * (r = 1 - r);
	data.vy -= y * r;

All the other nodes see a shadow version

d3-force/src/collide.js

Lines 46 to 47 in c3e73cf

	var x = xi - data.x - data.vx,
	y = yi - data.y - data.vy,

I have created pull request #225

The result is like:

I used the code from

https://bl.ocks.org/anonymous/9be75547ffb0ec24a0e0745d41fafd67/f47f6f6650dd0b0d505dfcef55fb63170556c314

You can create your own customforce.js by modifying the code related to the collision force.
See the pull request for the lines of the force() to copy and replace.
You get radial force x and y functions too. Because this gist was created for pull request 113

In the HTML use the following code:

function getRandomInt(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min) + min); // The maximum is exclusive and the minimum is inclusive
}

var svg = d3.select("#svganchor")
    .append("svg")
    .attr("width", 1000)
    .attr("height", 1000);

var data = [];
data.push({ x: 145, y: 145, fx: 145, fy: 145, r: 40, color: "blue" });
data.push({ x: 155, y: 155, fx: 155, fy: 155, r: 40, color: "green" });
for (let i = 0; i < 80; i++) {
  data.push({ x: getRandomInt(0, 400), y: getRandomInt(0, 400), r: 10, color: "red" });
}

var simulation = d3.forceSimulation(data)
    .force("collide", d3.forceCollide(d => d.r).strength(1).iterations(10))
    .force("x", d3.forceX(150))
    .force("y", d3.forceY(150));

var nodes = svg.selectAll(null)
    .data(data)
    .enter()
    .append("circle")
    .attr("r", d => d.r)
    .attr("fill", 'transparent')
    .style("stroke", d => d.color);

simulation.on("tick", tick);

function tick() {
  nodes
    .attr("cx", function(d) { return d.x })
    .attr("cy", function(d) { return d.y });
}