How to detect if an ellipse intersects(collides with) a circle?

Short answer: Solving exactly for whether the two objects intersect is complicated enough to be infeasible for the purpose of collision detection. Discretize your ellipse as an n-sided polygon for some n (depending on how accurate you need to be) and do collision detection with that polygon Long answer: If you insist on determining if the smooth ellipse and circle intersect, there are two main approaches. Both involve solving first for the closest point to the circle's center on the ellipse, and then comparing that distance to the circle's radius Approach 1 : Use a parametrization of the ellipse.

Transform your coordinates so that the ellipse is at the origin, with its axes aligned to the x-y axes. That is: Center of ellipse: (0,0) Center of circle: c = (cx, cy) Radius of circle: r Radius of x-aligned axis of ellipse: a Radius of y-aligned axis of ellipse: be The equation of the ellipse is then given by a cos(t), be sin(t) To find the closest point, we want to minimize the square distance (a cos t, be sin t) - c ||^2 As Jean points out, this is "just calculus": take a derivative, and set it equal to 0. Unless I'm missing something, though, solving the resulting (quite nasty) equation for t is not possible analytically, and must be approximated using e.g. Newton's Method.

Plug in the t you find into the parametric equation to get the closest point Pro: Numerical solve is only in one variable t Con: You must be able to write down a parametrization of the ellipse, or transform your coordinates so that you can. This shouldn't be too hard for any reasonable representation you have of the ellipse. However, I'm going to show you a second method, which is much more general and might be useful if you have to generalize your problem to, say, 3D Approach 2 : Use multidimensional calculus.

No change of coordinates is necessary Center of circle: c = (cx, cy) Radius of cirlce: r Ellipse is given by g(x, y) = 0 for a function g. For instance, per Curd's answer you might use g(x,y) = distance of (x,y) from focus 1 + distance of (x,y) from focus 2 - e Finding the point on the ellipse closest to the center of the circle can then be phrased as a constrained minimization problem : Minimize ||(x,y) - c||^2 subject to g(x,y) = 0 (Minimizing the square distance is equivalent to minimizing the distance, and much more pleasant to deal with since it's a quadratic polynomial in x,y.) To solve the constrained minimization problem, we introduce Lagrange multiplier lambda, and solve the system of equations 2 * (x,y) -c + lambda * Jg(x,y) = 0 g(x,y) = 0 Here Jg is the gradient of g. This is a system of three (nonlinear) equations in three unknowns: x, y, and lambda.

