3
$\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$
2
  • $\begingroup$ "to find the point perpendicular to ..". What do you mean by a point being perpendicular to something else? $\endgroup$ Commented Nov 24, 2017 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$ Commented Nov 24, 2017 at 2:33

2 Answers 2

Reset to default
2
$\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$
8
  • $\begingroup$ would this work for a line segment? or only an unrestricted line? $\endgroup$ Commented Nov 24, 2017 at 17:36
  • $\begingroup$ This can be modified for a segment: I'll update my answer in a few minutes. $\endgroup$ Commented Nov 24, 2017 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$ Commented Nov 25, 2017 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$ Commented Nov 25, 2017 at 12:42
  • $\begingroup$ @Intelligentipauca Sorry to dig this up 6 years later but this doesn't seem right to me? See this example that is clearly intersecting. The line F1'F2 doesn't intersect r anywhere close to the ellipse. imgur.com/a/ZVGyY0T $\endgroup$ Commented Oct 19, 2023 at 16:40
1
$\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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.