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