if I know two ellipse, how could I get the common tangent between them?

by algebra, I got this equations
already(http://mathforum.org/library/drmath/view/61599.html):

a1*x1*x1+b1*x1*y1+c1*y1*y1+d1*x1+e1*y1+f1=0  (x1,y1) is on ellipse 1
a2*x2*x2+b2*x2*y2+c2*y2*y2+d2*x2+e2*y2+f2=0  (x2,y2) is on ellipse 2

(2*a1*x1+b1*y1+d1)/(b1*x1+2c1y1+e1) = (y2-y1)/x2-x1)  the slope of
tangent at point(x1,y1) equals the slop of the common tangent

(2*a2*x2+b2*y2+d2)/(b2*x2+2c2y2+e2) = (y2-y1)/x2-x1)  the slope of
tangent at point(x2,y2) equals the slop of the common tangent

based on those four euqations, we should be able to get the solutions
(x1,y1)(x2,y2)

but does anybody know how to get it and maybe in a computer program
how to formalize it to code? or get the approximate solutions by
iterations. 
I know it's kind of difficult to solve this problem, I would like to
pay more based on the speed and degree of the your work. thanks!

---

Request for Question Clarification by mathtalk-ga on 15 Sep 2004 18:31 PDT

Hi, jdragon2k-ga:

Intuitively there are four solutions if the two ellipses do not
overlap, so presumably there is a quartic polynomial lurking somewhere
in the Answer.

One simplification I would propose is to assume, without loss of
generality, that one of the ellipses is a unit circle centered at the
origin and that the other ellipse is in "standard" orientation with
respect to having major/minor axes parallel to the coordinate axes.

For the list price offered, I could either show why such a reduction
is "without loss of generality" or show how to solve the problem once
it is reduced in that way.  But perhaps you would prefer to think
about the problem anew with these "hints" to see if you can make
further progress!

regards, mathtalk-ga

---

Request for Question Clarification by mathtalk-ga on 16 Sep 2004 19:35 PDT

Google Answers Researchers are not permitted to communicate with
Customers outside of this site.  Note however that for the list price
offered I've agreed to show you how to reduce the problem to the case
of a unit circle and an ellipse with axes parallel to the coordinate
axes.  This is a general reduction, applicable to any two ellipses in
whatever orientation.  If the ellipses overlap to begin with, then the
resulting circle and ellipse will again overlap.

It might be helpful to know the sort of computing application you have
in mind.  If there is a desire to write a command line program which
takes an input file containing the polynomial coefficients and writes
an output file describe the common tangents, if any, that might appeal
to one sort of programmer.  A subroutine geared toward repeatedly
solving a series of similar problems involving "moving" ellipses might
appeal to another kind.

Note in particular the case when one ellipse is strictly inside the
other.  Then there are no tangent lines to one ellipse that are also
tangent to the other ellipse.  Depending on how they intersect, a pair
of overlapping ellipses may have two or four common tangents
(including the degenerate case of the ellipses themselves being
tangent, which should actually be counted as a double tangent line).

regards, mathtalk-ga

---

Clarification of Question by jdragon2k-ga on 16 Sep 2004 21:13 PDT

sorry, the struct definition of ellipse should include the center too

double center_x;
double center_y;

---

Request for Question Clarification by mathtalk-ga on 28 Sep 2004 14:39 PDT

Hi, jdragon2k-ga:

I've reviewed carefully my suggestion of taking the two tangents from
the center of the ellipse to the unit circle as a starting point for a
"bisection" approach.  I believe this to be a sound approach, although
I can appreciate that the mere suggestion by itself leaves you with
many open questions/doubts about how to proceed in a programming
implementation.  [A computationally simpler but conceptually more
obscure approach is possible, but I would recommend an approach which
is easily understood for a "reference" implementation.]

I believe that a thorough Answer to your Question would require more
time than is reasonable to spend based on the list price you've
offered.  According the Google Answers Pricing Guidelines:

http://answers.google.com/answers/pricing.html

multi-part Questions would normally be at least $50.

Here are some of the issues that I see as belonging to a complete solution:

1. stable computation of quadratic roots
2. mapping an ellipse to the unit circle
3. tangents to the unit circle from an outside point
4. parametric equation of a line
5. locating real roots of a quadratic (rule of signs, etc.)
6. tangents to the unit circle from center of an ellipse
7. bisecting arcs of the unit circle
8. four mutual tangents between unit circle and non-overlapping ellipse
9. inverting the map from ellipse to the unit circle

