I can''t think of any good Google search string for this. I have a bunch of points. I need to find the origin and radius that describes a sphere that encompasses all those points. Straightforward. It''s a random distribution of points; they are not in the same plane. Any help would be greatly appreciated. I finally got collision detection working perfectly, so it''s optimization time now. ~CGameProgrammer( );

Actually I just tried something different and got a valid search result. According to this site, the center is just the average of the points. Then you just find the farthest point from the center and that distance is the radius. Straightforward but I'm not sure the center is correct.

In fact it isn't. Here's a simple example with a 2D triangle.



The red point is where the center of the overall sphere (or circle) should be. The green dot is where it would be from getting the average of the points.

~CGameProgrammer( );

By "should" I mean my goal is to get the minimum radius needed to cover all points. The circle may look better at the green dot, but the fact is its radius would have to be wider.

[edited by - CGameProgrammer on November 27, 2002 1:39:03 AM]

It's easy to find a sphere that surrounds all the points. You wouldn't want to use the average of the points however, because if a lot of points are clustered real close together they will weight the average towards them. You would want to make a tight bounding box around all the points and use the center of the bounding box. Then as you said, the point farthest away from this center becomes the radius.

While there works, there is a problem. We are not guaranteed that this is the sphere of smallest radius that can enclose the points, or if even the center is correct. Like you said, the red point should be where the center of the circle should be, but it's not too easy to calculate that point I've been working on a few algorithms for finding the tight circle analytically in 2D, and I'm getting real close to something . It shouldn't be too difficult to convert it to 3D mathmatics if I even get something

At any rate, there exists something that you can use to solve this problem, along the line of metaballs, superballs, something-balls I can't think of it off the top of my head.

[edited by - Zipster on November 27, 2002 1:49:47 AM]

Smallest enclosing balls:

http://www.inf.ethz.ch/personal/gaertner/miniball.html

If you only have four non-coplanar points, there''s a unique sphere that lies on all those points. If you have more, I suppose you could find the sphere that includes the four points farthest from the average of all the points.

http://www.flipcode.com/cgi-bin/msg.cgi?showThread=COTD-SmallestEnclosingSpheres&forum=cotd&id=-1

Ya that one is based on the algorithm developped by Gaertner (MrFreeze''s link) but limited to 3D which should be enough I guess...

Thanks for that link, Dirk.

~CGameProgrammer( );