# Minimal containing sphere for a set of spheres?

This topic is 4353 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Simple question, but I can't seem to figure out the answer. Basically, given a set of spheres defined by their centers and radii, determine the center and radius of the minimal volume sphere that completely contains all of these spheres. How should I go about doing this? The radius is pretty easy to do once I have the center, but I'm not sure how to determine the optimal center point. This isn't homework. I was originally doing this because I wanted to figure out the bounding sphere for a model, given the bounding spheres of all its submeshes. I determine the center of the sphere there from the combined AABB of those submeshes, since I had per-submesh and total AABBs anyway. Then I just get the final radius from the individual bounding spheres. But I'm still curious about the more general case of the problem, where you have been given just the spheres. It seems like a fairly interesting problem to deal with.

##### Share on other sites
why couldn't you just average all the centers of the set of spheres? Then find the longest distance between any two spheres, and that's the definition of you're best-fit bounding sphere.

##### Share on other sites
You've probably already found is but I found this on google it says that the second algorithm can be adapted to spheres.

Hope that helps.

##### Share on other sites
It's easy, look at softsurfer.net and you'd see IIRC three algorithms. You can have fast algorithm, or precisse algorithm choose.

I use bounding boxes, because they are less wastefull.

##### Share on other sites
Quote:
 Original post by Morpheus011why couldn't you just average all the centers of the set of spheres? Then find the longest distance between any two spheres, and that's the definition of you're best-fit bounding sphere.

Because it's not the guaranteed minimum enclosure :)

There was an article on Game Programming Gems II (or 1?) about a dynamic sphere tree. There was code there to calculate what you are looking for.

##### Share on other sites
One solution might be to find the enclosing sphere for all midpoints of the spheres (by finding the longest distance between to sphere midpoints) and then intersect all the spheres with the enclosing sphere. If an intersection exists you can extend the radius of the enclosing sphere by the amount of the diameter of the testet sphere minus the overlap with the enclosing sphere.

##### Share on other sites
There's a great article about Welzl's algorithm including source by Nicolas Capens: Smallest Enclosing Spheres

1. 1
2. 2
3. 3
Rutin
21
4. 4
frob
18
5. 5

• 33
• 13
• 10
• 10
• 12
• ### Forum Statistics

• Total Topics
632568
• Total Posts
3007119

×