[RESOLVED] Intersections of ellipses

[opus]

How could I calculated the intersections of two ellipses?

I have the positions of the two focus points of each ellipse,
the distance between those focus points (2e) and the diameter of the ellipse on the semimajor axis (2a).

I can calculate any point on on of the ellipses using either a angle from the center or a valid value for either x or y.
My problem is that I can't figure out to calculate an intersection.

[jemidiah]

This is remarkably similar to the other active thread. I... can't see any nifty geometric approach. I can only imagine that, with the ellipses being in different locations and with different orientations, it would be horrible. Algebraically, it would also be awful but a computer could do it for you. You would have to solve the generalized ellipse equation http://mathworld.wolfram.com/images/equations/Ellipse/NumberedEquation10.gif (valid for any rotation or starting position) (source (http://mathworld.wolfram.com/Ellipse.html)) for two sets of constants, in a system of two equations.

Several programs would solve this system analytically for you (the result would be much worse than the one I gave in the other thread). Many numerical solvers could also be employed. Fixed point iteration (http://en.wikipedia.org/wiki/Fixed_point_iteration) feels like it would work as well since the functions are polynomial, and that method is very easy to implement (though you'd have to somehow deal with the fact that this is a system instead of a single function; I have ideas on that if you're interested).

Unfortunately to use the methods I've described you would need to first solve the system of equations for a, b, c, d, f, g for each ellipse. While not terrible, it's an extra step of complexity.


You could use your own numerical method as well, using a form of the bisection method (http://en.wikipedia.org/wiki/Bisection_method). You would start by picking an ellipse, and looking at ranges of angles on that ellipse. At each step you would use some property to narrow the search range by half (I have ideas on these as well if you're interested). You would converge to the correct angle using binary search, adding an extra digit of precision (well, a constant number of digits of precision) at each step, i.e. rather quickly.

Another home-brew numerical method for this problem would be to calculate the position of, say, 10 points spaced evenly at angles on each ellipse. You would then check to see which pairs of points are closest to each other. From those pairs you would narrow your search angles, picking another 10 points in the new ranges (there would be two ranges, corresponding to the two intersections), and repeating the process. There are quite a lot of details to be worked out with this method, but it's conceptually pretty simple, and would be exponentially fast (since you're dividing the search region by 10 each time, picking an angle range spanning only 2 of your 10 points).


If the two ellipses were oriented in the same directions, this may well be tractable geometrically. I don't think it is sane to solve it geometrically in the general case, though, which is unfortunate because it would likely yield a nice set of several back substitutions which would be comprehensible to a human, as opposed to the apparent algebraic garbage the above system would produce.


Edit: A brief Google search yielded this (http://www.geometrictools.com/Documentation/IntersectionOfEllipses.pdf), which would seem to indicate this is a problem as hard as I've been thinking. It appears to use the system of equations I described to solve the problem, where the system is solved using some results from Algebraic Geometry.

[opus]

This is remarkably similar to the other active thread. I... can't see any nifty geometric approach. I can only imagine that, with the ellipses being in different locations and with different orientations, it would be horrible.
And in my case it will be horrible, since the ellipses only share one common focus.
I've looked thru all those links already, one of my problems is that I can't "convert " the values of the ellipses that I have (position of focus points and length of the semimajoraxis) into the generalized ellipse equation http://mathworld.wolfram.com/images/equations/Ellipse/NumberedEquation10.gif

[jemidiah]

Since you can calculate 6 different points on each ellipse, form a system of 6 linear equations in 6 variables to solve for the constants a...f for each ellipse. From there can you apply the methods listed?

[opus]

Several Linear Equations - I have to dig real deep (last schoolday was in the late 70th!)

That will take some time.
Thanks for the help.......................searching...................

[krtxmrtz]

A possible simple approach is using an iterative method based on random numbers. In a few words, you sample two points, one in the first ellipse and the other on the second and calculate their distance. Do this until the distance becomes sufficiently small.

I haven't tried it but it could be very efficient. I have solved various similar max/min problems using random numbers when everything else either fails or is too complicated.

Let me know if you need some help with the details.

[krtxmrtz]

Actually, I think its best to select a value for the number of random values to use. Here's a demo project for you to play around with. Try using 100000, 1000000 or more random numbers and see the results and the time it takes.

Probably you can improve the efficiency by limiting the sampling to a smaller interval around the current intersection after the distance between the 2 sampled points becomes sufficiently small.

Also the algorithm must be enhanced somehow in order to find the other intersections.

[jemidiah]

The random point sample approach is very similar to the uniform sample points one I had mentioned. It would converge... pretty slowly with increasing the number of sample points, though iterating through smaller and smaller intervals would make it converge exponentially fast in the average case (and not converge at all in the incredibly unlucky worst case). It's also quite nice and simple conceptually, not needing the gobs of analytic solving techniques employed in that paper I linked, nor the initial linear algebra.


As for solving for a...f (if that's the approach you're interested in ultimately), you'd use this:

Pick six points on your ellipse to form paris (x1, y1), ..., (x6, y6). You know that for some constants a...f, your ellipse has the equation ax^2+2bxy+cy^2+2dx+2fy+g=0. That is, you have six equations,

ax1^2+2b x1 y1 + cy1^2 + 2d x1 + 2f y1 = -g
...
ax6^2+2b x6 y6 + cy6^2 + 2d x6 + 2f y6 = -g

Form a matrix and vector (bold variables are vectors) of these as follows:


A =
[x1^2 2x1 y1 y1^2 2x1 2f]
[x2^2 2x2 y2 y2^2 2x2 2f]
[x3^2 2x3 y3 y3^2 2x3 2f]
[x4^2 2x4 y4 y4^2 2x4 2f]
[x5^2 2x5 y5 y5^2 2x5 2f]
[x6^2 2x6 y6 y6^2 2x6 2f]

b =
[-g]
[-g]
[-g]
[-g]
[-g]
[-g]

c =
[a]
[b]
[c]
[d]
[e]
[f]


Now we know Ac = b using matrix multiplication. The inverse of A can be found using various methods (among them Gauss-Jordan Elimination). After finding that, we have

c = A-1b.

Applying matrix multiplication on the vector b by A's inverse will give you the 6 constants you seek.

[opus]

Thanks for that big help in math.
Now I'm back into the problem.

[jemidiah]

One note, if you do use the paper I linked (whose method is elegant in a brute-force kind of way) you'll have to solve a quartic equation. While I'd recommend a numerical solver handle it, the quartic equation can be solved analytically. Wikipedia's page on Quartic functions (http://en.wikipedia.org/wiki/Quartic_equation#The_general_case.2C_along_Ferrari.27s_lines) goes into some remarkable depth on solving that monster. I really wouldn't recommend it, but if you're interested in a purely analytical solution to your problem, you'd be able to get one that way.

It feels like you could actually use the fact that there are 4 possible solutions to this problem, all of which must satisfy two quadratics, to prove that the roots of quartics are algebraic. You'd have to establish a correspondence between all quartics and all pairs of ellipses. From a countability argument, after scaling, and translating an ellipse in both directions to mash it down to the unit circle, and then rotating the problem so the second ellipse is oriented in some particular direction, you'd have... 4 degrees of freedom (center points of the second ellipse, major and minor axis size). That's exactly as many as you need (to solve the general quartic x^4+ax^3+bx^2+cx+d=0; the x^4 constant has been divided off since it's unnecessary); it could definitely be a fruitful line of reasoning to explore. Now that would be interesting to see done. You may even be able to show the existence of a cubic formula the same way.

[opus]

You may even be able to show .........

If that "You" was meant to be Me, I won't be able to do anything like that. I'm already way over my math-abilities.

[krtxmrtz]

If that "You" was meant to be Me, I won't be able to do anything like that. I'm already way over my math-abilities.
Don't worry, you can be interpreted as du and ihr... :)

[jemidiah]

Heh, sorry I got carried away with the idea. Yeah I meant a ihr :). Maybe I'll do it myself as a project or something. I am in an algebraic geometry course (the domain of these ideas), and the instructor may well give me extra credit for it.

Edit: I also punched in the system of two equations above to Mathematica to see how it would handle it brute-force. The result was hundreds and hundreds of pages of algebra. Definitely not the way you want to go.