Sign in to follow this  

Sphere that goes through 4 vertices of tetrahedron

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

Hello! I need a stable and fast way of creating a sphere that goes through the 4 vertices of a tetrahedron. I solved it in a hackish way but sometimes the algortihm creates bad result... How would you solve this problem? Thanks a lot!!!

Share this post


Link to post
Share on other sites
This isn't possible in general. Is there some constraint on your tetrahedron you're not telling us about?

For example, (0, 0, 0), (1, 1, 0), (2, 1, 0), (767, 1, 1) will have no such sphere. Not by a long shot.

Edit: That's not actually true. It is for (0, 0, 0), (1, 1, 0), (2, 1, 0), (767, 1, 0), though.

Regards
Admiral

[Edited by - TheAdmiral on November 26, 2006 7:25:09 PM]

Share this post


Link to post
Share on other sites
Yeah thats true. I need this for making a 3d delaunay triangulation to find out if one point is inside the sphere of the tet. The solution should be very fast and should make nearly correct results.

Share this post


Link to post
Share on other sites
It's possible to find a sphere that contains all four points, but as TheAdmiral aluded to your original problem is super-constrained, meaning that in general there won't be a solution. However that doesn't mean you won't get lucky and be handed a set of four points that are all on the surface of a sphere, which is what makes a solution possible in rare cases.

Off the top of my head, what you could do is take all combinations of 3 points and build a sphere from each of them. Then choose the smallest sphere that contains all the points. The reason this if off the top of my head is because I haven't considered the possibility of none of the spheres meeting the criteria or what to do when (if?) this case does occur.

Share this post


Link to post
Share on other sites
On second thoughts, the system is actually overdetermined only on a 1-dimensional subspace.

As alvaro's link establishes, we need any triplet of points to be non-collinear and all four to be non-planar. Given this, however, a sphere necessarily does exist, by rank-nullity. Who'd have guessed? [rolleyes].

We can picture it this way:
Pick any three points. We can create a unique circle passing through these. Now if we consider this circle to be the intersection of some plane with our desired sphere, it's clear that we can grow or shrink the sphere (and orient it to either side of the plane) so that it incorporates the remaining point.

Algorithmically, the aforementioned link gives you plenty of ideas to work with.

Regards
Admiral

Share this post


Link to post
Share on other sites
Yeah I'm silly, for some reason my mind was focusing too much on the degenerate 2D coplanar case to realize that in the general 3D case each triplet of points would lie on the circumference of a circular cross section of the sphere. I'm just no good with algorithms I can't draw on paper [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiralWe can picture it this way:
Pick any three points. We can create a unique circle passing through these. Now if we consider this circle to be the intersection of some plane with our desired sphere, it's clear that we can grow or shrink the sphere (and orient it to either side of the plane) so that it incorporates the remaining point.

Funny. That's exactly how I figured out that a solution must exist. Then I just googled a little and I found that link.

Share this post


Link to post
Share on other sites
Quote:
Original post by dali
Yeah thats true. I need this for making a 3d delaunay triangulation to find out if one point is inside the sphere of the tet. The solution should be very fast and should make nearly correct results.


Let say you have a sphere with minimal volume that contains all four points, let say that you need to encapsulate a non degenerate tetrahedron. Now answer the question: How many points must be part of the surface of the sphere at minimum?

Share this post


Link to post
Share on other sites
Let say you have a sphere with minimal volume that contains all four points, let say that you need to encapsulate a non degenerate tetrahedron. Now answer the question: How many points must be part of the surface of the sphere at minimum?

----

I'm guessing 2, considering the case of a very long thin tetrahedron.

Share this post


Link to post
Share on other sites

This topic is 4034 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this