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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.