Intersezione della curva parabolica e segmento

Question

Ho un'equazione di una curva parabolica che interseca un punto specifico, nel mio caso in cui l'utente ha fatto clic su un grafico.

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

Questo dà un grafico come questo:

Ho anche una serie di segmenti di linea definita da coordinate iniziale e finale:

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

Ho bisogno di trovare se e dove questa curva interseca questi segmenti (A):

Se si tratta di alcun aiuto, startX è sempre < endX

ho la sensazione che c'è un modo abbastanza semplice per fare questo, ma io non so davvero cosa cercare, né sono molto ben versati nella "propria" la matematica, gli esempi di codice in modo effettivo sarebbe molto apprezzato .

UPDATE:

Ho il lavoro di intersezione, ma la mia soluzione mi dà la coordinata per la parte sbagliata della y.

La sostituzione mie coordinate bersaglio con A e B, rispettivamente, dà questa equazione per la trama:

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

Questo è una risposta corretta, ma voglio la seconda variante possibile. Sono riuscito a correggere questo moltiplicando m con -1 prima del calcolo e fare lo stesso con il valore x le ultime dichiarazioni di calcolo, ma che si sente come un hack.

SOLUZIONE:

 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

In alternativa, più esplicito ancora.

Se la curva parabolica è y(x)= A x2+ B x + C (Eq 1)

e la vostra linea è y(x) = m x + b (Eq 2)

Le due soluzioni possibili (+ e -) per x sono

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

Si dovrebbe controllare se gli endpoint di settore (in x) contiene uno di questi due punti. Se lo fanno, basta sostituire le x corrispondenti nella y = m x + b equazione per ottenere la coordinata y per l'intersezione

Modifica>

Per ottenere l'ultima equazione hai appena detto che la "y" in eq 1 è pari al "y" in eq 2 (perché siete alla ricerca di un incrocio!). Che ti dà:

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


e raggruppamento

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

Che è un'equazione di secondo grado.

L'equazione 3 sono solo due possibili soluzioni per questo quadratica.

Modifica 2>

rileggendo il codice, sembra che la vostra parabola è definita da y(x) = A x2


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

Quindi nel tuo caso l'equazione 3 diventa semplicemente

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

HTH!

Answer 2

Prendere l'equazione per la curva e mettere la vostra linea in y = mx + b modulo. Risolvere per x e quindi determinare se X è tra le vostre punti iniziale e finale per voi segmento di linea.

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

Answer 3

stai facendo questo abbastanza spesso a desiderare un test separato per vedere se esiste un incrocio prima di poter realmente calcolare il punto di intersezione? In caso affermativo, considerare il fatto che la parabola è un insieme di livello per la funzione f (x, y) = y - (B * x * x) / (A * A) - in particolare, quello per cui f (x, y) = 0. Plug vostri due punti finali in f (x, y) - se hanno lo stesso segno, sono sullo stesso lato della parabola, mentre se hanno segni diversi, sono su lati diversi la parabola.

Ora, si potrebbe avere ancora un segmento che interseca la parabola due volte , e questo test non capito. Ma qualcosa nel modo in cui si sta definendo il problema mi fa sentire che forse questo è ok per la vostra applicazione.

Answer 4

In altre parole, è necessario Calulate l'equazione per ogni segmento di linea y = Ax + B confrontarlo con equazione della curva y = Cx^2 + Dx + E così Ax + B - Cx^2 - Dx - E = 0 e vedere se c'è una soluzione tra i valori startX e endX.