Intersecção da curva parabólica e segmento de linha

Question

Eu tenho uma equação parabólica curva de interseção de um ponto especificado, no meu caso, onde o usuário clicou em um gráfico.

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

Isso dá um gráfico como este:

Eu também tenho uma série de segmentos de reta definidos por coordenadas de início e fim:

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

Eu preciso saber se e onde esta curva intersecta os segmentos (A):

Se for de alguma ajuda, startX é sempre < endX

Tenho a sensação que há bastante simples maneira de fazer isso, mas eu realmente não sei o que procurar, nem sou muito versado em "adequado" de matemática, de modo real exemplos de código seria muito apreciado.

ATUALIZAÇÃO:

Eu tenho o cruzamento de trabalho, mas a minha solução me dá as coordenadas para o lado errado do eixo-y.

Substituir o meu destino coords com A e B, respectivamente, dá a esta equação para o enredo:

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

Este é uma resposta correta, mas eu quero a segunda variação possível.Eu consegui corrigir esse multiplicando m -1 antes de cálculo e fazendo o mesmo com o valor de x, o último cálculo retorna, mas que se sente como um hack.

SOLUÇÃO:

 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

Ou, mais explícito ainda.

Se sua curva parabólica for y(x)= A x2+ B x + C (Eq 1)

E sua linha é y(x) = m x + b (Eq 2)

As duas soluções possíveis (+ e -) para x são

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

Você deve verificar se os pontos de extremidade do segmento (em x) contêm qualquer um desses dois pontos. Se o fizerem, basta substituir o X correspondente na equação y = mx + b para obter a coordenada y para a interseção

Editar>

Para obter a última equação, você apenas diz que o "Y" na Eq 1 é igual ao "y" na Eq 2 (porque você está procurando uma interseção!). Isso te dá:

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


e reagrupamento

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

Que é uma equação quadrática.

A equação 3 são apenas as duas soluções possíveis para este quadrático.

Editar 2>

Relendo seu código, parece que sua parábola é definida por y(x) = A x2


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

Então, no seu caso, a eq 3 se torna simplesmente

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

HTH!

Answer 2

Pegue a equação para a curva e coloque sua linha na forma y = mx +b. Resolva para X e, em seguida, determine se X está entre os seus pontos de partida e final para o segmento de linha.

Verificação de saída: http://mathcentral.uregina.ca/qq/database/qq.09.03/senthil1.html

Answer 3

Você está fazendo isso muitas vezes suficiente para desejar um teste separado para ver se uma intersecção existe antes de calcular o ponto de intersecção?Se assim for, considere o fato de que a sua parábola é um conjunto de nível para a função f(x, y) = y - (B * x * x) / (A * A) -- especificamente, para os quais f(x, y) = 0.Ligue os dois pontos de extremidade em f(x,y) -- se eles têm o mesmo sinal, eles estão do mesmo lado da parábola, enquanto que, se eles têm sinais diferentes, eles estão em lados diferentes da parábola.

Agora, você ainda pode ter um segmento que intercepta a parábola duas vezes, e este teste não pegar.Mas alguma coisa sobre a forma como você define o problema, faz-me sentir que talvez seja o que está OK para a sua aplicação.

Answer 4

Em outras palavras, você precisa calular a equação para cada segmento de linha y = Ax + B Compare -o para curvar a equação y = Cx^2 + Dx + E assim Ax + B - Cx^2 - Dx - E = 0 e veja se há uma solução entre startX e endX valores.