Points of intersection between line and ellipse

Question

I'm trying to find out if a line intersects an ellipse.

I tried to do this without finding the intersection points at first, but this didn't work out well. So now I'm just trying to find the two intersection points and then check if they are on the line segment.

First I tried to implement an algorithm to find a line, perpendicular to the line segment, from the center of the ellipse to the line segment. If either end point was in the ellipse or the intersection point was both on the line segment and in the ellipse, then they intersected. However this failed around the perimeter of the ellipse in some situations.

So next I tried to implement an algorithm discussed in: Coordinates of the intersection points between an ellipse and a chord line

I used Hamed's answer. However, it doesn't appear to be working for me. I was hoping someone could tell me what I'm doing wrong. The $x$ values are coming out much higher than they should, and it often determines that there aren't real roots when there are. I'm not seeing the difference between my implementation and the solution. I'm just curious if I implemented it incorrectly, the equation is wrong or maybe there is something else I'm missing?

Thanks in advance, I appreciate any assistance I can get as I've hit a road block at this point.

Edit: $a$ and $b$ are of arbitrary size, $a$ can be larger than $b$ and vice versa. the ellipse is at the origin $(0,0)$ and the line is a line segment which is defined by end points. you'll also notice I multiplied things by themselves rather than use the built in function for squaring something, as I've read it's expensive in terms of computing power.

Edit: here is an example

public function lineTest( test_ellipse:Geometry_Ellipse, test_line:Geometry_Line ):Object {
        // get the variables that define the line and ellipse
        var m:Number = test_line.getSlope();
        var c:Number = test_line.getY_Intercept();
        var a:Number = test_ellipse.getRadius_X();
        var b:Number = test_ellipse.getRadius_Y();

        // check for division by 0 and sqrt of negative values
        if( (b*b)+(m*a)*(m*a)-(c*c) >= 0 && (b*b)+(m*a)*(m*a) != 0 ) {
            // get intersection points
            var point_1:Geometry_Coordinate = new Geometry_Coordinate(
                ( (m*c*a)*(m*c*a) + (a*b)*Math.sqrt((b*b)+(m*a)*(m*a)-(c*c)) ) / ( (b*b)+(m*a)*(m*a) ),
                ( (c*b)*(c*b) - ((m*a)*b)*Math.sqrt((b*b)+(m*a)*(m*a)-(c*c)) ) / ( (b*b)+(m*a)*(m*a) ),
                0
            );
            var point_2:Geometry_Coordinate = new Geometry_Coordinate(
                ( (m*c*a)*(m*c*a) - (a*b)*Math.sqrt((b*b)+(m*a)*(m*a)-(c*c)) ) / ( (b*b)+(m*a)*(m*a) ),
                ( (c*b)*(c*b) + ((m*a)*b)*Math.sqrt((b*b)+(m*a)*(m*a)-(c*c)) ) / ( (b*b)+(m*a)*(m*a) ),
                0
            );

            // check if points are on line segment
            // ...

            return { "result":true, "points":new Array(point_1, point_2) };
        } else {
            trace("no real values");
        }

        return { "result":false, "points":new Array() };
    }

Answer 1

I wasn't able to determine what was wrong with the previous implementation... however, I was able to find the points of intersection using a different equation.

using the quadratic equation provided at: http://www.analyzemath.com/Calculators/ellipse_line_calc.html I was able to reduce the equation they provided to the following quadratic equation:

ellipse: x^2/A^2 + y^2/B^2 = 1 line: mx + b = y

(B^2+A^2*m^2)x^2+(2*m*A^2*b)x+(A^2*b^2-A^2*B^2) = 0

after getting this quadratic equation and a general solution for quadratic equations ( provided by: http://pages.mtu.edu/~shene/COURSES/cs201/NOTES/chap03/quad-2.html ) I was able to find 2 X values and then plug those into the equation for the line to find the 2 Y values.

    // find x values of a quadratic function defined by
    // Ax^2 + Bx + C = 0
    public function solveQuadratic( A:Number, B:Number, C:Number ):Array {
        var sqrt_val:Number = (B*B) - (4*A*C);
        if( sqrt_val >= 0 ) {
            return new Array(
                (1/(2*A))*(-B + Math.sqrt(sqrt_val)),
                (1/(2*A))*(-B - Math.sqrt(sqrt_val))
            );
        } else {
            throw new Error("No real roots.");
        }
    }

    public function lineTest( test_line:Geometry_Line, test_ellipse:Geometry_Ellipse ):Object {
        // get the variables that define the line and ellipse
        var m:Number = test_line.getSlope();
        var b:Number = test_line.getY_Intercept();
        var A:Number = test_ellipse.getRadius_X();
        var B:Number = test_ellipse.getRadius_Y();

        // ellipse = x^2/A^2 + y^2/B^2 = 1, line = mx + b = y
        // (B^2+A^2*m^2)x^2+(2*m*A^2*b)x+(A^2*b^2-A^2*B^2) = 0
        var val_1:Number = (B*B)+((A*A)*(m*m));
        var val_2:Number = (2*m*(A*A)*b);
        var val_3:Number = ((A*A)*(b*b)-(A*A)*(B*B));

        try {
            var points:Array = solveQuadratic(val_1, val_2, val_3);
            var point_1:Geometry_Coordinate = new Geometry_Coordinate(points[0], (m*points[0]+b), 0);
            var point_2:Geometry_Coordinate = new Geometry_Coordinate(points[1], (m*points[1]+b), 0);

            // check if points are on line segment
            // ...

            return { "result":true, "points":new Array(point_1, point_2) };
        } catch( e:Error ) {
            return { "result":false, "points":new Array() };
        }
    }

Answer 2

To find if a certain line $r$ intersects an ellipse, I'd suggest the following method. You are required first of all to know the positions $F_1$ and $F_2$ of the foci of the ellipse, and its semi-major axis $a$.

1) Find the symmetric $F_1'$ of focus $F_1$ with respect to $r$.

2) Find the intersection $P$ between $r$ and line $F_2F_1'$.

3) Compute $PF_1+PF_2$: if $PF_1+PF_2<2a$ then $r$ intersects the ellipse; if $PF_1+PF_2>2a$ then $r$ doesn't intersects the ellipse; if $PF_1+PF_2=2a$ then $r$ is tangent to the ellipse.

EDIT.

If we want to find if a segment $AB$ intersects the ellipse, we can follow steps 1) and 2) above to find $P$ (where $r$ is of course the line containing $AB$). Segment $AB$ intersects the ellipse if and only if one of the following cases holds:

a) $AF_1+AF_2\ge2a$ AND $BF_1+BF_2\le2a$;

b) $AF_1+AF_2\le2a$ AND $BF_1+BF_2\ge2a$;

c) $AF_1+AF_2>2a$ AND $BF_1+BF_2>2a$ AND $PF_1+PF_2<2a$ AND $P$ is inside $AB$.