Jump to content
  • Advertisement

Archived

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

walkingcarcass

tight fitting spheres

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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).

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!