Path: utzoo!attcan!uunet!cs.utexas.edu!rutgers!att!alberta!uqv-mts!ualtavm.bitnet!ECULHAM
From: ECULHAM@UALTAVM.BITNET (Earl Culham)
Newsgroups: comp.graphics
Subject: Re: Ray Traced Bounding Spheres
Message-ID: <462@UALTAVM.BITNET>
Date: 11 May 89 20:10:30 GMT
References: <17241@versatc.UUCP>
Reply-To: ECULHAM@UALTAVM.BITNET
Organization: University of Alberta VM/CMS
Lines: 38
Disclaimer: Author bears full responsibility for contents of this article

In article <17241@versatc.UUCP>, ritter@versatc.UUCP (Jack Ritter) writes:
 
>Given a cluster of points in 3 space, is there
>a good method for finding the minumum radius
>sphere which encloses all the points?  If not
>minumum, at least "small"?  Certainly it should
>be tighter than the sphere which encloses the
>minimum bounding box.
>
>I have a feeling the solution is iterative. If
>so, I could provide a good initial guess for the
>center & radius.
>
 
The solution is not iterative. A simple solution is available in
a two step process, and is characterised by whether three, or only two
of the points are on the surface of the optimal sphere.
 
Given the points, A, B, and C.
Searching for the center of the optimal sphere, P, with the smallest
radius, R.
 
Checking the midpoints.
 
set P = point halfway between A and B
set R = 1/2 of length from A to B
If length from C to P is less than or equal to R ---> done
Repeat with line A-C, and B-C if needed.
 
Extending the midpoints at right angles.
 
build the line which intersects A-B at a right angle through the midpoint
  of A-B, call the line D
build the line which intersects A-C at a right angle through the midpoint
  of A-C, call it E.
P is the point where D and E intersect. (Solve the simultaneous equations
R is the length A-P.