5 ms·

Miniball to Matoušek-Sharir-Welzl algorithm

80 points by based2 9y ago

deleted 9y ago
[deleted]
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 ago
  To 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 ago
  You 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 ago
    That'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;
debatem1 9y ago
Why can it only touch three circles? I can draw as many tangent circles as I want to for any given path.
- bestham 9y ago
  The same reason that a table with three legs is always stable. If you add more legs it can begin to wobble depending on the smoothness of surface it stands on. The larger circle needs to touch three circles because if it touches any more two of those circles will be not change the larger circles if removed and are thus not necessary.
  - debatem1 9y ago
    I'm not sure we're saying the same thing. I'm saying that it is not true that it can only touch three (or four, or any less-than-infinite number of circles). I think you're saying that only three of them are necessary to draw the correct circle. The analogy would be that any three points on a plane describe both the vertices of exactly one triangle and exactly one circle circumscribing it (your statement) and that an infinite number of circumscribed triangles can be found for any nontrivial circle (my statement).
- mbostock 9y ago
  You can have more than three tangent circles, but three tangent circles are sufficient to represent an enclosing circle.
algorias 9y ago
A similar problem is also the smallest enclosing ball of a point set. A solver for that is available, implemented in C++ [0]. Both of these problems can be generalized to finding the sink of a unique sink orientation [1], so there is in fact a rich mathematical theory underlying all of this. [0]: https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html https://people.inf.ethz.ch/gaertner/subdir/software/miniball... [1]: https://www.ti.inf.ethz.ch/ew/courses/ApproxGeom05/paper/fischer_gaertner_03.pdf https://www.ti.inf.ethz.ch/ew/courses/ApproxGeom05/paper/fis...

80 points by based2 9y ago

deleted 9y ago

[deleted]

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 ago
To 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 ago
You 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 ago
  That'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;

debatem1 9y ago

Why can it only touch three circles? I can draw as many tangent circles as I want to for any given path.

bestham 9y ago
The same reason that a table with three legs is always stable. If you add more legs it can begin to wobble depending on the smoothness of surface it stands on. The larger circle needs to touch three circles because if it touches any more two of those circles will be not change the larger circles if removed and are thus not necessary.
- debatem1 9y ago
  I'm not sure we're saying the same thing. I'm saying that it is not true that it can only touch three (or four, or any less-than-infinite number of circles). I think you're saying that only three of them are necessary to draw the correct circle. The analogy would be that any three points on a plane describe both the vertices of exactly one triangle and exactly one circle circumscribing it (your statement) and that an infinite number of circumscribed triangles can be found for any nontrivial circle (my statement).
mbostock 9y ago
You can have more than three tangent circles, but three tangent circles are sufficient to represent an enclosing circle.

algorias 9y ago

A similar problem is also the smallest enclosing ball of a point set. A solver for that is available, implemented in C++ [0]. Both of these problems can be generalized to finding the sink of a unique sink orientation [1], so there is in fact a rich mathematical theory underlying all of this. [0]: https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html https://people.inf.ethz.ch/gaertner/subdir/software/miniball... [1]: https://www.ti.inf.ethz.ch/ew/courses/ApproxGeom05/paper/fischer_gaertner_03.pdf https://www.ti.inf.ethz.ch/ew/courses/ApproxGeom05/paper/fis...