求解三次方以找到曲线上最接近某点的点 [英] Solving a cubic to find nearest point on a curve to a point
问题描述
好吧
我有一个弹丸，其位置定义为:
I have a projectile that has its position defined such that:
a.x = initialX + initialDX * time;
a.y = initialY + initialDY * time + 0.5 * gravtiy * time^2;
我希望能够预测该弹丸将与我的环境中的哪些障碍物发生碰撞.我打算检查从 A 曲线上最近点到点 P 的距离.
I want to be able to predict which obstacles in my environment this projectile will collide with. I plan on checking the distance from A the closest point on the curve to the point P.
我认为在点 A 处，曲线的切线将垂直于矢量 AP ，并且在 A 就是该点弹丸的速度 V .
I figure that at the point A the tangent to the curve will be perpendicular to the vector AP, and that the tangent to the curve at A will simply be the velocity V of the projectile at that point.
AP 点 V = 0
ap.x = initialX + initialDX * time - p.x;
ap.y = initialY + initialDY * time + gravity * time^2 - p.y;
v.x = initialDX;
v.y = initialDY + gravity * time;
=>
AP 点 V =
( 0.5 * gravity^2 ) * t^3 +
( 1.5 * gravity * initialDY ) * t^2 +
( initialDX^2 + initialDY^2 + gravity * ( initialY - p.y ) ) * t +
( initialDX * ( initialX - p.x ) + initialDY * ( initialY - p.y ) )
从这里我可以看到这是三次函数.我花了一些时间在网上进行研究，发现有一个通用方程似乎对确定根的某些值有用.
From here I can see that this is a cubic function. I have spent some time researching online and found that there is a general equation that seems to work for certain values for finding the roots.
这是我尝试实现的过程. http://www.sosmath.com/algebra/factor/fac11/fac11. html
This is the process I have attempted to implement. http://www.sosmath.com/algebra/factor/fac11/fac11.html
a = 0.5 * gravity^2;
b = 1.5 * gravity * initialDY;
c = initialDX^2 + initialDY^2 + gravity * ( initialY - p.y );
d = initialDX * ( initialX - p.x ) + initialDY * ( initialY - p.y );
A = ( c - ( b * b ) / ( 3 * a ) ) / a;
B = -( d + ( 2 * b * b * b ) / ( 27 * a * a ) - ( b * c ) / ( 3 * a ) ) / a;
workingC = -Math.pow( A, 3 ) / 27;
u = ( -B + Math.sqrt( B * B - 4 * workingC ) ) / 2; // Quadratic formula
s = Math.pow( u + B, 1 / 3 );
t = Math.pow( u, 1 / 3 );
y = s - t;
x = y - b / ( 3 * a );
当我将x重新插入到曲线的原始方程式中时，这应该给我 A .这对于某些值似乎效果很好，但是当p.y大于某个值时，我在二次方程式中没有取平方根的正数.
When I plug x back into my original equations for the curve as the time, this should give me A. This seems to work well for certain values, however when p.y is above a certain value, I don't have a positive to take a square root of in the quadratic equation.
我对数学没有足够的了解，无法理解为什么会这样，或者我可以采取什么措施来解决问题.
I don't have a full enough understanding of the math to understand why this is happening, or what I can do to resolve the issue.
在此方面的任何帮助将不胜感激.
Any help on this would be much appreciated.
更新:
我已经调整了算法以处理复杂的根，但是仍然遇到麻烦. 如果判别为负，这就是我现在要做的:
I have adjusted my algorithm to deal with complex roots, however I am still having trouble. This is what I do now if the discriminant is negative:
a = 0.5 * gravity^2;
b = 1.5 * gravity * initialDY;
c = initialDX^2 + initialDY^2 + gravity * ( initialY - p.y );
d = initialDX * ( initialX - p.x ) + initialDY * ( initialY - p.y );
A = ( c - ( b * b ) / ( 3 * a ) ) / a;
B = -( d + ( 2 * b * b * b ) / ( 27 * a * a ) - ( b * c ) / ( 3 * a ) ) / a;
workingC = -Math.pow( A, 3 ) / 27;
discriminant = B * B - 4 * workingC;
then if discriminant < 0;
uc = new ComplexNumber( -B / 2, Math.sqrt( -discriminant ) / 2 );
tc = uc.cubeRoot( );
uc.a += B;
sc = uc.cubeRoot( );
yc = sc - tc;
yc.a -= b / ( 3 * a );
x = -d / ( yc.a * yc.a + yc.b * yc.b );
由于某种原因，这仍然不能给我期望的结果.这里有什么不对劲的地方吗?
For some reason, this is still not giving me the results I expect. Is there anything that stands out as being wrong here?
推荐答案
实多项式可以具有复数根，如果该根不是实数，则它们以共轭对出现.
Real polynomials can have complex number roots and if the roots are not real, they occur in conjugate pairs.
这意味着三次方始终至少具有一个实根.
This implies cubics always have at least one real root.
现在，如果使用该方法获得复数根，则可以尝试多点地求共轭并除以三次方的常数，取倒数即可得到实根.
Now if you get a complex root using your method, you can try to get the conjugate, mutiply and divide the constant of the cubic, take reciprocal to get the real root.
因此，如果必须采用-ve数的平方根，则等同于将其模的平方根乘以虚数"i".
So if you had to take the square root of a -ve number, then it is same as multiplying the square root of its modulus by the imaginary number 'i'.
因此，如果您将根表示为(m，n)，则表示复数m + i n.那么另一个根是m-i n =(m，-n)，而m和n是实数.
So if you represent your root as (m,n) denoting the complex number m + in. Then the other root is m - in = (m, -n) and m and n are real numbers.
然后可以将三次方程写成P(x)=(x ^ 2-2m +(m ^ 2 + n ^ 2))(x-r).
The cubic can then be written as P(x) = (x^2 - 2m + (m^2 + n^2))(x-r).
因此，如果P(x)= x ^ 3-a_1 * x ^ 2 + a_2 * x-a_3，则我们得出r = a_3/(m ^ 2 + n ^ 2)(a_3是根，即r(m ^ 2 + n ^ 2))
So if P(x) = x^3 - a_1 *x^2 + a_2*x - a_3, then we have that r = a_3/(m^2 + n^2) (a_3 is the product of the roots, which is r(m^2+n^2))
获取r的更简单方法是使用公式r = a_1-2m(a_1是根的总和，即r + 2m).
A simpler way to get r would be to use the formula r = a_1 - 2m (a_1 is the sum of the roots, which is r+2m).
签出: http://en.wikipedia.org/wiki/Complex_number
这篇关于求解三次方以找到曲线上最接近某点的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