We can solve this system using Newton's Method, and the (x,y) we get is the closest point to the circle's center Pro: No parametrization needs to be found Pro: Method is very general, and works well whenever writing g is easier than finding a parametric equation (such as in 3D) Con: Requires a multivariable Newton solve, which is very hairy if you don't have access to a numerical method package Caveat: both of these approaches technically solve for the point which extremizes the distance to the circle's center. Thus the point found might be the furthest point from the circle, and not the closest. For both methods, seeding your solve with a good initial guess (the center of the circle works well for Method 2; you're on your own for Method 1) will reduce this danger Potential Third Approach?

: It may be possible to directly solve for the roots of the system of two quadratic equations in two variables representing the circle and ellipse. If a real root exists, the objects intersect. The most direct way of solving this system, again using a numerical algorithm like Newton's Method, won't help because lack of convergence does not necessary imply nonexistence of a real root.

For two quadratic equations in two variables, however, there may exist a specialized method that's guaranteed to find real roots, if they exist. I myself can't think of a way of doing this, but you may want to research it yourself (or see if someone on stackoverflow can elaborate. ).

Short answer: Solving exactly for whether the two objects intersect is complicated enough to be infeasible for the purpose of collision detection. Discretize your ellipse as an n-sided polygon for some n (depending on how accurate you need to be) and do collision detection with that polygon. Long answer: If you insist on determining if the smooth ellipse and circle intersect, there are two main approaches.

Both involve solving first for the closest point to the circle's center on the ellipse, and then comparing that distance to the circle's radius. Approach 1: Use a parametrization of the ellipse. Transform your coordinates so that the ellipse is at the origin, with its axes aligned to the x-y axes.

That is: Center of ellipse: (0,0) Center of circle: c = (cx, cy) Radius of circle: r Radius of x-aligned axis of ellipse: a Radius of y-aligned axis of ellipse: b. The equation of the ellipse is then given by a cos(t), be sin(t). To find the closest point, we want to minimize the square distance || (a cos t, be sin t) - c ||^2.As Jean points out, this is "just calculus": take a derivative, and set it equal to 0.

Unless I'm missing something, though, solving the resulting (quite nasty) equation for t is not possible analytically, and must be approximated using e.g. Newton's Method. Plug in the t you find into the parametric equation to get the closest point. Pro: Numerical solve is only in one variable, t.

Con: You must be able to write down a parametrization of the ellipse, or transform your coordinates so that you can. This shouldn't be too hard for any reasonable representation you have of the ellipse. However, I'm going to show you a second method, which is much more general and might be useful if you have to generalize your problem to, say, 3D.

Approach 2: Use multidimensional calculus.No change of coordinates is necessary. Center of circle: c = (cx, cy) Radius of cirlce: r Ellipse is given by g(x, y) = 0 for a function g. For instance, per Curd's answer you might use g(x,y) = distance of (x,y) from focus 1 + distance of (x,y) from focus 2 - e.

Finding the point on the ellipse closest to the center of the circle can then be phrased as a constrained minimization problem: Minimize ||(x,y) - c||^2 subject to g(x,y) = 0 (Minimizing the square distance is equivalent to minimizing the distance, and much more pleasant to deal with since it's a quadratic polynomial in x,y. ) To solve the constrained minimization problem, we introduce Lagrange multiplier lambda, and solve the system of equations 2 * (x,y) -c + lambda * Jg(x,y) = 0 g(x,y) = 0 Here Jg is the gradient of g. This is a system of three (nonlinear) equations in three unknowns: x, y, and lambda.

We can solve this system using Newton's Method, and the (x,y) we get is the closest point to the circle's center. Pro: No parametrization needs to be found Pro: Method is very general, and works well whenever writing g is easier than finding a parametric equation (such as in 3D) Con: Requires a multivariable Newton solve, which is very hairy if you don't have access to a numerical method package. Caveat: both of these approaches technically solve for the point which extremizes the distance to the circle's center.

Thus the point found might be the furthest point from the circle, and not the closest. For both methods, seeding your solve with a good initial guess (the center of the circle works well for Method 2; you're on your own for Method 1) will reduce this danger. Potential Third Approach?

: It may be possible to directly solve for the roots of the system of two quadratic equations in two variables representing the circle and ellipse. If a real root exists, the objects intersect. The most direct way of solving this system, again using a numerical algorithm like Newton's Method, won't help because lack of convergence does not necessary imply nonexistence of a real root.

For two quadratic equations in two variables, however, there may exist a specialized method that's guaranteed to find real roots, if they exist. I myself can't think of a way of doing this, but you may want to research it yourself (or see if someone on stackoverflow can elaborate. ).

Note also that you need yet another set of checks to see if the circle lies entirely within the ellipse – Martin DeMello Jun 3 '10 at 8:16 thank you, I thought there is a much simple solution. Obviously, it would be not only hard to implement it for collision detection but also very slow. – php html Jun 3 '10 at 23:03.

An ellipse is defined a the set of points whose sum of the distance to point A and the distance to point B is constant e. (A and B are called the foci of the ellipse). All Points P, whose sum AP + BP is less than e, lie within the ellipse.

A circle is defined as the set of points whose distance to point C is r. A simple test for intersection of circle and ellipse is following: Find P as the intersection of the circle and the line AC and Q as the intersection of the circle and the line BC. Circle and ellipse intersect (or the circle lies completely within the ellipse) if AP + BP Maybe it is good enough for your practical purposes, although mathematically it is not perfect.

Dude. Well said. Did you quote a textbook?

– Warren P May 31 '10 at 19:00 No. The definitions of ellipse and circle are common. And the rest you can derive easily.

– Curd May 31 '10 at 19:17 3 i'm fairly sure a circle can intersect an ellipse, and still have the point of intersection of the circle's centre and the ellipse's focus lie outside the ellipse. Consider the top of a circle intersecting one end of a long, thin ellipse, and pick the distant focus. Edit: here's a diagram: i.imgur.Com/FU2MN.

Png – Martin DeMello Jun 1 '10 at 19:01 @Martin DeMello: you are right. I think a second check will fix it.(without having it proved).Thanks. I will edit the answer accordingly.

– Curd Jun 1 '10 at 23:34 A thought: I have no proof, but in the problem case I think that the intersection will have to be between the acute arc PQ. If that's that case you could make the test more accurate by testing a set of points on the circle inside that arc and see if any of those are within the ellipse. – aspo Jun 4 '10 at 18:16.

If a circle and an ellipse collide, then either their boundaries intersect 1, 2, 3, or 4 times(or infinitely many in the case of a circular ellipse that coincides with the circle), or the circle is within the ellipse or vice versa. I'm assuming the circle has an equation of (x - a)^2 + (y - b)^2 = 0 There you have it, if I didn't make any algebraic mistakes. I don't know how much you can simplify the resulting expression, so this solution might be quite computationally expensive if you're going to check for many circles/ellipses.

I think a similar approach might work though. – user168715 Jun 3 '10 at 0:36 whoops, forgot all about skewed ellipses, never really came across them in my various math courses. I'm not sure if it would be easy to modify this approach to deal with them.

– Bwmat Jun 3 '10 at 0:41 since a circle remains unchanged however you translate and rotate your coordinate system, you could redefine your axes to lie along the axes of the ellipse – Martin DeMello Jun 3 '10 at 8:19 Can you clarify the step near the beginning where you have f(x,y) = r^2 (1) and g(x,y) = 1 (2) and then say that these have a joint solution when f(x, y) + g(x, y) = r^2 + 1 (3)? I'm not sure if I'm being stupid, but I don't see why that has to be true. For example, a solution X,Y to the combined equation (3) might be such that f(X,Y) = 2 and g(X,Y) = r^2 - 1.

That would not be a solution to either (1) or (2), individually. – andrew cooke Jun 24 '10 at 1:56.

Forget about a mathematical solution. As you can easily see by by paining, you can have up to four solutions, and thus a fourth grade polynomial. Instead just do a binary search along the edge of one of the figures.It is easy to determine if a point lies within an ellipse and even more so in a circle (just see if distance is shorter than radius).

If you really want to go for the maths, Wolfram MathWorld has a nice article here: mathworld.wolfram.com/Circle-EllipseInte... but be warned, you'll still have to write a polynomial equation solver, probably using something like binary search.

Supposing: the ellipse is centred at the origin and with the semi-major axis (of length a) oriented along the x axis, and with a semi-minor axis of length b; E2 is the eccentricity squared, ie (a*a-b*b)/(a*a); the circle is centred at X,Y and of radius r. The easy cases are: the circle centre is inside the ellipse (ie hypot(X/a, Y/b) a+r) so there isn't an intersection. One approach for the other cases is to compute the geodetic coordinates (latitude, height) of the circle centre.

The circle intersects the ellipse if and only if the height is less than the radius. The geodetic latitude of a point on an ellipse is the angle the normal to the ellipse at the point makes with the x axis, and the height of a point outside the ellipse is the distance of the point from the point on the ellipse closest to it. Note the geodetic latitude is not same as the polar angle from the ellipse centre to the point unless the ellipse is in fact circular.In formulae the conversion from geodetic coordinates lat,ht to cartesian coordinates X,Y is X = (nu+ht)*cos(lat), Y = (nu * (1-E2) + ht)*sin(lat) where nu = a/sqrt( 1 - E2*sin(lat)*sin(lat)).

The point on the ellipse closest to X,Y is the point with the same latitude, but zero height, ie x = nu*cos(lat), y = nu * (1-E2) * sin(lat). Note that nu is a function of latitude. Unfortunately the process of finding lat,ht from X,Y is an iterative one.

One approach is to first find the latitude, and then the height. A little algebra shows that the latitude satisfies lat = atan2( Y+ E2*nu*sin(lat), X) which can be used to compute successive approximations to the latitude, starting at lat = atan2( Y, X*(1.0-E2)), or (more efficiently) can be solved using newton's method. The larger E2 is, ie the flatter the ellipse is, the more iterations will be required.

For example if the ellipse is nearly circular (say E2Finally, given the latitude, the height can be computed by computing (x,y): x = nu*cos(lat), y = nu*(1-E2)*sin(lat) and then h is the distance from x,y to the circle centre, h = hypot( X-x, Y-y).

This isn't that hard. User168715's answer is generally right, but doing calculus isn't necessary. Just trigonometry.

Find the angle between the center of the two objects. Using this you can find the closest point to the circle's center on the ellipse using the polar-form: (Taken from Wikipedia article on Ellipses) Now compare the distance between the two object centers, subtracting the ellipse radius and circle radius. Maybe I'm missing something; maybe ArcTan/Cos/Sin are slow -- but I don't think so, and there should be fast-approximations if needed.

It is possible to efficiently obtain a close approximation to whether or not an ellipse and a circle collide using only simple operations. Given the major axis of an ellipse, draw a line on that axis centered on the ellipses origin that has a length equal to the length of the major axis, times the ratio (A+B)/(A-B). Then, get the closest point on the line to the circle's center divided by the ratio, followed by the closest point on the circle to that point on the line.

Check to see if that point falls within the ellipse. This always works with a maximum error margin of about 5% on worst-case scenarios. Example implementation in C++: static inline bool BSS_FASTCALL CircleEllipseIntersect(T X, T Y, T A, T B, T x, T y, T r) { T tx=(x-X); T ty=(y-Y); T tx2=tx*tx; T ty2=ty*ty; T A2 = A*A; T B2 = B*B; T d = tx2+ty2; T r2=r*r; //checks to see if the ellipse center is inside the circle or vice versa if((dA) { U1=tx;tx=ty;ty=U1; U1=A;A=B;B=U1; } T ratio = (A-B + (2*B/(1+(ty/A)*B)))/(A+B); U1=A/ratio; U2=-U1; //the y coordinates of the line are always 0 cPosition::NearestPointToLine(tx,ty,U1,0,U2,0,Vx,Vy); Vx*=ratio; //if the nearest point on the line is inside the circle, the circle intersects the line, so it must intersect the ellipse if(bss_util::distsqr(Vx,Vy,tx,ty)Note that an ellipse-ellipse intersection can be transformed into a circle-ellipse intersection by scaling one axis.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.