The intersection of the parabolic curve and the segment

Question

I have an equation for a parabolic curve intersecting a specified point, in my case, when the user clicked on the 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 like this:

I also have a series of line segments defined by the 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 this helps, startX always < endX

I feel that there is a pretty direct way to do this, but I really don’t know what to look for, and I am not very good at “right” math, so actual code examples would be very appreciated.

UPDATE:

An intersection works for me, but my solution gives me the coordinate for the wrong side of the y axis.

Replacing my target coordinates with A and B, respectively, gives this equation for the graph:

 (x * x) / A * (B/A) // this simplifies down to: (B * x * x) / (A * A) // which i am the equating to the line 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 the correct answer, but I want the second option. I managed to fix this by multiplying m by -1 before calculating and doing the same with the value x returned by the last calculation, but this seems like a hack.

DECISION:

  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 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 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, even more clearly.

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

and your string y(x) = mx + b (Eq 2)

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

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

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

Edit>

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

A x 2 + B x + C = mx + b


and regrouping

A x 2 + (Bm) x + (Cb) = 0

This is a quadratic equation.

Equation 3 is just two possible solutions for this quadratic.

Change 2>

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


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

So in your case, Eq 3 just becomes

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

NTN!

Answer 2

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

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

Answer 3

You do this often enough to get a separate test to see if there is an intersection before the actual calculation of the intersection point? If yes, consider the fact that your parabola is a set of levels for the function f (x, y) = y - (B * x * x) / (A * A) - in particular, the one for which f (x, y ) = 0. Connect your two endpoints to f (x, y) - if they have the same sign, they are on the same side of the parabola, and if they have different signs, they are on different sides of the parabola.

Now you can still have a segment that crosses the parabola twice, and this test will not catch it. But something about how you identify the problem makes me feel like maybe this is normal for your application.

Answer 4

In other words, you need to calculate the equation for each segment of the line y = Ax + B compare it with the equation of the curve y = Cx^2 + Dx + E , therefore Ax + B - Cx^2 - Dx - E = 0 and see if solution between startX and endX .