Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!samsung!shadooby!egrunix!nucleus!mjb From: mjb@nucleus.UUCP (Mark Bobak) Newsgroups: comp.graphics Subject: Re: smallest sphere enclosing a set of points Message-ID: <5497@nucleus.UUCP> Date: 7 Dec 89 20:35:36 GMT References: <28@ <658@cditi.UUCP> <4893@skinner.nprdc.arpa> <679@dbrmelb.dbrhi.oz> Reply-To: mjb@nucleus.UUCP (Mark Bobak) Organization: The Nucleus Public Access Unix, Clarkston, MI Lines: 56 In article <679@dbrmelb.dbrhi.oz> davidp@dbrmelb.dbrhi.oz (David Paterson) writes: > > >In article <4893@skinner.nprdc.arpa>, malloy@nprdc.arpa (Sean Malloy) writes: >> >> Then generalize it. Find the largest distance between any two points. >> Take all the pairs of points with that separation, and average their >> coordinates. This will give you the center of the sphere; the distance >> from that point to any of the equidistant points will give you the >> radius. >> >> Each point in the set of points with largest separation gets counted >> twice in the averaging, but since you divide by the number of endpoints, >> not the number of separations, the averaging still works. >> >Sorry, still doesn't work, consider, for instance the circle surrounding >points (-1,0),(1,0),(0,2). > >My solution was (see earlier posting) to solve simultaneously three >quadratic equations using Newton's method. Does anyone know a quicker >way? >----------------------------------------------------------------------- >David Paterson, CSIRO, Highett, 3190, Victoria, Australia Hmm....Could everyone be overlooking the obvious? It seems to me, for a circle, sphere, hypersphere, (in 2D,3D,4D, or N-D for that matter) that will enclose a set of points, simply find the max x,y,z and min x,y,z. Then, the center point should be: ( Average(maxx,minx),Average(maxy,miny),Average(maxz,minz) ) Then, your radius would be longest of the distances from center point to any point. I tried a couple examples, let's use (-1,0),(1,0),(0,2) here: Max X = 1, Min X = -1, Max Y = 2, Min Y = 0, Then, Average X = (1+(-1))/2 = 0 and Average Y = (2+0)/2 = 1 So, Center Point = (0,1) Distance from (0,1) to (-1,0) is: Sqrt((0 - (-1))^2 + (1 - 0)^2) = Sqrt(1+1) = Sqrt(2) = 1.414 Distance from (0,1) to (1,0) is: Sqrt( (0 - (-1))^2 + (1 - 0)^2 ) = Sqrt(1+1) = Sqrt(2) = 1.414 Distance from (0,1) to (0,2) is: Sqrt( (0 - 0)^2 + (1 - 2)^2 ) = Sqrt(0+1) = 1 Therefore, we have C(0,1) and radius Sqrt(2). This solution should work for N-Dimensional space. -- Mark Bobak The Nucleus Public Access Unix, Clarkston, Mi. mjb@nucleus.mi.org mjb@m-net.ann-arbor.mi.us