Intersection of parabolic curve and line segment

Question

I have an equation for a parabolic curve intersecting a specified point, in my case where the user clicked on a graph.

 // this would typically be mouse coords on the graph
 var _target:Point = new Point(100, 50);

 public static function plot(x:Number, target:Point):Number{
  return (x * x) / target.x * (target.y / target.x);
 }

This gives a graph such as this:

I also have a series of line segments defined by start and end coordinates:

startX:Number, startY:Number, endX:Number, endY:Number

I need to find if and where this curve intersects these segments (A):

If it's any help, startX is always < endX

I get the feeling there's a fairly straight forward way to do this, but I don't really know what to search for, nor am I very well versed in "proper" math, so actual code examples would be very much appreciated.

UPDATE:

I've got the intersection working, but my solution gives me the coordinate for the wrong side of the y-axis.

Replacing my target coords with A and B respectively, gives this equation for the plot:

(x * x) / A * (B/A)

// this simplifies down to:
(B * x * x) / (A * A)

// which i am the equating to the line's equation
(B * x * x) / (A * A) =  m * x + b

// i run this through wolfram alpha (because i have no idea what i'm doing) and get:
(A * A * m - A * Math.sqrt(A * A * m * m + 4 * b * B)) / (2 * B)

This is a correct answer, but I want the second possible variation. I've managed to correct this by multiplying m with -1 before the calculation and doing the same with the x value the last calculation returns, but that feels like a hack.

SOLUTION:

 public static function intersectsSegment(targetX:Number, targetY:Number, startX:Number, startY:Number, endX:Number, endY:Number):Point {
  // slope of the line
  var m:Number = (endY - startY) / (endX - startX);

  // where the line intersects the y-axis
  var b:Number = startY - startX * m;

  // solve the two variatons of the equation, we may need both
  var ix1:Number = solve(targetX, targetY, m, b);
  var ix2:Number = solveInverse(targetX, targetY, m, b);

  var intersection1:Point;
  var intersection2:Point;

  // if the intersection is outside the line segment startX/endX it's discarded
  if (ix1 > startX && ix1 < endX) intersection1 = new Point(ix1, plot(ix1, targetX, targetY));
  if (ix2 > startX && ix2 < endX) intersection2 = new Point(ix2, plot(ix2, targetX, targetY));

  // somewhat fiddly code to return the smallest set intersection
  if (intersection1 && intersection2) {
   // return the intersection with the smaller x value
   return intersection1.x < intersection2.x ? intersection1 : intersection2;
  } else if (intersection1) {
   return intersection1;
  }

  // this effectively means that we return intersection2 or if that's unset, null
  return intersection2;
 }

 private static function solve(A:Number, B:Number, m:Number, b:Number):Number {
  return (m + Math.sqrt(4 * (B / (A * A)) * b + m * m)) / (2 * (B / (A * A)));
 }

 private static function solveInverse(A:Number, B:Number, m:Number, b:Number):Number {
  return (m - Math.sqrt(4 * (B / (A * A)) * b + m * m)) / (2 * (B / (A * A)));
 }

 public static function plot(x:Number, targetX:Number, targetY:Number):Number{
  return (targetY * x * x) / (targetX * targetX);
 }

Answer 1

Or, more explicit yet.

If your parabolic curve is y(x)= A x2+ B x + C (Eq 1)

and your line is y(x) = m x + b (Eq 2)

The two possible solutions (+ and -) for x are

x = ((-B + m +- Sqrt[4 A b + B^2 - 4 A C - 2 B m + m^2])/(2 A))   (Eq 3)

You should check if your segment endpoints (in x) contains any of these two points. If they do, just replace the corresponding x in the y=m x + b equation to get the y coordinate for the intersection

Edit>

To get the last equation you just say that the "y" in eq 1 is equal to the "y" in eq 2 (because you are looking for an intersection!). That gives you:

A x2+ B x + C = m x + b


and regrouping

A x2+ (B-m) x + (C-b) = 0

Which is a quadratic equation.

Equation 3 are just the two possible solutions for this quadratic.

Edit 2>

re-reading your code, it seems that your parabola is defined by y(x) = A x2


where
A = (target.y / (target.x)2)

So in your case Eq 3 becomes simply

 x = ((m +- Sqrt[4 A b + m^2])/(2 A))   (Eq 3b)  

HTH!

Answer 2

Take the equation for the curve and put your line into y = mx +b form. Solve for x and then determine if X is between your your start and end points for you line segment.

Check out: http://mathcentral.uregina.ca/QQ/database/QQ.09.03/senthil1.html

Answer 3

Are you doing this often enough to desire a separate test to see if an intersection exists before actually computing the intersection point? If so, consider the fact that your parabola is a level set for the function f(x, y) = y - (B * x * x) / (A * A) -- specifically, the one for which f(x, y) = 0. Plug your two endpoints into f(x,y) -- if they have the same sign, they're on the same side of the parabola, while if they have different signs, they're on different sides of the parabola.

Now, you still might have a segment that intersects the parabola twice, and this test doesn't catch that. But something about the way you're defining the problem makes me feel that maybe that's OK for your application.

Answer 4

In other words, you need to calulate the equation for each line segment y = Ax + B compare it to curve equation y = Cx^2 + Dx + E so Ax + B - Cx^2 - Dx - E = 0 and see if there is a solution between startX and endX values.