Fun Math Exercise -- Solutions!
If you're not trying to program a spaceship, you should probably skip this blog entry.
Two methods that I've discovered so far:
Straight-up geometry.
- Starting with a collection of points, start with any random point in space (e.g., the average of the point set, or one of the points in the set, or whatever). Take this initial point as your initial sphere center. Find the maximum distance from that point to any other point in the set. This maximum-distance point will be the first point defining your sphere.
- Define the sphere as being centered on that initial point, and the radius as the distance to that far point. Keeping the radius as the distance between center and far point, start moving the initial center towards the far point (thereby shrinking the radius). Calculate how close the center point can get to that far point before another point in the set hits the sphere radius. Whichever point hits the sphere radius next is the second point defining your sphere.
- Keep the sphere radius attached to these two points. The center is now an equal distance between the two points. Start moving the center towards the halfway point between the two radius points, shrinking the radius appropriately. Wait for a third point to hit the radius. This point will be the third point defining your sphere.
- If there is no third point before the center reaches the halfway point, then the sphere is defined by the halfway point as the center and the radius as the distance from the halfway point to one of the radius points. Done!
- With three points defined, calculate the circumcenter of the triangle that they define. Start moving the center towards the circumcenter, shrinking the radius to keep the three points attached to the radius. Calculate when a fourth point will hit the radius. You then have your sphere. Done!
- If there is no fourth point before the center reaches the plane of the three radius points, then the center is the triangle circumcenter and the radius is the distance to any of the three radius points. Done!
Recursion.
- Do some crazy shit found in Christer Ericson's Real-time Collision Detection called Welzl's algorithm.
I'm assuming this field is vague enough that the first method, which I sort of intuited, can be Malling's algorithm. If so, please label it properly.