Sphere that goes through 4 vertices of tetrahedron
Author
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!!!
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]
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]
Author
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.
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.
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.
I think The Admiral and Zipster are wrong on this one. Read here: http://steve.hollasch.net/cgindex/geometry/sphere4pts.html
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
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
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]
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.
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?
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.
----
I'm guessing 2, considering the case of a very long thin tetrahedron.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement