Michael Andrews wrote:
> 
> 
> I seem to remember the sequence goes something like this:
> 
> Find the two points furthest apart and set a sphere so that they are on
> the diameter. If both other points are inside the sphere you are done.
> 
> If one or two points are outside the sphere find the point furthest
> outside the sphere. Produce the sphere that has the circumcircle of the
> three points as its great-circle. If the fourth point is inside this
> sphere you are done.
> 
> Otherwise find the sphere with all four points on the surface.
> 
> I think this is right ...
> 
> Mike Andrews.

I think you are right.  I don't think it would be too hard to make a
macro to do that either.  Now I guess the next thing is to find the
smallest oriented bounding box, and see which one is smaller.  If one is
always smaller.  

-- 
Dan Johnson 
http://www.livejournal.com/userinfo.bml?user=teknotus
http://www.geocities.com/zapob

Post a reply to this message

Dan Johnson wrote:

> 
> I think you are right.  I don't think it would be too hard to make a
> macro to do that either.  Now I guess the next thing is to find the
> smallest oriented bounding box, and see which one is smaller.  If one is
> always smaller.
> 

Do bounding boxes with sheer work?  If they do I think you can get even
closer.  Then you could define it as a cube, and a matrix.  I think that
in an ideal bounding box all vertices would also be vertices of the
inclosed tetrahedron.  

Dan Johnson 
http://www.livejournal.com/userinfo.bml?user=teknotus
http://www.geocities.com/zapob

Post a reply to this message

Yes, of course, you're right about my wording.  I see what you are talking
about WRT to the smallest sphere, too.  Nearly coplanar points would produce
an enormous sphere if you only allowed the points to be on the surface of
the sphere.

"Tor Olav Kristensen" <tor### [at] hotmailcom> wrote in message
news:web.3dfe7e1187ba9bcf38149fba0@news.povray.org...
>
> Rick Gutleber wrote:
> >If the points are _tangential_ to the sphere, wouldn't there only be one
> >solution?
>
> Rick,
> I don't think one can say about points
> that they can be tangential to anything.
>
> You probably mean that they are on the
> surface of the sphere.
>
> If you have four points in 3D space that
> are not coplanar (*), then yes; there
> are only one specific sphere that have
> them all on its surface. (And the macro
> I mentioned in my other post finds that
> very sphere.)
>
> This sphere will, of coarse, enclose a
> tetrahedron that has these four points
> as its vertices.
>
> But as Peter and I pointed out, this is
> not always the most optimal sphere to
> choose for bounding of such a tetrahedron.
>
> It will in some cases be possible to
> find spheres with smaller radii, that
> encloses the tetrahedron.
>
> And in these cases only 2 or 3 of the
> 4 points (vertices) will be on the surface
> of the sphere. The other 2 or 1 will be
> inside it.
>
> The problem is now to find the bounding
> sphere with the smallest radius.
>
>
> (*) More precisely I mean:
> vdot(p1 - p0, vcross(p2 - p0, p3 - p0)) != 0
>
>
> Tor Olav
>
>
> >"Peter Popov" <pet### [at] vipbg> wrote in message
> >news:6ldgvu8m3haqih3b2cud5narcqn8p82pvi[at]4ax.com...
> >> On Wed, 11 Dec 2002 11:45:10 -0500, "Rick Gutleber" <ric### [at] hiscom>
> >> wrote:
> >>
> >> >I bet the Graphics Gems books have code that will allow you to
determine
> >a
> >> >sphere tangential to 4 points in 3-space.  The code for those books
can
> >be
> >> >found on-line.
> >>
> >> There sure is, but keep in mind that the circumscribed sphere is
> >> usually not the smallest sphere containing four points.
>
>

Post a reply to this message

In article <3DFF8126.37A7E1BE@hotmail.com>,
 Dan Johnson <zap### [at] hotmailcom> wrote:

> I think you are right.  I don't think it would be too hard to make a
> macro to do that either.  Now I guess the next thing is to find the
> smallest oriented bounding box, and see which one is smaller.  If one is
> always smaller.  

I am almost certain the box is always smaller. The optimal sphere 
bounding is a circumscribed sphere around a regular tetrahedron. The 
optimal box bounding of that tetrahedron would have each corner of the 
tetrahedron at a corner of the box, the least optimal (I think) would 
have two edges of the tetrahedron against opposing faces of the box, 
parallel to different axii (the best case, rotated 45 degrees around one 
axis).

For a regular tetrahedron with 1-unit edges, the best bounding sphere 
has a radius of sqrt(3)/sqrt(8) (~0.612), the best-case box a 
2/sqrt(8)-unit (~0.707) cube, the worst-case box a 1x1x2/sqrt(8) 
(1x1x~0.707) box. The sphere has a volume of 0.96 units^3, the cube 
0.353 units^3, and the box 0.707 units^3.

For optimal bounding of irregular tetrahedrons, both will be less 
efficient, but I think a box will always be better. Even if the 
tetrahedron is a thin rod along a diagonal of the box (the worst case), 
the sphere will have a larger volume (having a diameter about equal to 
the length of the diagonal of the box).

This is for axis-aligned boxes, if you use oriented boxes the bounding 
of a regular tetrahedron or some irregular tetrahedrons (those you can 
get by applying an affine transformation to a regular tetrahedron) is 
always the best case, for other tetrahedrons it still improves.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message