[Math] Points of intersection between line and ellipse

conic sectionsgeometry

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

example 1

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() };
    }

Best Answer

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$.

Related Question