Berechnung des Schnittpunkts der quadratischen Bezier-Kurve

Question

Dies ist definitiv die Grenzen für meine trig Wissen.

Gibt es eine Formel zum Berechnen eines Schnittpunkts zwischen einer quadratischen Bezierkurve und einer Linie?

Beispiel:

im Bild unten, ich habe P1, P2, C (die der Steuerpunkt ist) und X1, X2 (die für meine besondere Berechnung ist nur eine gerade Linie auf der X-Achse .)

Was ich gerne wissen möchte, ist die X-, Y-Position von T sowie der Winkel der Tangente bei T. am Schnittpunkt zwischen der roten Kurve und der schwarzen Linie.

Nach einer wenig Forschung und this Frage zu finden, ich weiß, ich kann:

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; 

meine X zu berechnen, Y-Position zu jedem entlang der Kurve gegebenen Punktes. Mit dieser Funktion konnte ich einfach eine Reihe von Punkten entlang der Kurve durchlaufen und prüfen, ob sich diese auf meiner X-Achse befinden. Und von dort versuche ich meinen Tangentenwinkel zu berechnen. Aber das scheint wirklich nicht der beste Weg zu sein. Jeder Mathe-Guru da draußen weiß, was der beste Weg ist?

Ich denke, dass es vielleicht ein bisschen komplizierter ist, als ich es möchte.

Answer 1

Quadratic Kurve Formel:

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

Linie Formel:

// note: this `B` is not the same as the `b` in the quadratic formula ;-) 

y=m*x+B // where m,B are known. 

Die Kurve & Linie schneiden, wo die beiden Gleichungen für die s wahr sind ame [x, y]:

Hier ist Code kommentiert und eine 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*(b-a)); }; 
 

 
// 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(p.x,p.y); 
 
    ctx.arc(p.x,p.y,4,0,Math.PI*2); 
 
    ctx.closePath(); 
 
    textPoints+=' ['+parseInt(p.x)+','+parseInt(p.y)+']'; 
 
} 
 
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

Wenn Sie nur eine Kreuzung mit einer geraden Linie in der x-Richtung müssen Sie bereits wissen, die Y-Koordinate der Kreuzung.Um die bekommen x-Koordinate so etwas tun:

• Die Gleichung für die Linie ist einfach y = b
• einstellen es gleich Ihre y-Gleichung der Bézier-Funktion y(t) bekommt man:
  b = (1 - t) * (1 - t) * p[0].y + 2 * (1 - t) * t * p[1].y + t * t * p[2].y
• die Lösung * für t bekommt man:
  t = (p[0].y - p[1].y - sqrt(b*a + p[1].y*p[1].y - p[0].y*p[2].y))/a
  mit a = p[0].y - 2*p[1].y + p[2].y
• den resultierenden t in der x-Gleichung des Einsatz Beziér Funktion x(t), um die X-Koordinate zu erhalten, und Sie sind fertig.

Sie können die Aufmerksamkeit auf einige Sonderfälle zu zahlen haben, wie wenn keine Lösung existiert, weil das Argument der Quadratwurzel dann negativ werden kann oder der Nenner (a) könnte zu Null, oder so ähnlich.

Hinterlassen Sie einen Kommentar, wenn Sie weitere Hilfe oder die Kreuzung mit beliebigen Linien benötigen.

(*) Ich habe Wolfram Alpha verwendet, um die Gleichung zu lösen, weil ich faul bin: Wolfram alpha solution.