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.