View Question
Q: Merging Spheres ( Answered ,   1 Comment )
 Question
 Subject: Merging Spheres Category: Science > Math Asked by: tfpsoft-ga List Price: \$10.00 Posted: 06 May 2004 09:50 PDT Expires: 05 Jun 2004 09:50 PDT Question ID: 342125
 ```Given two spheres--each defined as an x,y,z coordinate in 3D space representing the center of the sphere, and a radius--what is a simple formula for merging the spheres together? The goal is to produce a new sphere of the smallest possible radius that fully encompasses the other two.``` Request for Question Clarification by andrewxmp-ga on 06 May 2004 21:57 PDT ```I have an idea for an answer, but it seems quite simple, and perhaps is not what you are looking for. On the other hand, it seems correct to me. The first set of equations would produce a sphere in which the first two spheres could fit, assuming that the first two are side-by-side (not overlapping somehow) and that the "new" sphere is hollow, obviously, as it is encompassing the first two. Please let me know, and comments from other researchers to double-check would be helpful as well. The position of this new sphere would be given (where Xs1 is the X coordinate of sphere #1, Ys1 is the Y coordinate of sphere #1, and so forth) by: X coordinate of new sphere: [(Xs1+Xs2)/2] Y coordinate of new sphere: [(Ys1+Ys2)/2] Z coordinate of new sphere: [(Ys1+Ys2)/2] The radius of the new sphere would be given by: {[2X(radius of sphere #1)]+[2X(radius of sphere #2)]}/2 If the first spheres are NOT exactly adjacent to each other, but at any arbitrary points in space (this is probably the universal formula you are looking for), then the position would be determined the same way, but the radius would be given as follows: [(Xs1-Xs2)+(Ys1-Ys2)+(Zs1-Zs2)]^(1/3) PLUS [(radius of sphere #1)+(radius of sphere #2)] (the first term is basically the pythagorean theorum in 3 dimensions, to find the distance between the centers of the two pheres, which is then added to one radii of each) How does this look to everyone? I'm pretty sleepy, been studying all day :( If this is correct, I will gladly post it as an answer. Thanks! -Andrewxmp``` Clarification of Question by tfpsoft-ga on 07 May 2004 03:19 PDT ```Hmm. I agree, the answer should be simple, but I don't think what you've posted is right. Of course, I'm pretty sleepy too, hence why I posted the question. :-) As you guessed, I *do* need a general case solution, assuming not only that the spheres are not adjacent--they may be anywhere in space--but also assuming that the spheres may be intersecting. For sake of argument, let's say I can easily throw away the case where one sphere is already fully inside the other sphere, but I still need to deal with the case where one sphere is partially inside the other sphere. I've been using close to the same formula as you for radius. [Oh... on a side note... the distance formula, aka. "3D Pythagoras", should be squared root, not cubed root. I know it seems like it should be cubed root because we've added a term, but it isn't. A quick proof for this is to assume that z=0... you should get the same answer as you would in 2D.] I'm using: distance = ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 -z1)) ^ 1/2 r3 = (r1 + r2 + distance) / 2 Divided by two, of course, as adding the radii plus the distance gives us the new diameter, not the radius. I'm pretty sure that's right. It's the position calculation that's throwing me. Averaging the center points of the spheres, as you have done, won't work. As a case example, try taking a very large sphere and putting it next to a very small sphere. If I simply add the centers and divide by two, the small sphere has too much influence on the position... the answer is clearly wrong. Here's a picture, with everything measured in my graphics program, to show you what I mean: http://www.kitchencloset.com/home/lisa/circles1.gif [Incidentally, it would be really nice if Google let you post pictures directly.] The solution I've tried is to create a line from outer edge to outer edge of both spheres, then bisect the line. I've been doing this like so: A = center of first sphere B = center of second sphere vector V = B - A Normalize the vector (V). Get a point (C and D) along the vector on the outer edge of each sphere. C = A - (r1 * V) D = B + (r2 * V) Bisect the line between C and D. New center = (C + D) / 2 This seems right, and when I sketch it out on paper it seems to work out okay, but when I try to do this on the computer something isn't working. Either my math is fubar and I can't get my head straight enough to see it right now, or my math's okay and there's a bug in my program... and I just can't see it right now, either. :-) Sigh. Thanks!``` Request for Question Clarification by mathtalk-ga on 07 May 2004 12:48 PDT ```Hi, tfpsoft-ga: You were definitely on the right track with using the vector between the two centers in the wee hours today. If you are still interested in an Answer, I'd be happy to oblige, but I can see that you were closing in on the solution for yourself. regards, mathtalk-ga``` Clarification of Question by tfpsoft-ga on 13 May 2004 00:49 PDT `Thanks mathtalk! Feel free to post that as an answer.`
 ```Thanks, tfpsoft-ga: As the analysis shows, there are two cases to consider. If one sphere is inside the other, then the larger sphere is the bounding sphere. Otherwise take the points on the two spheres which are furthest from each other. These two points will fall on a line passing through both spheres' centers, and in this respect the analysis would be the same regardless of the dimension of the "spheres". A moments reflection shows that by this construction the distance between the two extremal points exceeds the diameter of either sphere, so that a bounding sphere tangent to each of the two spheres at their respective extremal points will share the common line passing through its center & creating a diameter for the bounding sphere between the two points. [The diameters to both spheres at a point of tangency are collinear because they are perpendicular to the surface of the spheres at that point.] Let (x1,y1,z1) be the center of the first sphere and let (x2,y2,z2) be the center of the second sphere. Let r1 and r2 be their respective radii. Now the diameter of the bounding sphere is: r1 + SQRT( (x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 ) + r2 as the bounding diameter extends a distance r1 and r2 respectively on either side of the line segment joining the centers of the two original spheres. The _radius_ of the bounding sphere is half this value. Finally the center of the bounding sphere is the midpoint of this bounding diameter. To express this concisely (hopefully in a manner conducive to clear but efficient programming!), define the vector: V = (x2,y2,z2) - (x1,y1,z1) The center of the bounding sphere is then: (x3,y3,z3) = (x1,y1,z1) + (0.5 * (r2 + |V| - r1)/|V| ) V where |V| is the length of V. This notation also compactly expresses the radius of the bounding sphere by: r3 = 0.5 * (r1 + |V| + r2) best wishes, mathtalk-ga```
 ```Hi, The Google Answers Editors might not see or act upon andrewxmp-ga's request until Monday, but the Customer (tfpsoft-ga) does not need to do anything in this circumstance. While we are waiting, let me go ahead and fill in an observation about the "cases" that arise in this problem. As noted there are at least the two cases that one of the two original spheres is contained entirely in the other, or that an encompassing sphere will be tangent to each of those two spheres (at farthest points of intersection along the line drawn through the two spheres' centers). To prove that these are the only two possible cases, first note that the line between the centers is at least well-defined unless the two centers coincide. If the centers A,B coincide, then clearly the encompassing sphere would be the larger of the two original spheres. Assuming the centers A,B are distinct, the vector V = B - A defined by tfpsoft-ga is nonzero. Let's use the length |V| of this vector rather than redefine the vector V to be normalized V/|V|. Thinking of a "number line" generated by distances along the direction defined by V, we have the first center A at the origin and the second center B at distance |V| "forward" along the line. Going backward from A distance r1 (to point C) would correspond to number -r1 on this line and going forward from B distance r2 (to point D) would correspond to number |V| + r2. The formulas proposed by tfpsoft-ga amount to using the interval [-r1, |V| + r2] as the diameter of a third sphere. Its center is given in tfpsoft-ga's notation as midpoint (C + D)/2, and its radius would be half the length of the diameter: r3 = (|V| + r2 + r1)/2 A B |---------> ... ---------+----|-------------+---- ... -r1 0 |V|+r2 C . D In order for the proposed sphere to encompass the two original spheres it is necessary and sufficient for the new diameter [-r1, |V| + r2] to contain the original diameters [-r1, r1] and [|V| - r2, |V| + r2]. To restate the geometric condition algebraically, inclusion of the diameters means: (1) r1 <= |V| + r2 (2) -r1 <= |V| - r2 If, in the alternative, condition (1) fails, it means that: r1 > |V| + r2 which implies that the diameter of the second sphere is contained in that of the first sphere: [|V| - r2, |V| + r2] contained in [-r1, r1] Likewise the failure of condition (2) implies: -r1 > |V| - r2 that the diameter of the first sphere is contained in that of the second: [-r1, r1] contained in [|V| - r2, |V| + r2] Therefore tfpsoft-ga's approach "encompasses" all the possibilities! A couple of notes on generalizations. The basic construction here works, for two "spheres", in any dimension. This may be glimpsed in the fact that the argument above reduces the issues to relations among the one-dimensional diameters of the the "spheres". If more than two "spheres" are involved, then the problem of finding an encompassing sphere can be a challenging but algorithmically tractable one. Even in two-dimensions and with the radii reduced to zero (points), the problem of a minimal bounding circle is a fascinating exercise. regards, mathtalk-ga```