Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.csd.uwm.edu!gem.mps.ohio-state.edu!tut.cis.ohio-state.edu!ucbvax!agate!shelby!polya!rokicki
From: rokicki@polya.Stanford.EDU (Tomas G. Rokicki)
Newsgroups: comp.graphics
Subject: Tangents to three circles
Message-ID: <11391@polya.Stanford.EDU>
Date: 19 Aug 89 00:25:43 GMT
Sender: Tomas G. Rokicki <rokicki@Polya.Stanford.EDU>
Organization: Stanford University
Lines: 103

This particular puzzle (given three circles, find all circles tangental
to these three) was given as a programming puzzle at the 1987 ACM National
Programming contest.  A correct solution to this puzzle by Bob Alverson
of the Stanford team helped Stanford take the title that year.  As a
member of the team, I vaguely recall the solution; it was quite clever.
It's also not excruciatingly difficult, simply requiring a few insights.

I encourage everyone to try and find an analytical solution before
reading the spoiler which follows.



Given x_i, y_i, and r_i, 1 <= i <= 3.  Find all x, y, and r, such that
the circle described by the latter triple is tangent to all three
specified circles.

If two circles are tangent, then they can either be `interior'
circles, where the larger wholly includes the smaller, or they can
be `exterior' circles, where the only point shared by the circles
is the tangent point.

If C_i (the i'th circle, described by x_i, y_i, r_i) is `interior'
tangent to C (our result circle), then the distance between the
centers must be equal to the difference in the radii of the circles.

	(x-x_i)^2 + (y-y_i)^2 = (r-r_i)^2                (1)

If the circles are `exterior' tangent, then the distance must be
equal to the sum of the radii of the circles:

	(x-x_i)^2 + (y-y_i)^2 = (r+r_i)^2                (2)

The only difference between these equations is the sign of r_i.
For the remainder of the solution, we solve for interior tangents.
For all solutions, this algorithm should be iterated over both
positive and negative r_i's, for all i.  (Since there are three,
we would call it eight times.

If we expand (1), we have

        x^2 - 2xx_i + x_i^2 + y^2 - 2yy_i + y_i^2 = r^2 - 2rr_i + r_i^2   (3)

This gives us three equations and three unknowns, but there are some
nasty square terms.  Let's introduce another variable, k, such that

	x^2 + y^2 - r^2 = k                                    (4)

Now, we can rewrite the above equation as

        k - 2xx_i + x_i^2 - 2yy_i + y_i^2 = 2rr_i + r_i^2      (5)

which is nice and linear (the x_i, etc. are constants.)  Writing this
as a system of equations, we have

 / 2x_1  2y_1  2r_1 \ / x \   / x_1^2 + y_1^2 - r_1^2 \   / k \
 | 2x_1  2y_1  2r_1 | | y | = | x_2^2 + y_2^2 - r_2^2 | + | k |  (6)
 \ 2x_1  2y_1  2r_1 / \ r /   \ x_3^3 + y_3^3 - r_3^3 /   \ k /


If the first square matrix is nonsingular, we can easily solve this
system for x, y, and r, in terms of k.  Our solution is of the form

      x = a_x + b_x k
      y = a_y + b_y k                                   (7)
      r = a_r + b_r k

where all of the a_i and b_i are numbers dependent only on c_i, so
they can be directly evaluated.

Our only remaining task is to evaluate k.  Taking our definition of
k from (4), we have

     x^2 + y^2 - r^2 = k                                (8)

or

     (a_x + b_x k)^2 + (a_y + b_y k)^2 - (a_r + b_r k)^2 = k   (9)

which is an easily solved quadratic equation for k.  If the quadratic
equation has no solutions, there are no solutions for this set of
interior/exterior assignments.  Otherwise, we solve for the (up to)
two possible values of k.  We reject any solutions which would make
r negative (they will be found by symmetry with another set of
interior/exterior assignments, only with r correctly positive.)
And this gives us x, y, and r, easily.

If the quadratic equation has a `0' term for k^2, then it
is a simple linear equation for k with one solution.

There remain only singularities.  Specifically, if the original
input matrix is singular, this solution will fail, even though
there may be solutions.  However, it is easy to show (and left as
an exercise) that if there is a solution, a constant may be added
to all input x_i's, y_i's, or r_i's to make the matrix nonsingular.
This constant must then be subtracted (in the case of x_i's or y_i's)
or added (in the case of r_i's) to the resulting x, y, or r,
respectively, to find the real solution.

Writing this up as a numerically stable algorithm must be done
carefully, but is not terribly difficult.  It just looks a lot
uglier than it really is.

-tom