Closest approach of two particles.

[luckykaa]

So, I'm trying to work out whether a projectile will hit a moving target.  That is, it its closest approach within the collision sphere of the target.

I have the position and velocity of the target and the position and velocity of the target.  The obvious way of doing this is work out the position w.r.t time, use pythagoras to work out the distance (or distance squared because it makes things easier), differentiate to work out the time of closest approach and then put t back into the previous formula to work out the distance. 

It works.  Probably.  But there has to be a nicer way.  It's not like I need to know the time this happens or the actual positions.  Just the distance.  Adding the extra variable just seems to be making things horribly complicated. 

So far what I have it that we can assume that the target is stationary at the origin, and subtract its position and velocity from our projectile, and work out closest approach to the origin.  Now, this will be when the origin is at a right angle to the modified vector.  I just can't work out how to establish how close this is.

Advice, mathematical geniuses of the interwebs?

Comments

[ingaborg.livejournal.com]

Does the projectile fall under gravity?

[luckykaa.livejournal.com]

Nope. It's all just straight vectors.

[ingaborg.livejournal.com]

So...erm, yes. My first approach would be to google for ready-make answers.

To work out closest distance between vector and point, I think there is a simple bit of vector maths that does the trick. I have a function in my javascript that does this...hang on...here it is, dunno if it's what you need?

function LineCircleIntersection(circleX, circleY, radius, p1X, p1Y, p2X, p2Y)
{
// finds whether the line intersects the circle
// also returns the square of the shortest distance from centre to line
// usually squared distance can be used for comparisons: this saves a square root operation
// circleX, circleY defines circle centre
// radius is circle radius
// p1X, p1Y defines start of line
// p2X, p2Y defines end of line
// note the two points must be different to avoid error (line must not have 0 length)

var dirX = p2X - p1X; // find vector pointing along line
var dirY = p2Y - p1Y;

var diffX = circleX - p1X; // find vector pointing from line start to circle centre
var diffY = circleY - p1Y;

// find proportion of line length travelled to reach the point closest to the circle centre
// (projection of diff onto dir)
var t = DotProduct(diffX, diffY, dirX, dirY) / DotProduct(dirX, dirY, dirX, dirY);
if (t < 0) { t = 0; } // if closest point before start of line, find distance to line start
if (t > 1) { t = 1; } // if closest point after end of line, find distance to line end

var nearestX = p1X + (t * dirX); // find coordinates of point on line nearest circle centre
var nearestY = p1Y + (t * dirY);

var distanceX = circleX - nearestX; // find vector from circle centre to closest point on line
var distanceY = circleY - nearestY;

// find square of distance from circle centre to line
var distance_squared = DotProduct(distanceX, distanceY, distanceX, distanceY);

// return true if distance to line less than radius
return {_collision: (distance_squared <= radius * radius), _distance_squared:distance_squared};
}

[luckykaa.livejournal.com]

Thanks. That looks like it does exactly what I want.

I did try googling. Everyone came up with my hideous complicated method.

[luckykaa.livejournal.com]

Ah! I think I've realised where I was going wrong! I was representing my live as a point and a vector. I should be representing it as a normal and distance to origin.

Now to look at your code and work out if that's what you;re doing:)

[ingaborg.livejournal.com]

I represented my line as two points - and I think it's equivalent to what you said first, a point and a vector, because the first point is current location of projectile, and the vector is its direction of movement expressed as a normalised vector. So I can get the 2nd point easily, by adding velocity to current position.

Still, I agree there ought to be a simple formula for the distance between 2 objects moving in a straight line.

[luckykaa.livejournal.com]

Yes. Follow it now. dot project for projection of position vector onto line vector. Use that to establish distance. Use that to establish position, and then work out he square difference.

I'm just a bit confused by this line:

var t = DotProduct(diffX, diffY, dirX, dirY) / DotProduct(dirX, dirY, dirX, dirY);

Isn't the dot product going to be scaled by the square root of that? In my case it doesn't matter because my motion vector is a unit vector plus a speed but I'm a little confused that I don't quite get it.

EDIT: Ah! Got it! The result is scaled by length but so is the initial vector. So we divide by that squared!

[ingaborg.livejournal.com]

Oops! Sorry, I didn't read the function through before posting it. I should also have sent the DotProduct function. I'm sure you've already done your own version of this, but just for completeness here it is:

function DotProduct(x_1, y_1, x_2, y_2)
{
// finds the dot product of two vectors
return ((x_1 * x_2) + (y_1 * y_2));
}

[raygungothic.livejournal.com]

Hmm.

Do you really mean both projectile and target are moving with constant velocity? Or am I misinterpreting?

[luckykaa.livejournal.com]

Yes. The two velocities are different but they're straight lines.

[raygungothic.livejournal.com]

Ingaborg beat me to it pretty comprehensively.