# Thread: Find points where two ellipses cross

1. ## Find points where two ellipses cross

I want to find the coordinates where two ellipses meet. They each have five degrees of freedom (axes lengths, center coordinates and tilt angle) although we could assume that both have the same tilt angle.

I suppose that no managable algebraic solution exists.

How should I proceed in order to solve it numerically, for example with the secant method?

For each point I pick on one ellipse, I need to numerically search for the point on the other ellipse which is closest to it. But I want the solution algorithm to be computationally fairly efficient. Is there no smarter way?

2. I find this problem interesting...

May I ask, are five degrees of freedom enough to characterise a general ellipse in 3D space? It seems to me, at first glance, that two tilt angles would be required: inclination and azimuth.

Edit: Sorry, I was thinking of ellipsoids in 3D. In fact your problem concerns ellipses in 2D.

Do the ellipses overlap, touch at a single point, or are they separate? Or can we not know in general?

3. Thank you for showing interest!

They are 2D ellipses in the same plane.

One cannot beforehand know if they cross in no, one or two points. But lets exclude the possiblity of them crossing in three or four points if that helps. This because we can assume that both ellipses have the same tilt angle. And they have somewhat similar proportions between their major and minor axes. One is always smaller that the other in both height and width.

Still, it is possible that they do not cross, either because one ellipse is completely surrounded by the other, or because they lie side by side.

I know the "parametric" form of the ellipses, and I know how to transform that so that I can express their formulas in the cartesian form too.

So the problem can be phrased as "For what values of x and y are these two formulas equal?":

a*x + b*y + c*x*y + d*x^2 + e*y^2 + f = 0
A*x + B*y + C*x*y + D*x^2 + E*y^2 + F = 0

Naively, I multiply the first equation by D/d and subtract the other equation in order to eliminate x^2. I rename the new "combined" coefficients to simplify notation. I solve for x. They I substitute this solution for x in the other of the equations and politely ask Mathematica to run its "Solve[]" command on it. The solution is several pages long. Unmanagable.

Obviously, some more intelligent procedure is necessary...

4. Originally Posted by Dirlewanger
Thank you for showing interest!

They are 2D ellipses in the same plane.

One cannot beforehand know if they cross in no, one or two points. But lets exclude the possiblity of them crossing in three or four points if that helps. This because we can assume that both ellipses have the same tilt angle. And they have somewhat similar proportions between their major and minor axes. One is always smaller that the other in both height and width.

Still, it is possible that they do not cross, either because one ellipse is completely surrounded by the other, or because they lie side by side.

I know the "parametric" form of the ellipses, and I know how to transform that so that I can express their formulas in the cartesian form too.

So the problem can be phrased as "For what values of x and y are these two formulas equal?":

a*x + b*y + c*x*y + d*x^2 + e*y^2 + f = 0
A*x + B*y + C*x*y + D*x^2 + E*y^2 + F = 0

Naively, I multiply the first equation by D/d and subtract the other equation in order to eliminate x^2. I rename the new "combined" coefficients to simplify notation. I solve for x. They I substitute this solution for x in the other of the equations and politely ask Mathematica to run its "Solve[]" command on it. The solution is several pages long. Unmanagable.

Obviously, some more intelligent procedure is necessary...
1) You cannot plot the ellipses on the same cartesian axes? If you can, do they intrersect?

2) Can you express Ax +By +Cxy +Dx^2 +Ey^2 +F
into its more "elementary" form ((x -G)^2 /(h^2) +(y -J)^2 /(k^2) = 1?

5. Hi ticbol!
Originally Posted by ticbol
1) You cannot plot the ellipses on the same cartesian axes? If you can, do they intrersect?
I need a solution METHOD to apply on many pairs of ellipses. And the solution needs to be done algorithmically without human interference (and with some computational efficiency).