If you hope to encourage a Researcher to assist you at the current
price offered, I suggest that you clarify that you are able to "fill
in the details" for almost all of the above implementation issues by
yourself.  Only a thorough grasp of most of these basics would allow
someone to provide a satisfactory yet concise explanation of the
remaining obstacles.

regards, mathtalk-ga

It is simply a one dimensional root finding problem, so there is no
special difficult in solving numerically by bisection in the case of
two ellipses that do not overlap to obtain all four (real) solutions.

Consider, since you agree the general problem can be reduced to this
one, a unit circle at the origin and an ellipse drawn anywhere outside
that.

From the center of the ellipse find the two lines tangent to the unit
circle.  This is simply trigonometry if you wish to do it numerically,
for the line from the ellipse center to the circle center (origin) is
the hypotenuse of both right triangles formed by the two tangents and
the radial line segments to the two points of tangency.

As you "rotate" from one tangent to the other, e.g. by moving the
point of tangency, the circle's tangent line at that point goes from
intersecting the ellipse twice (e.g. through the center) to
intersecting once (a double point, a common tangent line), to no
intersections, back around to insecting once (another common tangent
line), and then back to intersecting twice (until we reach the other
line through the ellipse's center).  If you keep on going around the
"back" of the circle, this pattern repeats for a total of four common
tangent lines in all.

Bisection is guaranteed to be a success if you can reduce the problem
to find the root of a continuous function which is positive at one end
of an interval and negative at the other.  Of course if the function
is "smoother" than merely continuous, we can use a variety of faster
solving methods.  Brent's hybrid between bisection and false position
comes to mind, but in fact for these polynomial curves one can take
derivatives analytically and use Newton's method.

In fact a fourth degree polynomial even has (after a fashion) a closed
form solution in terms of radicals.  I'm sure it would be more trouble
than it's worth since you seem to need a computer program to provide
the results, but it can actually be done with algebra.

regards, mathtalk-ga

Here's another way to think about it that may be clearer, just
exchanging the roles of the circle and ellipse.

Given a point on the ellipse, find the tangent to it there and by
expressing it in "normal form" determine the closest distance of that
line to the origin.

The ellipse tangent is also tangent to the unit circle precisely when
the distance to the origin (at the point of closest approach, as given
by the absolute value of the constant in the normal form of its
equation) is 1.

In the case of the ellipse and the circle not overlapping, the
circumference of the ellipse can be split into two subintervals first
by picking the two tangents to the ellipse that pass through the
center of the circle (namely the origin), and each of those
"intervals" subdivided once again by picking the two tangents to the
ellipse where the line from the origin to the center of the ellipse
cuts the ellipse.  There will be one "root" in each of the four
subintervals formed in this fashion, and you can use the function:

      (nearest distance of ellipse tangent to origin) - 1

to define the four roots.

regards, mathtalk-ga

I can't understand this part here, not sure it will work, please
clarify more it for me, thanks!

"each of those "intervals" subdivided once again by picking the two
tangents to the ellipse where the line from the origin to the center
of the ellipse
cuts the ellipse."


I know we need to find a point between two tangent point. The tangent
on this point should be unit 1 distant from the origin. Are you saying
that get a line by connecting the unit circle's center and the
ellipse's center, the line's intersections with the ellipse are such
points? I am not sure whether you can guarantee this in mathematics.

Could you answer my this question, instead of deleting it? Thanks!

Let (cos(t),sin(t)) be an arbitrary point on the unit circle.

The tangent line to the unit circle in the (x,y)-plane at that point is:

y = - cot(t)*( x - cos(t) )  +  sin(t)

because the slope of the tangent line is the negative reciprocal of
the slope of the radial line at the same point (they are perpendicular
to each other).

Now the question is, given another ellipse, which by rotation may be
assumed in "standard position" (axes paralle to the coordinate axes):

  (x-h)^2 + (y-k)^2
  -------   -------  =  1
    A^2       B^2

for what values of the parameter t (between 0 and 2pi radians) will
the tangent line intersect the above ellipse in a double root (ie. at
a tangent to the ellipse)?

Since the line gives us y in terms of x (and the parameter t), we can
in principle simply substitute for y in terms of x in the ellipse
equation.  Now we have a quadratic in terms of x (but with
coefficients depending on t), and the condition for the quadratic to
have a double root is well known to be that its discriminant is zero. 
Once we've expressed the discriminant in terms of t, the problem is
reduced to finding values of t that make the discriminant zero, ie.
finding roots of this discriminant as a function of t.

What I had to say about the line connecting the center of the circle
and the ellipse was merely intended to convey that with a little
thought you can easily divide the range [0,2pi] into four subintervals
in which (assuming the ellipse lies entirely outside the unit circle)
exactly one root/tangent occurs per subinterval.

regards, mathtalk-ga

yes, now you return to the old problem ---- how to solve the
equations?  In fact, I even simply the equations I mentioned before to
something like :
 a*cos(t)+b*sin(t)+c*sint(2t)=0 
I just don't know how to solve it and I believe the thing you
mentioned here will result into something like it too. This doesn't
necessarily give you the t. even it is one unknown variable and one
equation.

If you are satisfied with a numeric solution, then the bisection
method for a continuous function f(t) on some interval [a,b] such
that:

  f(a)*f(b) < 0

is guaranteed to converge to a root.  I really thought this is where
you were headed with your discussion of a computer program.

If you want a symbolic solution, then instead we should focus on
deriving a fourth degree (quartic) polynomial (in a single unknown)
that describes the mutual tangent condition.   I can post just such an
equation as an Answer if you wish, for the problem of a unit circle
and an ellipse lying entirely in the half-plane y > 1 (not necessarily
in standard position).  The general situation can be reduced to this
one, in which the circle's tangents are easily parameterized by the
x-coordinate where they intersect the horizontal line y=1.

regards, mathtalk-ga

yes, I know it's easy to use f(a)*f(b)<0 to do binary search. I have
no problem with that algorithm. The thing is how to get the boundary
of a, b. As you mentioned, the first time use the tangent point to
devide the ellipse into two part. We know that tangent at those two
points will be within unit 1 distant from origin. My problem is how to
guarrantee your pick point to subdevide the two ellipse arc is unit 1
distant from origin. You said something to solve that parameter t
equation. I think this will return to the old problem of equations.

What I want to know is how do you get the two boundary points to
subdevide the two ellipse arcs. I don't think your solution by
connecting two centers and get the intersections with the ellipse is
the answer.

The NSolve function in Mathematica easily solved the problem for two
ellipses that I picked at random.  Neither ellipse is a circle,
neither ellipse is centered at the origin and the major axes of the
ellipses are not parallel to each other.  I got 4 lines, as expected,
and verified graphically that they are tangent to both ellipses.  I
suspect that a symbolic solution, if it exists, would be many pages
long.

yes, I know it is possible, but what I am looking for here is how to
define the boundary f(a)f(b)<0, so that I could use binary search for
the results. I am not looking for some lib from Mathematica, since I
am not going to call it in our software. We try to get the right
algorithm and implement it. Thanks!

The Mathematica function FindRoot found one of the tangents for a
given starting set of values of the four variables and FindRoot uses
Newton-Raphson, so that should work.  The Numerical Recipes books tell
how to implement Newton-Raphson in C or Fortran, depending on which
book you're looking at.

please note the equation I want to solve is f(x,y)=0, not f(x), since
you can't get rid of y or you will get some expressions under the
square root sign, u can't get rid of that square root sign, so
Newton-Raphson can not be the solution.

Actually the Newton-Raphson name is often reserved for the
multi-variable version of Newton's method for finding roots.  One
needs as many "scalar" equations as unknowns to calculate a
"correction" to x,y based on the error terms and the Jacobian (matrix
of first partial derivatives).

regards, mathtalk-ga

What computer language are you working in?

If I were going to code this to handle the possibility of overlap
between the two ellipses, I would begin simply with the line through
the center of the two ellipses and check how the two pairs of
intersections are arranged along that line.

From this "center line" I would create four new lines, each of which
is defined by choosing a point on each ellipse (and those two points
define that line).  In the best case each of the four lines starts a
sequence of lines that converges to a different "common tangent" to
the two ellipses.  Each new line in the four sequences would be
checked for proper arrangement of the pairs of intersections with the
two ellipses.

regards, mathtalk-ga

I myself spend many hours looking for the answer to this question.  I
got myself most of the way through the answer, but ended up finding
http://vxl.sourceforge.net which is "a collection of C++ libraries
designed for computer vision research and implementation."  Look at
http://paine.wiau.man.ac.uk/pub/doc_vxl/core/vgl/html/classvgl__homg__operators__2d.html#vgl__homg__operators__2de28
specifially.  This method will give you the lines (infinite, not line
segments) that are tangent.  If you actually want the tangent points
as well, there is a different method (still using their library) that
I can help you with (or you can just find the intersection points
between the tangent lines and the conics).  If you need any more help
with it, post here and I'll check back.

I plan on putting up a web page to "remind" myself at a later time how
to do this, and when I do, I will post a link to it here if people are
interested.

-digitalseraphim