4 ms·
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 an
by arnioxux 9y ago
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 https://codepen.io/anon/pen/ZyEaaQ?editors=0010
EDIT: demo should work correctly after mbostock's hint below!
- arnioxux 9y agoTo answer my own question, the problem seems to be that once it finds an enclosing circle it loses gradient on x and y so it doesn't know where to reposition the circle. Not sure how to fix this.
- mbostock 9y agoYou can solve by finding the point <x, y> that minimizes the distance from any point in any input circle: \sqrt{(x_p - x) ^ 2 + (y_p - y) ^ 2} + r_p for p ∈ L. This is the center of the smallest enclosing circle. Once you have the center, you can iterate over every input circle to compute its radius.
- arnioxux 9y agoThat's clever! I updated the code and it seems to work for the several times I refreshed now. Thanks! This was the final cost function that worked: let encloseCost = 0; let farthestPointCost = 0; for (let i = 0; i < B.length; i++) { const b = B[i]; const dx = b.x - a.x; const dy = b.y - a.y; encloseCost += Math.max( 0, -a.r + (b.r + Math.sqrt(dx * dx + dy * dy)) ); farthestPointCost = Math.max( farthestPointCost, b.r + Math.sqrt(dx * dx + dy * dy) ); } const radiusCost = Math.abs(a.r); const totalCost = encloseCost + farthestPointCost + radiusCost;