Calculation of the intersection point of a quadratic Bezier curve

Question

This definitely pushes the limits on my knowledge of triggers.

Is there a formula for calculating the intersection point between a quadratic Bezier curve and a line?

Example:

in the image below, I have P1, P2, C (which is the control point) and X1, X2 (which for my specific calculation is a straight line on the X axis.)

What I would like to know is the position of X, YT, as well as the angle of the tangent in T. at the intersection between the red curve and the black line.

After doing a little research and searching for this question, I know that I can use:

t = 0.5; // given example value x = (1 - t) * (1 - t) * p[0].x + 2 * (1 - t) * t * p[1].x + t * t * p[2].x; y = (1 - t) * (1 - t) * p[0].y + 2 * (1 - t) * t * p[1].y + t * t * p[2].y; 

to calculate my position X, Y at any given point along the curve. Therefore, using this, I could just skip a bunch of points along the curve, checking to see if there is an X axis on my intersecting axis. And from there try to calculate my tangential angle. But this is really not the best way to do this. Does any mathematician-guru know which is the best way?

I think that maybe this is a little harder than I want.

Answer 1

The formula of a quadratic curve:

 y=ax^2+bx+c // where a,b,c are known 

Line formula:

 // note: this `B` is not the same as the `b` in the quadratic formula ;-) y=m*x+B // where m,B are known. 

The curve and the line intersect when both equations are true for the same [x, y]:

Here's the annotated code and demo:

 // canvas vars var canvas=document.getElementById("canvas"); var ctx=canvas.getContext("2d"); var cw=canvas.width; var ch=canvas.height; // linear interpolation utility var lerp=function(a,b,x){ return(a+x*(ba)); }; // qCurve & line defs var p1={x:125,y:200}; var p2={x:250,y:225}; var p3={x:275,y:100}; var a1={x:30,y:125}; var a2={x:300,y:175}; // calc the intersections var points=calcQLintersects(p1,p2,p3,a1,a2); // plot the curve, line & solution(s) var textPoints='Intersections: '; ctx.beginPath(); ctx.moveTo(p1.x,p1.y); ctx.quadraticCurveTo(p2.x,p2.y,p3.x,p3.y); ctx.moveTo(a1.x,a1.y); ctx.lineTo(a2.x,a2.y); ctx.stroke(); ctx.beginPath(); for(var i=0;i<points.length;i++){ var p=points[i]; ctx.moveTo(px,py); ctx.arc(px,py,4,0,Math.PI*2); ctx.closePath(); textPoints+=' ['+parseInt(px)+','+parseInt(py)+']'; } ctx.font='14px verdana'; ctx.fillText(textPoints,10,20); ctx.fillStyle='red'; ctx.fill(); /////////////////////////////////////////////////// function calcQLintersects(p1, p2, p3, a1, a2) { var intersections=[]; // inverse line normal var normal={ x: a1.y-a2.y, y: a2.x-a1.x, } // Q-coefficients var c2={ x: p1.x + p2.x*-2 + p3.x, y: p1.y + p2.y*-2 + p3.y } var c1={ x: p1.x*-2 + p2.x*2, y: p1.y*-2 + p2.y*2, } var c0={ x: p1.x, y: p1.y } // Transform to line var coefficient=a1.x*a2.y-a2.x*a1.y; var a=normal.x*c2.x + normal.y*c2.y; var b=(normal.x*c1.x + normal.y*c1.y)/a; var c=(normal.x*c0.x + normal.y*c0.y + coefficient)/a; // solve the roots var roots=[]; d=b*b-4*c; if(d>0){ var e=Math.sqrt(d); roots.push((-b+Math.sqrt(d))/2); roots.push((-b-Math.sqrt(d))/2); }else if(d==0){ roots.push(-b/2); } // calc the solution points for(var i=0;i<roots.length;i++){ var minX=Math.min(a1.x,a2.x); var minY=Math.min(a1.y,a2.y); var maxX=Math.max(a1.x,a2.x); var maxY=Math.max(a1.y,a2.y); var t = roots[i]; if (t>=0 && t<=1) { // possible point -- pending bounds check var point={ x:lerp(lerp(p1.x,p2.x,t),lerp(p2.x,p3.x,t),t), y:lerp(lerp(p1.y,p2.y,t),lerp(p2.y,p3.y,t),t) } var x=point.x; var y=point.y; // bounds checks if(a1.x==a2.x && y>=minY && y<=maxY){ // vertical line intersections.push(point); }else if(a1.y==a2.y && x>=minX && x<=maxX){ // horizontal line intersections.push(point); }else if(x>=minX && y>=minY && x<=maxX && y<=maxY){ // line passed bounds check intersections.push(point); } } } return intersections; } 

 body{ background-color: ivory; padding:10px; } #canvas{border:1px solid red;} 

 <h4>Calculate intersections of QBez-Curve and Line</h4> <canvas id="canvas" width=350 height=350></canvas> 

Answer 2

If you only need the intersection with a straight line in the x direction, you already know the y-coordinate of the intersection. To get the x coordinate, do the following:

• The equation for your string is just y = b
• By setting it equal to your y-equation of the function beziér y(t) , you get:
  b = (1 - t) * (1 - t) * p[0].y + 2 * (1 - t) * t * p[1].y + t * t * p[2].y
• The solution * for t gets you:
  t = (p[0].y - p[1].y - sqrt(b*a + p[1].y*p[1].y - p[0].y*p[2].y)) / a
  with a = p[0].y - 2*p[1].y + p[2].y
• Insert the resulting t into your x-equation of the function beziér x(t) to get the x coordinate, and you are done.

You may need to pay attention to some special cases, for example, when there is no solution, because the square root argument may then become negative, or the denominator ( a ) may become zero or something like that.

Leave a comment if you need more help or intersecting with arbitrary lines.

(*) I used tungsten alpha to solve the equation, because I'm lazy: Wolfram alpha solution .