I wanted to try a more naive/slow/sledge-hammer approach of just setting up the cost function and throwing it at an optimizer.
I couldn't get it to converge and I am not sure if it's just the library I am using being buggy (numeric.js) or my cost function is just bad.
Cost:
const cost = (a, b) => {
// If a encloses b, returns 0, otherwise a positive cost
const dx = b.x - a.x;
const dy = b.y - a.y;
return Math.max(
0,
-a.r + (b.r + Math.sqrt(dx * dx + dy * dy))
);
}
let iter = 0;
const costAll = ([x, y, r]) => {
// Cost of enclosing all balls (which should be 0) plus cost of radius (which should get us the smallest ball)
const a = { x, y, r };
const radiusCost = Math.abs(a.r);
let encloseCost = 0;
for (let i = 0; i < B.length; i++) {
encloseCost += cost(a, B[i]);
}
const totalCost = encloseCost + radiusCost;
return totalCost;
}
Demo:https://codepen.io/anon/pen/ZyEaaQ?editors=0010
EDIT: demo should work correctly after mbostock's hint below!