Finding Intersections of Two Ellipses

Date: 06/17/2005 at 11:12:49
From: 
Subject: Two-Ellipse Intersection Condition

As part of a computer program, I'm working on the problem of detecting
the collision of two ellipses given the length of their axes and
coordinates of their centers on the X-Y plane.  The ellipses are not
rotated, although they can be oriented so that their major axis is
either vertical or horizontal.

Essentially I am looking at trying to detect the
collision/intersection between the following two ellipses, given
arbitrary constants a,b,c,d,x1,x2,y1,y2:

((x-x1)^2)/(a^2) + ((y-y1)^2)/(b^2) = 1
((x-x2)^2)/(c^2) + ((y-y2)^2)/(d^2) = 1

Other than utilizing various computationally-expensive approximations
(such as brute-force checking of points), I cannot find a good way to
detect a collision, and as a result, I was wondering if there was an
algebraic condition in terms of a,b,c,d,x1,x2,y1,y2 which could
determine collision.

By using radius checks with the major and minor axes of the ellipses,
I can handle the case where the ellipses are nested one within the
other and case where the ellipses are obviously too far apart.  This
reduces the problem of collision to checking if there is any solution
(x,y), indicating intersection.  Shifting the coordinate system to
place an ellipse at the center, my parents and I were able to somewhat
reduce the problem, but the algebra quickly became intractable as
irreduceable terms appeared under radicals that wouldn't go away.

Is there an algebraic condition for collision or perhaps an entirely
different, better way to determine collision?

Date: 06/17/2005 at 16:38:07
From: Doctor George
Subject: Re: Two-Ellipse Intersection Condition

Hi David,

Thanks for writing to Doctor Math.

If you eliminate y from your pair of ellipse equations you will get a
4th order equation in x.  It is messy to solve, but it can be done.

Here is how I would attack this problem for programming purposes.

(I'm going to change your notation a bit.  I would call the constants
x1,y1,a1,b1 and x2,y2,a2,b2.  For ellipses most books will use c to
represent the location of the foci.)

First, write one ellipse in a parameterized form.

         x = x1 + a1 cos(theta)
         y = y1 + b1 sin(theta)

As theta goes from 0 to 2 pi the point P = (x,y) traces out the
ellipse.  Do you see why?

Second, let the foci of the second ellipse be F21 and F22, and examine
the function

         f(theta) = |P - F21| + |P - F22| - 2 a2

The right side of the equation is closely tied to the definition of
the second ellipse in terms of its foci.  Can you see that when
f(theta) = 0, the point P falls on the second ellipse, thus giving you
an intersection point?  As you change theta, the point P walks around
the first ellipse and will fall on the second ellipse for certain
values of theta (assuming that the ellipses intersect).

Now you have a one variable problem!  You just need to find the 
correct value(s) of theta.

If you have learned a little Calculus you can solve this equation in
your program using Newton's Method.  If you have not learned any
Calculus the simplest approach is called the Bisection Method.  You 
can find information about these methods on the Internet.

I hope this is enough to get you started.  Write again if you need 
more help.

- Doctor George, The Math Forum
  http://mathforum.org/dr.math/