Archived

This topic is now archived and is closed to further replies.

tight fitting spheres

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

Recommended Posts

what is the position and radius of the smallest sphere containing all of any number of given points? ******** A Problem Worthy of Attack Proves It''s Worth by Fighting Back

Share on other sites
What I would do is find the bounding box of all the points. Then, you take the largest element of this box (i.e width, length, or height) and make that the diameter of the sphere (so basically the radius is half of whatever element is chosen). The center of the sphere would be the center of the bounding box. Hope that makes sense

Share on other sites
what if one point is in the corner of the box, won''t it get left out, and if the radius is set to include the corners, won''t it be ill-fitting unless there are points in every corner?

********

A Problem Worthy of Attack
Proves It''s Worth by Fighting Back

Share on other sites
Have a look here:

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

Share on other sites
Ack, I was thinking something but wrote something else

You''d still want to find the bounding box, but the radius of the circle would be largest distance between any one point and the center of the bounding box.

Share on other sites
the approaches i have seen are recursive, i have an idea:

from the origin find the furthest point. from that point again find the furthest point. these will be two points both on the edge of the circle or sphere. no other two points will be further away.

i then could find the point furthest from the line between the first two. this would aso be on the edge of the circle.

for each additional dimension, take the last found futhest point and add it to the "far" group: from that group construct a surface from which to test distance.

eg for 3-dimensions, form a plane with the line''s end points and the latest "far point". the point furthest from that would be needed to make the tightest possible sphere.

are there any situations where this approach would not give the N points at the extreme edges of the bounding shape? ie can there ever be points in the set outside the computed shape?

********

A Problem Worthy of Attack
Proves It''s Worth by Fighting Back

Share on other sites
That might be a bit of overkill. This bounding sphere has to contain every point on your object, that''s a given. So if you find the farthest point from the origin and make your radius equal to that distance, then that''s really the minimum radius you can have from that origin that encompasses all the points. Any smaller and that one far point won''t fit, and any larger and it wouldn''t be a tight sphere.

I would have to test the algorithm a few times to see if it finds the "true" tight bounding sphere for any set of points, but it sounds like a good method.

Share on other sites
im not taking the distance from the origin.

the basic approach is "find the furthest point from whatever structure has been made from the previously found "far points"

the origin is just where to start having found no points yet. the furthest point from the origin is the real starting point because it is somewhere on the edge

the next furthest point from the furthest point is also on the edge

the next next furthest point from the next furthest point and the furthest point is also on the edge

and so on and so on as many times as is needed

********

A Problem Worthy of Attack
Proves It''s Worth by Fighting Back

Share on other sites
Why not create an ABB and find the center of that AABB. (Get min / max, and then compute the center(half way from min to max) ).

Then the radius is the length from the center to a corner(ie: center to max, or center to min).

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

• 26
• 11
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633701
• Total Posts
3013446
×