Results 1 to 13 of 13

Math Help - Find points where two ellipses cross

  1. #1
    Newbie
    Joined
    Jan 2008
    Posts
    24

    Arrow 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2008
    Posts
    24

    Smile

    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...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Apr 2005
    Posts
    1,631
    Quote Originally Posted by Dirlewanger View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2008
    Posts
    24
    Hi ticbol!
    Quote Originally Posted by ticbol View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Apr 2005
    Posts
    1,631
    Quote Originally Posted by Dirlewanger View Post
    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 thought I read you asked Mathemathica to help you, that's why I asked if you can plot the ellipses using MathCad or any other non-human method.

    I think Mathematica doesn't show METHODs of solving problems algorithmically. Or does it?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2008
    Posts
    24

    Smile

    Quote Originally Posted by ticbol View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,903
    Thanks
    329
    Awards
    1
    Quote Originally Posted by Dirlewanger View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    I think there is a closed-form solution - though it could be messy.

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

    The points of intersection are

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

    and the square root for y fails if 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.)
    Attached Thumbnails Attached Thumbnails Find points where two ellipses cross-circles.bmp  
    Last edited by Pterid; July 2nd 2008 at 11:31 AM. Reason: cleanup
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jan 2008
    Posts
    24
    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?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jan 2008
    Posts
    24
    Quote Originally Posted by Pterid View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Jan 2008
    Posts
    24
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find the period -- from cross section??
    Posted in the Trigonometry Forum
    Replies: 8
    Last Post: February 19th 2011, 05:37 PM
  2. Find the points where two circles cross
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: October 20th 2010, 05:28 AM
  3. Replies: 5
    Last Post: April 5th 2010, 09:15 AM
  4. Replies: 2
    Last Post: September 4th 2009, 10:19 PM
  5. Replies: 4
    Last Post: May 2nd 2009, 10:15 AM

Search Tags


/mathhelpforum @mathhelpforum