Intersecção da curva parabólica e segmento de linha
-
25-09-2019 - |
Pergunta
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);
}
Solução
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!
Outras dicas
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
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.
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.