Schnittpunkt der parabolischen Kurve und Liniensegments

Question

Ich habe eine Gleichung für eine parabolische Kurve eines bestimmten Punkt schneiden, in meinem Fall, in dem der Benutzer auf einem Diagramm geklickt.

 // 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);
 }

Dies ergibt eine grafische Darstellung, wie diese:

Ich habe auch eine Reihe von Liniensegmenten, die durch Start- und Zielkoordinaten:

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

Ich muss herausfinden, ob und wo diese Kurve schneidet diese Segmente (A):

Wenn es keine Hilfe ist, startX ist immer < endX

Ich habe das Gefühl, es gibt einen recht geradlinig Weg, dies zu tun, aber ich weiß nicht wirklich, was für suchen, noch bin ich sehr gut in „richtigen“ Mathematik bewandert, so eigentliche Code-Beispiele sehr viel würden geschätzt .

UPDATE:

Ich habe die Kreuzung Arbeits bekommt, aber meine Lösung gibt die ich für die falsche Seite der y-Achse zu koordinieren.

Ersetzen mein Ziel coords mit A bzw. B, gibt diese Gleichung für die Handlung:

(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)

Das ist eine richtige Antwort, aber ich mag die zweite mögliche Variante. Ich habe es geschafft, das durch Multiplikation zu korrigieren m mit -1 vor der Berechnung und tun das gleiche mit dem x-Wert der letzten Berechnung zurückgibt, aber das fühlt sich wie ein Hack.

LÖSUNG:

 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

Oder noch deutlicher vor.

Wenn Sie Ihre parabolische Kurve ist y(x)= A x2+ B x + C (Eq 1)

und Ihre Leitung y(x) = m x + b (Eq 2)

Die beiden möglichen Lösungen (+ und -) für x

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

Sie sollten überprüfen, ob Ihre Segmentendpunkte (in x) jeder dieser beiden Punkte enthält. Wenn sie es tun, ersetzen Sie einfach die entsprechenden x in y = m x + b Gleichung die y-Koordinate für die Kreuzung zu bekommen

Bearbeiten>

Um die letzte Gleichung bekommt man nur sagen, dass die „y“ in der Gleichung 1 ist gleich die „y“ in der Gleichung 2 (weil Sie nach einer Kreuzung suchen!). Das gibt Ihnen:

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


und Umgruppierung

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

Das ist eine quadratische Gleichung.

Gleichung 3 sind nur die zwei möglichen Lösungen für diesen quadratisch.

Edit 2>

Re-Lektüre Ihren Code, so scheint es, dass Ihre Parabel ist definiert durch y(x) = A x2


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

So in Ihrem Fall Gleichung 3 wird einfach

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

HTH!

Answer 2

Nehmen Sie die Gleichung für die Kurve und setzen Sie Ihre Linie in y = mx + b Form. Lösen Sie für x und dann bestimmen, ob X zwischen den Start- und Endpunkten für Sie Segment auskleiden.

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

Answer 3

Machst du oft genug einen separaten Test zu wünschen übrig, um zu sehen, ob eine Kreuzung vor existiert tatsächlich den Schnittpunkt der Berechnung? Wenn dem so ist, die Tatsache zu berücksichtigen, dass Ihre Parabel einen Pegel eingestellt, für die Funktion f (x, y) = y - (B * x * x) / (A * A) - insbesondere der eine, für die f (x, y) = 0. Schließen sie Ihre zwei Endpunkte in f (x, y) - wenn sie das gleiche Vorzeichen haben, sie auf der gleichen Seite der Parabel sind, während, wenn sie unterschiedliche Vorzeichen haben, sie sind auf verschiedenen Seiten die Parabel.

Nun könnte man noch ein Segment hat, dass schneidet die Parabel zweimal , und dieser Test nicht verfängt. Aber etwas über die Art und Weise, das Problem sind definiert, macht mich das Gefühl, dass vielleicht ist das OK für Ihre Anwendung.

Answer 4

Mit anderen Worten, Sie müssen für jedes Liniensegment y = Ax + B die Gleichung calulate vergleichen Sie es mit Kurvengleichung y = Cx^2 + Dx + E so Ax + B - Cx^2 - Dx - E = 0 und sehen, ob es eine Lösung zwischen startX und endX Werten ist.