From: bob@black.ox.ac.uk (Bob Douglas)
Subject: Re: Sphere from 4 points?
Organization: Oxford University Computing Service, 13 Banbury Rd, Oxford, U
Lines: 94
Originator: bob@black

In article <2406@hcrlgw92.crl.hitachi.co.jp> steve@hcrlgw (Steven Collins) writes:
>In article <1qkgbuINNs9n@shelley.u.washington.edu> bolson@carson.u.washington.edu (Edward Bolson) writes:
>>Boy, this will be embarassing if it is trivial or an FAQ:
>>
>>Given 4 points (non coplanar), how does one find the sphere, that is,
>>center and radius, exactly fitting those points?  I know how to do it
>>for a circle (from 3 points), but do not immediately see a 
>>straightforward way to do it in 3-D.  I have checked some
>>geometry books, Graphics Gems, and Farin, but am still at a loss?
>>Please have mercy on me and provide the solution?  
>
>Wouldn't this require a hyper-sphere.  In 3-space, 4 points over specifies
>a sphere as far as I can see.  Unless that is you can prove that a point
>exists in 3-space that is equi-distant from the 4 points, and this may not
>necessarily happen.
>
>Correct me if I'm wrong (which I quite possibly am!)
>
>steve

Sorry!! :-)

Call the four points A, B, C and D. Any three of them must be
non-collinear (otherwise all three could not lie on the surface
of a sphere) and all four must not be coplaner (otherwise either
they cannot all lie on a sphere or they define an infinity of them).

A, B and C define a circle. The perpendicular bisectors of AB, BC
and CA  meet in a point (P, say) which is the centre of this circle.
This circle must lie on the surface of the desired sphere.

Consider the normal to the plane ABC passing through P. All points
on this normal are equidistant from A, B and C and its circle (in
fact it is a diameter of the desired sphere). Take the plane
containing this normal and D (if D lies on the normal any
plane containing the normal will do); this plane is at right angles
to the ABC one.

Let E be the point (there are normally two of them) on the circumference
of the ABC circle which lies in this plane. We need a point Q on the
normal such that EQ = DQ. But the intersection of the perpendicular
bisector of ED and the normal is such a point (and it exists since D is
not in the plane ABC, and so ED is not at right angles to the normal).


Algorithm:

Is the sphere well defined?
    (1) Check that A and B are not coincident (=> failure).
    (2) Find the line AB and check that C does not lie on it (=> failure).
    (3) Find the plane ABC and check that D does not lie in it (=> failure).
Yes. Find its centre.
    (1) Find the perpendicular bisectors of AB and AC.
    (2) Find their point of intersection (P).
    (3) Find the normal to the plane ABC passing through P (line N).
    (4) Find the plane containing N and D; find the point E on the
	ABC circle in this plane (if D lies on N, take E as A).
    (4) Find the perpendicular bisector of ED (line L)
    (5) Find the point of intersection of N and L (Q).
Q is the centre of the desired sphere


Pictures:

(1) In the plane ABC

			A


                                P
                 
                B                               C

(2) At right-angles to ABC, in the plane containing N and D

			E


                                                          D

    line N
    --------------------P-------------Q---------------------------


Numerically:

If ED << EP then Q will be very close to P (relative to the radius
of the ABC circle) and subject to error. It's best to choose D so
that the least of AD, BD and CD is larger than for any other choice.
-- 
Bob Douglas              Computing Services, University of Oxford
Internet:                bob@oxford.ac.uk
Address:                 13 Banbury Road, Oxford OX2 6NN, UK
Telephone:               +44-865-273211