Copyright 1984 by ABComputing ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» º Common Tangents to Two Ellipses º º º º by º º º º Bill Salkin º ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ Introduction ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ Visualize two ellipses as displayed on a graphics screen. There are many lines tangent to both ellipses. To specify which tangent line is desired, each ellipse is selected with a light pen. The point where the light pen "touches" an ellipse indicates the side to which the tangent line will be drawn. When both ellipses have been light pen selected, a unique tangent line can be determined, and finally drawn on the graphics screen. This article outlines a method for finding common tangents to two ellipses. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ Terminology ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ELLIPSE1 ELLIPSE2 .*ø*. .*ø*. * * * * * * P = (E,F) * * * P1 Ä * ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ *Ä P2 * * ³ * * ³ * *  * *  * ø*.*ø ø*.*ø Q1(X1,Y1) ÄÄÄÄÄÄÄ Q2(X2,Y2) ÄÄÄÄÄÄÄ Q1' Q2' Figure ( it-out ) #1 Description of nomenclature used in Figure 1: ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ ELLIPSE1 ³ ELLIPSE2 ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ ³ center ³ P1(XC1,YC1) ³ P2(XC2,YC2) ³ ³ radius vector from center ³ ³ ³ ³ intersects ellipse at: ³ Q1(X1,Y1) ³ Q2(X2,Y2) ³ ³ tangent vector at QI ³ Q1' ³ Q2' ³ ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´ ³ The vector P = (E,F) joins the centers of the ellipses. ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ All data associated with ELLIPSEI ( I = 1,2 ) has the number "I" appended. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ The Method ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ Consider a line tangent to ELLIPSE1 and ELLIPSE2 at points Q1 and Q2, respectively. This line must be parallel to the tangent vectors at Q1 and Q2. As the vector cross product of parallel vectors is 0, this condition can be formulated mathematically as: ( Q2 - Q1 ) X Q1' = 0 and ( Q2 - Q1 ) X Q2' = 0 (1) Q1 is a point on ELLIPSE1. Q1' is the derivative of the parametric equation of ELLIPSE1, evaluated at point Q1. ( Q2 - Q1) is a vector joining the perimeters of the ellipses. It acts as an approximation to the tangent line. If the above equations are satisfied, ( Q2 - Q1 ) is tangent to both ellipses. Two simultaneous non-linear equations are represented by (1). The method used to solve these equations is the "3-dimensional" Newton method. This method is discussed next. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ 3-d Newton Method ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ This is an iterative method for solving the equations f(x,y) = 0, and g(x,y) = 0 An initial point ( x(0), y(0) ) is selected and successive points (hopefully converging to an answer) are found from the sequences: x(n) = x(n-1) + h(n-1) y(n) = y(n-1) + k(n-1) where h and k satisfy f ( x(n-1), y(n-1)) h(n-1) x + f ( x(n-1), y(n-1)) k(n-1) = - f( x(n-1), y(n-1)) y and g ( x(n-1), y(n-1)) h(n-1) x + g ( x(n-1), y(n-1)) k(n-1) = - g( x(n-1), y(n-1)) y f denotes the partial derivative of f with respect to x. x These equations are derived by replacing the multivariable Taylor series by its linear part. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ Transformation 1 ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ The equations in (1) must be transformed into a form that is suitable for Newton's method. From vector algebra, Q1 and Q2 can be represented as: Q1 = P1 +iX1 + jY1, Q2 = P2 + iX2 + jY2 where "i" and "j" are the orthogonal unit vectors forming the standard basis for the complex plane. P1 and P2 are the centers of the ellipses. Substituting these expressions in (1), and using P = (E,F) = Ei + Fj gives [ ( E + X2 - X1 )i + ( F + Y2 - Y1)j ] X [ IX1' + jY1'] = 0 [ ( E + X2 - X1 )i + ( F + Y2 - Y1)j ] X [ IX2' + jY2'] = 0 Simplifying these equations gives [ ( E + X2 - X1 ) Y1' - ( F + Y2 - Y1) X1' ] = 0 (2) [ ( E + X2 - X1 ) Y2' - ( F + Y2 - Y1) X2' ] = 0 ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ Transformation 2 ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ The parametric equation of an ellipse, with origin (XC,YC), semimajor axis "a", semiminor axis "b", and rotated @ radians ( with respect to the positive x-axis ) is: X = XC + ( a cos@ ) cost - ( b sin@ ) sint (3) Y = YC + ( b cos@ ) sint + ( a sin@ ) cost where 0 <= t <= Two Pi radians ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ The Grand Finale ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ Substitution of the equations (3) into (2) result in two equations in two unknowns. This is the form needed by Newton's method. The equations resulting from this substitution are not given in this article! The reader is encouraged to perform the algebra and determine them. I have applied Newton's method to these equations and can report that the method has never failed in my experience ( undoubtedly owing to the infinite differentiability of the ellipse parametric equations ). ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ Conclusion ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ It is difficult to present mathematical symbols and diagrams on the IBM PC. The tangent-line geometry in this article can be "massaged" to address other geometrical problems such as finding the projection of a point to an ellipse, or the intersection of two splines. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ File Name: ÛÛ fort1.txt ÛÛ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ xt mode) ³ ³ ³ BL=color (0-15, 16-31 for high-intensity chars. ³ ³