2) Can you express Ax +By +Cxy +Dx^2 +Ey^2 +F
into its more "elementary" form ((x -G)^2 /(h^2) +(y -J)^2 /(k^2) = 1?
The form you suggest looks like the formula for an untilted elipse, i.e. an ellipse whose axes are parallell to the axes of the coordinate system. I don't know how tilted ellipses could be expressed in that form.

But maybe since tilt can be assumed to be the same for both ellipses, there is a way to "turn" the coordinate system by that angle and then proceed in this form with only four degrees of freedom?

Please see Ellipse - Wikipedia, the free encyclopedia to see what I mean with "parametric form". Except for the tilt, all other four variables in the parametric form correspond directly to the variables in the form you suggest.

6. Originally Posted by Dirlewanger
Hi ticbol!

I need a solution METHOD to apply on many pairs of ellipses. And the solution needs to be done algorithmically without human interference (and with some computational efficiency).

The form you suggest looks like the formula for an untilted elipse, i.e. an ellipse whose axes are parallell to the axes of the coordinate system. I don't know how tilted ellipses could be expressed in that form.

But maybe since tilt can be assumed to be the same for both ellipses, there is a way to "turn" the coordinate system by that angle and then proceed in this form with only four degrees of freedom?

Please see Ellipse - Wikipedia, the free encyclopedia to see what I mean with "parametric form". Except for the tilt, all other four variables in the parametric form correspond directly to the variables in the form you suggest.
Wow, my friend, I think we two are not on the same wavelength.

If no human interference is needed, sorry, I am human.

I think Mathematica doesn't show METHODs of solving problems algorithmically. Or does it?

7. Originally Posted by ticbol
I think Mathematica doesn't show METHODs of solving problems algorithmically. Or does it?
I was using Mathematica to look for a neat formula which I could use in an algorithm. Developing the method to solve the problem, of course needs to be done manually (since Terminator Doomsday hasn't come yet...) But then I want to have an automatic and speedy process into which I stuff specifications of the ellipses, and get as a result their crossing points, if any.

However, tilted ellipses are complicated objects. They seem to be like any irregular curve, really. There isn't much hope of finding any neat formula for anything concerning them.

But how about transforming the coordinate system so that the ellipses no longer are tilted relative to it? Could I proceed as if they are untilted, and then transform the coordinates for the crossing points to account for the tilt?

8. Originally Posted by Dirlewanger
I was using Mathematica to look for a neat formula which I could use in an algorithm. Developing the method to solve the problem, of course needs to be done manually (since Terminator Doomsday hasn't come yet...) But then I want to have an automatic and speedy process into which I stuff specifications of the ellipses, and get as a result their crossing points, if any.

However, tilted ellipses are complicated objects. They seem to be like any irregular curve, really. There isn't much hope of finding any neat formula for anything concerning them.

But how about transforming the coordinate system so that the ellipses no longer are tilted relative to it? Could I proceed as if they are untilted, and then transform the coordinates for the crossing points to account for the tilt?
Even if the ellipses have the same tilt angle, you cannot get rid of the tilt of at least one of them. You can translate the system such that one of the ellipses has its center at the origin and proceed to rotate the axes to remove the tilt of that one, but the other ellipse will be away from the origin and will merely rotate about the origin rather than rotate about its center. So in general one of your ellipses will still have its major axis at a slant.

-Dan

9. I think there is a closed-form solution - though it could be messy.

Think of this very simplified scenario: two circles, same radius $\displaystyle r$, at the origin and $\displaystyle (a,0)$.

The points of intersection are

$\displaystyle (x,y) = (a/2, \pm \sqrt{r^2 - a^2/4})$

and the square root for $\displaystyle y$ fails if $\displaystyle a>2r$.

I can see immediately some ways to extend this; the biggest difficulty comes when, as stated above, one ellipse is tilted with respect to the other.

If a closed-form solution is not possible, you can always use iterative methods. They will compromise the efficiency of your computation (which I assume is some kind of collision-detection?) -- but perhaps not by as much as you think. (It depends on how much accuracy you need, and on how many complicated 'fiddles' you want to put into the algorithm.)

10. topsquark, yes I see now how a coordinate translation cannot get rid of the tilt problem.

Pterid, Mathematica did find an algebraic solution, but it was page up and page down. Maybe a smarter formulation of the problem could shorten it, but basically it seems as if a tilted ellipse easily causes great comlications for algebra...

So, the subject from now on maybe should be what a smart approach to a numerical solution would look like?

My naive proposal would be to pick a point A on elllipse one, then search points along ellipse two until I find the point on it closest to point A. Then I move point A along ellipse one and again search for the point on ellipse two which is closest to that. Until the points on the two ellipses are close enough to each other.

Can't I use some better approach?

11. Perhaps you could share the results that Mathematica gave? A closed-form solution, even if it looks complicated, can be more efficient in terms of clock cycles than many iterations of a numerical solver.

12. Originally Posted by Pterid
Perhaps you could share the results that Mathematica gave? A closed-form solution, even if it looks complicated, can be more efficient in terms of clock cycles than many iterations of a numerical solver.
It is a huge polynom. But sure, I'll post it. Maybe it is possible to make some radical improvements to the question I posed to Mathematica.

It's on another computer, so I'll post it later.

13. I seems to have lost part of that solution and have to redo some of it.

Anyway, let's put this on ice for a while. I'got bigger headaches now...

Thanks for the inputs, everyone!