1
$\begingroup$

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() };
    }
$\endgroup$
  • $\begingroup$ "to find the point perpendicular to ..". What do you mean by a point being perpendicular to something else? $\endgroup$ – stressed out Nov 24 '17 at 1:50
  • 1
    $\begingroup$ that solution didn't work, so not really that important... but what i mean was draw a line from the center of the ellipse to the line being tested. with the line from the center being perpendicular to the line given. This worked well for everything except some situations where the line barely contacts the perimeter of the ellipse. $\endgroup$ – Hussein Sabbagh Nov 24 '17 at 2:33
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ would this work for a line segment? or only an unrestricted line? $\endgroup$ – Hussein Sabbagh Nov 24 '17 at 17:36
  • $\begingroup$ This can be modified for a segment: I'll update my answer in a few minutes. $\endgroup$ – Aretino Nov 24 '17 at 17:49
  • $\begingroup$ when you say AF1 + AF2 are you adding the 2 dot products together or adding the lines A -> F1 and A -> F2, sorry not 100% sure about the annotations. thanks for your help though, i appreciate the time you put in. $\endgroup$ – Hussein Sabbagh Nov 25 '17 at 0:26
  • $\begingroup$ $AF_1$ is the distance between points $A$ and $F_1$, and $AF_1+AF_2$ is the sum of two distances. $\endgroup$ – Aretino Nov 25 '17 at 12:42
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.