Barnes-Hut

All-pairs charge costs *n*² per tick. forceManyBody builds a quadtree whose cells store total strength and center of mass; a cell whose width over distance is below theta (0.9) acts as one node: Barnes and Hut's 1986 approximation, about n log n. theta(0) disables it:

barnes-hut.mjs: theta 0.9 against exact pairwise charge (Node.js)JavaScript

import { forceSimulation, forceManyBody, randomLcg } from 'd3';
const random = randomLcg(7);
const nodes = () => Array.from({ length: 2000 },
  () => ({ x: random() * 1000, y: random() * 1000 }));
for (const theta of [0.9, 0]) {
  const sim = forceSimulation(nodes()).force('charge', forceManyBody().theta(theta)).stop();
  const t0 = performance.now();
  sim.tick(3);
  console.log(`theta ${theta}: ${((performance.now() - t0) / 3).toFixed(1)} ms per tick`);
}

Output

theta 0.9: 29.7 ms per tick
theta 0: 494.0 ms per tick

Earlier runs on this shared 4-CPU machine gave 39.5/528.6 and 28.3/478.0 ms: 13 to 17 times faster, a gap that grows with n. The same d3.quadtree powers find() (Hybrid Canvas-and-SVG Charts) and forceCollide.

The quadtree behind forceManyBody, with the cells Barnes-Hut treats as one node, and timings for thetaHTMLLive

<!doctype html>
<style>
  body { margin: 0; padding: 8px; background: #fafaf7; font: 12px system-ui, sans-serif; color: #263238; }
  svg { width: 100%; max-width: 600px; display: block; background: #fff; }
</style>
<script src="https://cdn.jsdelivr.net/npm/d3@7.9.0/dist/d3.min.js"></script>
<p>theta <input type="range" id="theta" min="0.1" max="1.5" step="0.1" value="0.9"> <span id="tv"></span> · move the pointer to pick the node that feels the force</p>
<svg viewBox="0 0 600 300" font-size="11"></svg>
<p id="out">Timing…</p>
<script>
  const random = d3.randomLcg(7);
  const points = Array.from({ length: 800 }, () => {
    const cluster = Math.floor(random() * 4), cx = [90, 220, 120, 230][cluster], cy = [80, 90, 220, 210][cluster];
    return [cx + d3.randomNormal.source(random)(0, 38)(), cy + d3.randomNormal.source(random)(0, 38)()];
  }).filter(([x, y]) => x > 2 && x < 298 && y > 2 && y < 298);
  const tree = d3.quadtree().extent([[0, 0], [300, 300]]).addAll(points);
  const svg = d3.select('svg');
  const cellsG = svg.append('g'), dotsG = svg.append('g');
  dotsG.selectAll('circle').data(points).join('circle').attr('r', 1.5).attr('cx', p => p[0]).attr('cy', p => p[1]).attr('fill', '#90a4ae');
  const me = svg.append('circle').attr('r', 5).attr('fill', '#b5452f');

  // Walk the tree as forceManyBody does: a cell far enough away (width / distance < theta) counts as one body
  function show([px, py]) {
    const theta = +d3.select('#theta').property('value'), cells = [];
    tree.visit((node, x0, y0, x1, y1) => {
      const cx = (x0 + x1) / 2, cy = (y0 + y1) / 2, w = x1 - x0, d = Math.hypot(cx - px, cy - py);
      if (!node.length) { cells.push({ x0, y0, x1, y1, far: false }); return true; }   // a leaf: exact
      if (w / d < theta) { cells.push({ x0, y0, x1, y1, far: true }); return true; }  // approximate, skip children
      return false;                                                                  // look inside
    });
    cellsG.selectAll('rect').data(cells).join('rect').attr('x', c => c.x0).attr('y', c => c.y0)
      .attr('width', c => c.x1 - c.x0).attr('height', c => c.y1 - c.y0)
      .attr('fill', c => c.far ? '#e09a10' : 'none').attr('fill-opacity', 0.18).attr('stroke', c => c.far ? '#e09a10' : '#dfe6ea');
    me.attr('cx', px).attr('cy', py);
    d3.select('#tv').text(`${theta}: ${cells.filter(c => c.far).length} far cells + ${cells.filter(c => !c.far).length} near leaves, ` +
      `instead of ${points.length - 1} pairs`);
  }
  svg.on('pointermove', e => { const [x, y] = d3.pointer(e); if (x < 300) show([x, y]); });
  d3.select('#theta').on('input', () => show([+me.attr('cx'), +me.attr('cy')]));
  show([100, 90]);

  // Time one tick of forceManyBody with Barnes-Hut (0.9) and with all pairs (theta 0)
  setTimeout(() => {
    const nodes = () => Array.from({ length: 1500 }, () => ({ x: random() * 1000, y: random() * 1000 }));
    const times = [0.9, 0].map(theta => {
      const sim = d3.forceSimulation(nodes()).force('charge', d3.forceManyBody().theta(theta)).stop();
      const t0 = performance.now();  sim.tick(2);
      return { theta, ms: (performance.now() - t0) / 2 };
    });
    const tx = d3.scaleLinear([0, d3.max(times, t => t.ms)], [0, 250]);
    const g = svg.append('g').attr('transform', 'translate(320,40)');
    g.append('text').attr('font-weight', 'bold').text('1,500 nodes, ms per tick');
    const bar = g.selectAll('g').data(times).join('g').attr('transform', (t, i) => `translate(0,${34 + i * 50})`);
    bar.append('rect').attr('height', 24).attr('width', t => tx(t.ms)).attr('fill', t => t.theta ? '#3f7d3a' : '#b5452f');
    bar.append('text').attr('y', -4).text(t => `theta ${t.theta}${t.theta ? ' (Barnes-Hut)' : ' (all pairs)'}: ${t.ms.toFixed(1)} ms`);
    d3.select('#out').text(`Barnes-Hut was ${(times[1].ms / times[0].ms).toFixed(1)}× faster here; the gap grows with n.`);
  }, 50);
</script>

MENU