How to find a point where a line intersects an ellipse in 2D (C#)

Question

I need to find a point where a line (its origin is ellipse' center) intersects an ellipse in 2D... I can easily find a point on a circle, because I know an angle F and the circle' radius (R):

x = x0 + R * cosF
y = y0 + R * sinF

However I just can't figure how am I supposed to deal with an ellipse... I know it's dimensions (A & B), but what is the way of finding parameter T?!

x = x0 + A * cosT
y = y0 + B * sinT

From what I understand the parameter T (T angle) is not far from the F angle (approximately +-15 degrees in some cases), but I just can't figure how to calculate it!!!

If there is a kind hearted soul, please help me with this problem...

Answer 1

The standard equation of an ellipse, stationed at 0,0, is:

1 = (x)^2 / (a)    +  (y)^2 / (b)

Where a is 1/2 the diameter on the horizontal axis, and b is 1/2 the diameter on the vertical axis.

you have a line, assuming an equation:

y = (m)(x - x0) + y0

So, let us plug-and-play!

1 = (x)^2 / (a)   +   (m(x - x0) + y0)^2 / (b)

1 = x^2 / a  +  (mx + (y0 - mx0))^2 / b

1 = x^2 / a  +  (m^2 * x^2 + 2mx*(y0 - mx0) + (y0 - mx0)^2) / b

1 = x^2 / a  + (m^2 x^2) / b + (2mx*(y0 - mx0) + (y0^2 - 2y0mx0 + m^2*x0^2)) / b

1 = ((x^2 * b) / (a * b)) + ((m^2 * x^2 * a) / (a * b)) + (2mxy0 - 2m^2xx0)/b + (y0^2 - 2y0mx0 + m^2*x0^2)/b

1 = ((bx^2 + am^2x^2)/(ab)) + (x*(2my0 - 2m^2x0))/b + (y0^2 - 2y0mx0 + m^2*x0^2)/b

0 = x^2*((b + a*m^2)/(ab)) + x*((2my0 - 2m^2x0)/b) + (((y0^2 - 2y0mx0 + m^2*x0^2)/b) - 1)

That last equation follows the form of a standard quadratic equation.

So just use the quadratic formula, with:

((b + a*m^2)/(ab))
((2my0 - 2m^2x0)/b)
and 
(((y0^2 - 2y0mx0 + m^2*x0^2)/b) - 1)

to get the X values at the intersections; Then, plug in those values into your original line equation to get the Y values.

Good luck!

Answer 2

Don't do it this way. Instead check the equation that forms an ellipse and that forming a line and solve the set:

The ellipse: (x/a)^2 + (y/b)^2 = 1 Your line: y = cx

You know a, b and c, so finding a solution is going to be easy. You'll find two solutions, because the line crosses the ellipse twice.

EDIT: Note I moved your ellipse's center to (0,0). It makes everything easier. Just add (x0,y0) to the solution.

Answer 3

public Hits<float2> EllipseLineIntersection ( float rx , float ry , float2 p1 , float2 p2 )
{
    Hits<float2> hits = default(Hits<float2>);
    float2 p3, p4;
    Rect rect = default(Rect);
    {
        rect.xMin = math.min(p1.x,p2.x);
        rect.xMax = math.max(p1.x,p2.x);
        rect.yMin = math.min(p1.y,p2.y);
        rect.yMax = math.max(p1.y,p2.y);
    }

    float s = ( p2.y - p1.y )/( p2.x - p1.x );
    float si = p2.y - ( s * p2.x );
    float a = ( ry*ry )+( rx*rx * s*s );
    float b = 2f * rx*rx * si * s;
    float c = rx*rx * si*si - rx*rx * ry*ry;

    float radicand_sqrt = math.sqrt( ( b*b )-( 4f * a * c) );
    p3.x = ( -b - radicand_sqrt )/( 2f*a );
    p4.x = ( -b + radicand_sqrt )/( 2f*a );
    p3.y = s*p3.x + si;
    p4.y = s*p4.x + si;

    if( rect.Contains(p3) ) hits.Push( p3 );
    if( rect.Contains(p4) ) hits.Push( p4 );
    return hits;
}
public struct Hits<T>
{
    public byte count;
    public T point0, point1;
    public void Push ( T val )
    {
        if( count==0 ) { point0 = val; count ++; }
        else if( count==1 ) { point1 = val; count ++; }
        else print("This structure can only fit 2 values");
    }
}

Answer 4

I wrote a C# code for your problem and I hope you can find it helpful. the distance function inside this code calculates euclidean distance between two points in space.

wX denotes horizontal radios of ellipse and wY denotes vertical radios.

private PointF LineIntersectEllipse(PointF A, PointF B, float wX, float wY)
{
      double dx = B.X - A.X;
      double dy = B.Y - A.Y;
      double theta = Math.Atan2(dy, dx);
      double r = distance(A, B) - ((wX * wY) / Math.Sqrt(Math.Pow(wY * Math.Cos(theta), 2) + Math.Pow(wX * Math.Sin(theta), 2)));
      return PointF((float)(A.X + r * Math.Cos(theta)), (float)(A.Y + r * Math.Sin(theta)));
}

Answer 5

Andrew ?ukasik posted a good and useful answer, however it is not using regular C# types. As I wrote in the comments, I converted the code using System.Drawing objects PointF and RectangleF. I found out that if the points given as parameters are aligned as a vertical or horizontal line, then "rect" will have a width or a height equal to 0. Then, rect.Contains(point) will return false even if the point is on this line.

I also modified the "Hits" structure to check if the point pushed is not already existing, which is the case if the line is perfectly tangent, then p3 and p4 will have same coordinates, as the exact tangent point is the only crossing point.

Here is the new code taking care of all the cases :

public static Hits<PointF> EllipseLineIntersection0(float rx, float ry, PointF p1, PointF p2)
{
    Hits<PointF> hits = default(Hits<PointF>);
    PointF p3 = new PointF();
    PointF p4 = new PointF();

    var rect = default(RectangleF);
    rect.X = Math.Min(p1.X, p2.X);
    rect.Width = Math.Max(p1.X, p2.X) - rect.X;
    rect.Y = Math.Min(p1.Y, p2.Y);
    rect.Height = Math.Max(p1.Y, p2.Y) - rect.Y;

    float s = (p2.Y - p1.Y) / (p2.X - p1.X);
    float si = p2.Y - (s * p2.X);
    float a = (ry * ry) + (rx * rx * s * s);
    float b = 2f * rx * rx * si * s;
    float c = rx * rx * si * si - rx * rx * ry * ry;
        
    float radicand_sqrt = (float)Math.Sqrt((b * b) - (4f * a * c));
    p3.X = (-b - radicand_sqrt) / (2f * a);
    p4.X = (-b + radicand_sqrt) / (2f * a);
    p3.Y = s * p3.X + si;
    p4.Y = s * p4.X + si;

    if (rect.Width == 0)
    {
        if (p3.Y >= rect.Y && p3.Y <= rect.Y + rect.Height) hits.Push(p3);
        if (p4.Y >= rect.Y && p4.Y <= rect.Y + rect.Height) hits.Push(p4);
    }
    else if (rect.Height == 0)
    {
        if (p3.X >= rect.X && p3.X <= rect.X + rect.Width) hits.Push(p3);
        if (p4.X >= rect.X && p4.X <= rect.X + rect.Width) hits.Push(p4);
    }
    else
    {
        if (rect.Contains(p3)) hits.Push(p3);
        if (rect.Contains(p4)) hits.Push(p4);
    }

    return hits;
}

public struct Hits<T>
{
    public byte Count;
    public T P0, P1;

    public void Push(T val)
    {
        if (Count == 0) { P0 = val; Count++; }
        else if (Count == 1) { if (!P0.Equals(val)) { P1 = val; Count++; } }
        else throw new OverflowException("Structure Hits can only fit 2 values.");
    }
}