Jump to content
  • Advertisement
Sign in to follow this  
rpsathe

a sphere passing thru' 4 points

This topic is 4252 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

How does one go about finding a unique sphere that passes thru' 4 points? In case of 2D (i.e. in a given plane), I know that 3 points define a circle. Perpendicular bisectors of two secants intersect at the center of the circle. Recently I remember one needs 4 points in space (3 is not enough) for a sphere passing thru' all 4 points. Any idea how to about finding the center of the sphere?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by rpsathe
How does one go about finding a unique sphere that passes thru' 4 points?
Depending on why you need this, it may be worthwhile to note that e.g. the sphere through 4 (non-planar) points is generally not the same thing as the smallest bounding sphere for the same 4 points.

Share this post


Link to post
Share on other sites
Edit: Removed lies.

In fact, the sphere passing through the four points is the minimal bounding sphere only for a single 1D subspace of the problem set (read: in very few cases).

While we're at it, your problem requires that no three points are collinear for a (finite-radius) solution to exist.

Admiral

[Edited by - TheAdmiral on February 1, 2007 2:52:12 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
In fact, the sphere passing through the four points is the minimal bounding sphere only for a single 1D subspace of the problem set (read: in very few cases).

Do you have proof of that? It looks to me like if you have the four vertices of a regular tetrahedron and you jitter one of them around inside a little sphere, the solution is still the sphere that passes through all four points, but I haven't worked out the details.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Do you have proof of that? It looks to me like if you have the four vertices of a regular tetrahedron and you jitter one of them around inside a little sphere, the solution is still the sphere that passes through all four points, but I haven't worked out the details.

It depends on how much of a jitter it is :) For instance, if you move one of the points too close to the opposite side, then it will no longer be on the surface of the minimal bounding sphere. This critical distance depends on the geometry of the opposite side. In some cases the minimal bounding sphere might have no more than 2 points on the surface no matter how many dimensions the sphere is in.

Share this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
In fact, the sphere passing through the four points is the minimal bounding sphere only for a single 1D subspace of the problem set (read: in very few cases).
The circumsphere S of a tetrahedron T is the minimum bounding sphere of T iff the circumcenter C of S lies inside T. If a, b, c, and 1 - a - b - c are the barycentric coordinates of C with respect to T, C lies inside T when a >= 0, b >= 0, c >= 0, and 1 - a - b - c >= 0.

In no interpretation I can think of does this solution space constitute a "1D subspace" of the space of T.

Share this post


Link to post
Share on other sites
Zipster: A jitter is an arbitrarily small perturbation. When discussing the dimensionality of a set, we only need to prove that it contains a k-dimensional manifold (no matter how small) to know that the set has at least dimension k. By jittering all four vertices of the tetrahedron, it seems to me that the set of situations where the minimum bounding sphere passes through all four points has dimension 12 (or as large as the set of all tetrahedrons).

Quote:
Original post by Christer Ericson
The circumsphere S of a tetrahedron T is the minimum bounding sphere of T iff the circumcenter C of S lies inside T. If a, b, c, and 1 - a - b - c are the barycentric coordinates of C with respect to T, C lies inside T when a >= 0, b >= 0, c >= 0, and 1 - a - b - c >= 0.

In no interpretation I can think of does this solution space constitute a "1D subspace" of the space of T.


That's what I thought.

Share this post


Link to post
Share on other sites
I would have thought that one through, had I known anyone would be paying attention [rolleyes].
You're all quite right, though. The 1D subspace I was thinking of was the in fact a subset of a 2D subspace - the one generated by moving one of the points along the surface of the existing sphere, as Zipster described. Worse still, the logic behind my thoughts was patently flawed [rolleyes], as made clear by:
Quote:
The circumsphere S of a tetrahedron T is the minimum bounding sphere of T iff the circumcenter C of S lies inside T.
What a lovely little lemma.

Consider me chastised.
Admiral

Share this post


Link to post
Share on other sites
Well we've spent a lot of time talking about the minimal bounding sphere, but we haven't actually brought up how to find this sphere [smile] Long story short, you can use the Miniball software to find the smallest enclosing ball in any dimension. It works, it's fast, and there's a paper linked if you want to know the theory behind it. I've been spending a few days trying to come up with a different method (not implying the miniball approach is bad, I'm just bored and curious), but that's for another day and another post.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!