Solving a cubic to find nearest point on a curve to a point...

Question

Ok,

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;

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.

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 dot 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 dot 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.

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

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.

UPDATE:

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?

Answer 1

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.

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'.

So if you represent your root as (m,n) denoting the complex number m + i*n. Then the other root is m - i*n = (m, -n) and m and n are real numbers.

The cubic can then be written as P(x) = (x^2 - 2m + (m^2 + n^2))(x-r).

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

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

Check out: http://en.wikipedia.org/wiki/Complex_number