Finding the edge of an ellipse - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Finding the edge of an ellipse

I hope this is not too basic a question but my experience in this area is very limited and my maths are not that good either, hope there is someone who can help ;-)

I am looking for a way to find an XY point at the intersection of the edge of an ellipse and a line drawn from any XY point outside of the ellipse to the center point of the ellipse. I got this working for circles, that was relativly easy but ellipse seems to be a whole different problem. Can anyone help me out?

Comments

  • IDKIDK Posts: 1,784Member
    [b][red]This message was edited by IDK at 2006-8-5 8:44:3[/red][/b][hr]
    : I hope this is not too basic a question but my experience in this area is very limited and my maths are not that good either, hope there is someone who can help ;-)
    :
    : I am looking for a way to find an XY point at the intersection of the edge of an ellipse and a line drawn from any XY point outside of the ellipse to the center point of the ellipse. I got this working for circles, that was relativly easy but ellipse seems to be a whole different problem. Can anyone help me out?
    :
    Do like this:
    1. determine the angle of the line.
    2. 'draw' the point where it intersects the ellipse.

    1. This is rather simple trigonometry, but I haven't been teached trigonometry so I don't know how it's done. This is how I would do it with my rather weak knowledge of trigonometry:
    [code]
    z---y
    | /
    _|_/
    / |/
    | x |
    ___/
    [/code]
    Point z is gotten from x value of y and y value of x ;-)
    Then sin(a) = z.y-y.y / sqrt((x.x-y.x)^2+(x.y-y.y)^2)
    Since z.y = x.y it can be replaced, and z isn't needed.

    2. If you use y=cos(a) and x=sin(a)*2 to draw the ellipse, then replace a with the value obtained at 1.

    Happy coding wishes
    the one and only
    [b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]



  • gerrysweeneygerrysweeney Posts: 6Member
    : 1. This is rather simple trigonometry, but I haven't been teached trigonometry so I don't know how it's done. This is how I would do it with my rather weak knowledge of trigonometry:
    : [code]
    : z---y
    : | /
    : _|_/
    : / |/
    : | x |
    : ___/
    : [/code]
    : Point z is gotten from x value of y and y value of x ;-)
    : Then sin(a) = z.y-y.y / sqrt((x.x-y.x)^2+(x.y-y.y)^2)
    : Since z.y = x.y it can be replaced, and z isn't needed.
    :
    : 2. If you use y=cos(a) and x=sin(a)*2 to draw the ellipse, then replace a with the value obtained at 1.
    :
    Hi Niklas,

    Thank you for your reply. I am not sure I understand this entirely but I am starting to get the picture I think. I am a bit confused about how "y=cos(a) and x=sin(a)*2" work in relation to what I am trying to achieve. I am assuming that "a" is the angle in radians, and as I am looking for a point on the edge of an ellipse so surely the formula to find the point needs to account for the position of the center point of the elliipse and the X/Y radius?

    Gerry







  • IDKIDK Posts: 1,784Member
    [b][red]This message was edited by IDK at 2006-8-6 11:5:47[/red][/b][hr]
    : : 1. This is rather simple trigonometry, but I haven't been teached trigonometry so I don't know how it's done. This is how I would do it with my rather weak knowledge of trigonometry:
    : : [code]
    : : z---y
    : : | /
    : : _|_/
    : : / |/
    : : | x |
    : : ___/
    : : [/code]
    : : Point z is gotten from x value of y and y value of x ;-)
    : : Then sin(a) = z.y-y.y / sqrt((x.x-y.x)^2+(x.y-y.y)^2)
    : : Since z.y = x.y it can be replaced, and z isn't needed.
    : :
    : : 2. If you use y=cos(a) and x=sin(a)*2 to draw the ellipse, then replace a with the value obtained at 1.
    : :
    : Hi Niklas,
    :
    : Thank you for your reply. I am not sure I understand this entirely but I am starting to get the picture I think. I am a bit confused about how "y=cos(a) and x=sin(a)*2" work in relation to what I am trying to achieve. I am assuming that "a" is the angle in radians, and as I am looking for a point on the edge of an ellipse so surely the formula to find the point needs to account for the position of the center point of the elliipse and the X/Y radius?
    :
    : Gerry
    :
    :
    Yes, you'r right.
    It should look like this:
    x=centerX+cos(a)*radius
    y=centerY+sin(a)*radius*//(can't remember the name in swedish, and I don't know the name in english, but some kind of ratio)


    Another thing, how does the formula with a circle look like?
  • gerrysweeneygerrysweeney Posts: 6Member
    : [b][red]This message was edited by IDK at 2006-8-6 11:5:47[/red][/b][hr]
    : : : 1. This is rather simple trigonometry, but I haven't been teached trigonometry so I don't know how it's done. This is how I would do it with my rather weak knowledge of trigonometry:
    : : : [code]
    : : : z---y
    : : : | /
    : : : _|_/
    : : : / |/
    : : : | x |
    : : : ___/
    : : : [/code]
    : : : Point z is gotten from x value of y and y value of x ;-)
    : : : Then sin(a) = z.y-y.y / sqrt((x.x-y.x)^2+(x.y-y.y)^2)
    : : : Since z.y = x.y it can be replaced, and z isn't needed.
    : : :
    : : : 2. If you use y=cos(a) and x=sin(a)*2 to draw the ellipse, then replace a with the value obtained at 1.
    : : :
    : : Hi Niklas,
    : :
    : : Thank you for your reply. I am not sure I understand this entirely but I am starting to get the picture I think. I am a bit confused about how "y=cos(a) and x=sin(a)*2" work in relation to what I am trying to achieve. I am assuming that "a" is the angle in radians, and as I am looking for a point on the edge of an ellipse so surely the formula to find the point needs to account for the position of the center point of the elliipse and the X/Y radius?
    : :
    : : Gerry
    : :
    : :
    : Yes, you'r right.
    : It should look like this:
    : x=centerX+cos(a)*radius
    : y=centerY+sin(a)*radius*//(can't remember the name in swedish, and I don't know the name in english, but some kind of ratio)
    :
    :
    : Another thing, how does the formula with a circle look like?
    :
    Hi Niklas,

    Thanks for the update, I eventually figured it out and got it working but there are a couple of points worth noting.

    // Get angle in radions
    float angle = getAngle(lc.st.X, lc.st.Y, lc.end.X, lc.end.Y);

    // Find position
    int x = ( lc.x + lc.xRadius * sin(angle) );
    int y = ( lc.y + lc.yRadius * cos(angle) );

    The "angle" is in radions (I found the above function on the net an adapted it for my purposes).

    This does the job but this calculation seems to be an approximation. The XY posiion always ends up exactly on the perimeter of the ellipse but it does not always intersect the line exacyly. From what I can make out in the debugger, the angle is correct but the resultant position of the calculated point around the ellipse is slightly off.

    If the ellipse is a circle (i.e Xradius and Yradius are equal) then its 100% accurate), if its an ellipse, then the points 0, 90, 180 and 270 degrees are spot on but the points in between those are not perfect. The more elliptical the shape the more error there seems to be.

    In answer to your point about the circle, its very accurate.

    In answer to your point about the ratio, its provided by virtue of the fact that the calculation takes into account the X and Y radius.

    I could not figure out why the inaccuracy occurs but from what I can find on the web it seems to be generally accepted that caclulating this exactly is very difficult. It seems to relate to the fact that the angle calculated is linear on the XY plane but the angle around the ellipse is not because of the XY ratio. It looks like the angle value may need some kind of sine adjustment based on the ratio of the XY radius.

    Anyway, thank you very much for your help, you got me going in the right direction. Although not a perfect solution this works for my purposes and is good enough (although it will secretly bug me until I find the answer ;-) ).

    Gerry



  • gautamgautam Posts: 642Member
    [b][red]This message was edited by gautam at 2006-8-7 3:33:44[/red][/b][hr]
    [b][red]This message was edited by gautam at 2006-8-7 3:30:52[/red][/b][hr]
    The ratio is called eccentricity. Well its not exactly a ratio but rather it denotes how elongated the ellipse is. You will have to take care of this to get a better approximation.

    Equation of an ellipse and circumference of the ellipse -http://en.wikipedia.org/wiki/Ellipse

    The equation of a circle with the centre at origin is x*x + y*y = r*r


    : : [b][red]This message was edited by IDK at 2006-8-6 11:5:47[/red][/b][hr]
    : : : : 1. This is rather simple trigonometry, but I haven't been teached trigonometry so I don't know how it's done. This is how I would do it with my rather weak knowledge of trigonometry:
    : : : : [code]
    : : : : z---y
    : : : : | /
    : : : : _|_/
    : : : : / |/
    : : : : | x |
    : : : : ___/
    : : : : [/code]
    : : : : Point z is gotten from x value of y and y value of x ;-)
    : : : : Then sin(a) = z.y-y.y / sqrt((x.x-y.x)^2+(x.y-y.y)^2)
    : : : : Since z.y = x.y it can be replaced, and z isn't needed.
    : : : :
    : : : : 2. If you use y=cos(a) and x=sin(a)*2 to draw the ellipse, then replace a with the value obtained at 1.
    : : : :
    : : : Hi Niklas,
    : : :
    : : : Thank you for your reply. I am not sure I understand this entirely but I am starting to get the picture I think. I am a bit confused about how "y=cos(a) and x=sin(a)*2" work in relation to what I am trying to achieve. I am assuming that "a" is the angle in radians, and as I am looking for a point on the edge of an ellipse so surely the formula to find the point needs to account for the position of the center point of the elliipse and the X/Y radius?
    : : :
    : : : Gerry
    : : :
    : : :
    : : Yes, you'r right.
    : : It should look like this:
    : : x=centerX+cos(a)*radius
    : : y=centerY+sin(a)*radius*//(can't remember the name in swedish, and I don't know the name in english, but some kind of ratio)
    : :
    : :
    : : Another thing, how does the formula with a circle look like?
    : :
    : Hi Niklas,
    :
    : Thanks for the update, I eventually figured it out and got it working but there are a couple of points worth noting.
    :
    : // Get angle in radions
    : float angle = getAngle(lc.st.X, lc.st.Y, lc.end.X, lc.end.Y);
    :
    : // Find position
    : int x = ( lc.x + lc.xRadius * sin(angle) );
    : int y = ( lc.y + lc.yRadius * cos(angle) );
    :
    : The "angle" is in radions (I found the above function on the net an adapted it for my purposes).
    :
    : This does the job but this calculation seems to be an approximation. The XY posiion always ends up exactly on the perimeter of the ellipse but it does not always intersect the line exacyly. From what I can make out in the debugger, the angle is correct but the resultant position of the calculated point around the ellipse is slightly off.
    :
    : If the ellipse is a circle (i.e Xradius and Yradius are equal) then its 100% accurate), if its an ellipse, then the points 0, 90, 180 and 270 degrees are spot on but the points in between those are not perfect. The more elliptical the shape the more error there seems to be.
    :
    : In answer to your point about the circle, its very accurate.
    :
    : In answer to your point about the ratio, its provided by virtue of the fact that the calculation takes into account the X and Y radius.
    :
    : I could not figure out why the inaccuracy occurs but from what I can find on the web it seems to be generally accepted that caclulating this exactly is very difficult. It seems to relate to the fact that the angle calculated is linear on the XY plane but the angle around the ellipse is not because of the XY ratio. It looks like the angle value may need some kind of sine adjustment based on the ratio of the XY radius.
    :
    : Anyway, thank you very much for your help, you got me going in the right direction. Although not a perfect solution this works for my purposes and is good enough (although it will secretly bug me until I find the answer ;-) ).
    :
    : Gerry
    :
    :
    :
    :





  • IDKIDK Posts: 1,784Member
    : The ratio is called eccentricity. Well its not exactly a ratio but rather it denotes how elongated the ellipse is. You will have to take care of this to get a better approximation.

    I know, but one could say that it's the ratio between the height and width of the ellipse.

    :
    : Equation of an ellipse and circumference of the ellipse -http://en.wikipedia.org/wiki/Ellipse
    :
    : The equation of a circle with the centre at origin is x*x + y*y = r*r
    :
    :
    I know why it's being wrong now, after a little thinking...

    It's a little hard to expain without really drawing, but I hope you understand:
    [code]
    Circle:
    a-_d
    |
    |
    b----c

    Ellipse:
    e-h
    |
    |
    f---g
    [/code]

    Since bc is longer than fg, ad must be shorter than eh too, and that makes the angle to d, different from the alngle to h.

    If you understand my little messy explanation, it expains why it's wrong.

    I don't know how to make it right though.

    Again, how does the formula for the circle look like?
  • gerrysweeneygerrysweeney Posts: 6Member
    [b][red]This message was edited by gerrysweeney at 2006-8-7 15:53:57[/red][/b][hr]
    : [b][red]This message was edited by gautam at 2006-8-7 3:33:44[/red][/b][hr]
    : [b][red]This message was edited by gautam at 2006-8-7 3:30:52[/red][/b][hr]
    : The ratio is called eccentricity. Well its not exactly a ratio but rather it denotes how elongated the ellipse is. You will have to take care of this to get a better approximation.
    :
    : Equation of an ellipse and circumference of the ellipse -http://en.wikipedia.org/wiki/Ellipse
    :
    : The equation of a circle with the centre at origin is x*x + y*y = r*r
    :
    :
    Hi, thanks for the pointer. Having read this it does make sense and the excentricity is certainly what I noticed. I am no mathametition so have no idea how to apply this to the formula I have working, I will have a play about and see if I can make it work. Many thanks.



  • gerrysweeneygerrysweeney Posts: 6Member
    : : The ratio is called eccentricity. Well its not exactly a ratio but rather it denotes how elongated the ellipse is. You will have to take care of this to get a better approximation.
    :
    : I know, but one could say that it's the ratio between the height and width of the ellipse.
    :
    : :
    : : Equation of an ellipse and circumference of the ellipse -http://en.wikipedia.org/wiki/Ellipse
    : :
    : : The equation of a circle with the centre at origin is x*x + y*y = r*r
    : :
    : :
    : I know why it's being wrong now, after a little thinking...
    :
    : It's a little hard to expain without really drawing, but I hope you understand:
    : [code]
    : Circle:
    : a-_d
    : |
    : |
    : b----c
    :
    : Ellipse:
    : e-h
    : |
    : |
    : f---g
    : [/code]
    :
    : Since bc is longer than fg, ad must be shorter than eh too, and that makes the angle to d, different from the alngle to h.
    :
    : If you understand my little messy explanation, it expains why it's wrong.
    Yes, that seems to make sense. See the other post that points to a Wiki on the subject, its covered and there is probably enough information there for me to fumble around a solution ;-)

    : I don't know how to make it right though.
    If I figure it out, I will post it up for other people.

    : Again, how does the formula for the circle look like?
    Sorry, I thought I answered your question, i am not sure what you are asking here.

    If you are asking how the formula I used for the ellipse works for circles, then the answer is its 100% accurate.

    If you are asking what formula I am using for circles, the answer is, its the same formula I am using.


    Regards

    Gerry







  • IDKIDK Posts: 1,784Member
    : : I don't know how to make it right though.
    : If I figure it out, I will post it up for other people.
    :
    : : Again, how does the formula for the circle look like?
    : Sorry, I thought I answered your question, i am not sure what you are asking here.
    :
    :
    : If you are asking what formula I am using for circles, the answer is, its the same formula I am using.
    :

    OK, thanks.

    Here's some reasoning, but since I'm just a school kid I can't really come up with a sollution.
    [code]
    // Get angle in radions
    float angle = getAngle(lc.st.X, lc.st.Y, lc.end.X, lc.end.Y);

    // Find position
    int x = ( lc.x + lc.xRadius * sin(angle) );
    int y = ( lc.y + lc.yRadius * cos(angle) );

    float angle2 = getAngle(lc.st.X, lc.st.Y, x, y);

    v = getAngle(a,b)
    p = findPos(v)
    v2 = getAngle(a,p);
    v != v2

    getAngle(x,y) = invsin( x.y-y.y / sqrt((x.x-y.x)^2+(x.y-y.y)^2) )
    findPos(v) = {lc.x + lc.xR * sin(v), lc.y + lc.yR * cos(v)}

    v = invsin( a.y-b.y / sqrt((a.x-b.x)^2+(a.y-b.y)^2) )
    p = {lc.x + lc.xR * sin(v), lc.y + lc.yR * cos(v)}
    v2 = invsin( a.y-p.y / sqrt((a.x-p.x)^2+(a.y-p.y)^2) )

    We want v == v2, so let's do like this:
    v = invsin( a.y-b.y / sqrt((a.x-b.x)^2+(a.y-b.y)^2) )
    p = f(v)
    v = invsin( a.y-p.y / sqrt((a.x-p.x)^2+(a.y-p.y)^2) )

    Then we can write:
    { v = invsin( a.y-b.y / sqrt((a.x-b.x)^2+(a.y-b.y)^2) )
    v = invsin( a.y-p.y / sqrt((a.x-p.x)^2+(a.y-p.y)^2) ) }
    <=>
    invsin( a.y-b.y / sqrt((a.x-b.x)^2+(a.y-b.y)^2) ) = invsin( a.y-p.y / sqrt((a.x-p.x)^2+(a.y-p.y)^2) )
    <=>
    (a.y-b.y) / sqrt((a.x-b.x)^2+(a.y-b.y)^2) = (a.y-p.y) / sqrt((a.x-p.x)^2+(a.y-p.y)^2)
    [/code]

    This doesn't really solve anything, it's allreaedy written and is to no use if I throw it away.
  • gerrysweeneygerrysweeney Posts: 6Member
    : : : I don't know how to make it right though.
    : : If I figure it out, I will post it up for other people.
    : :
    : : : Again, how does the formula for the circle look like?
    : : Sorry, I thought I answered your question, i am not sure what you are asking here.
    : :
    : :
    : : If you are asking what formula I am using for circles, the answer is, its the same formula I am using.
    : :
    :
    : OK, thanks.
    :
    : Here's some reasoning, but since I'm just a school kid I can't really come up with a sollution.
    : [code]
    : // Get angle in radions
    : float angle = getAngle(lc.st.X, lc.st.Y, lc.end.X, lc.end.Y);
    :
    : // Find position
    : int x = ( lc.x + lc.xRadius * sin(angle) );
    : int y = ( lc.y + lc.yRadius * cos(angle) );
    :
    : float angle2 = getAngle(lc.st.X, lc.st.Y, x, y);
    :
    : v = getAngle(a,b)
    : p = findPos(v)
    : v2 = getAngle(a,p);
    : v != v2
    :
    : getAngle(x,y) = invsin( x.y-y.y / sqrt((x.x-y.x)^2+(x.y-y.y)^2) )
    : findPos(v) = {lc.x + lc.xR * sin(v), lc.y + lc.yR * cos(v)}
    :
    : v = invsin( a.y-b.y / sqrt((a.x-b.x)^2+(a.y-b.y)^2) )
    : p = {lc.x + lc.xR * sin(v), lc.y + lc.yR * cos(v)}
    : v2 = invsin( a.y-p.y / sqrt((a.x-p.x)^2+(a.y-p.y)^2) )
    :
    : We want v == v2, so let's do like this:
    : v = invsin( a.y-b.y / sqrt((a.x-b.x)^2+(a.y-b.y)^2) )
    : p = f(v)
    : v = invsin( a.y-p.y / sqrt((a.x-p.x)^2+(a.y-p.y)^2) )
    :
    : Then we can write:
    : { v = invsin( a.y-b.y / sqrt((a.x-b.x)^2+(a.y-b.y)^2) )
    : v = invsin( a.y-p.y / sqrt((a.x-p.x)^2+(a.y-p.y)^2) ) }
    : <=>
    : invsin( a.y-b.y / sqrt((a.x-b.x)^2+(a.y-b.y)^2) ) = invsin( a.y-p.y / sqrt((a.x-p.x)^2+(a.y-p.y)^2) )
    : <=>
    : (a.y-b.y) / sqrt((a.x-b.x)^2+(a.y-b.y)^2) = (a.y-p.y) / sqrt((a.x-p.x)^2+(a.y-p.y)^2)
    : [/code]
    :
    : This doesn't really solve anything, it's allreaedy written and is to no use if I throw it away.
    :

    Hmm thanks, I think I will not try that code ;-)
Sign In or Register to comment.