function dodge(data, {radius = 1, x = d => d} = {}) {
const getRadius = typeof radius === "function" ? radius : () => radius;
const circles = data.map((d, i, data) => ({
x: +x(d, i, data),
r: +getRadius(d, i, data),
data: d
})).sort((a, b) => a.x - b.x);
const epsilon = 1e-3;
let head = null, tail = null;
function intersects(x, y, r) {
let a = head;
while (a) {
const sumR = a.r + r;
if ((a.x - x) ** 2 + (a.y - y) ** 2 < sumR * sumR - epsilon) {
return true;
}
a = a.next;
}
return false;
}
for (const b of circles) {
while (head && head.x < b.x - (head.r + b.r)) {
head = head.next;
}
b.y = 0;
if (intersects(b.x, b.y, b.r)) {
let a = head;
b.y = Infinity;
do {
const dx = a.x - b.x;
const sumR = a.r + b.r;
if (Math.abs(dx) <= sumR) {
const y = a.y + Math.sqrt(sumR * sumR - dx * dx);
if (y < b.y && !intersects(b.x, y, b.r)) {
b.y = y;
}
}
a = a.next;
} while (a);
}
b.next = null;
if (head === null) head = tail = b;
else tail = tail.next = b;
}
return circles;
}