Calculating point of intersection based on angle and speed

Question

I have a vector consisting of a point, speed and direction. We will call this vector R. And another vector that only consists of a point and a speed. No direction. We will call this one T. Now, what I am trying to do is to find the shortest intersection point of these two vectors. Since T has no direction, this is proving to be difficult. I was able to create a formula that works in CaRMetal but I can not get it working in python. Can someone suggest a more efficient way to solve this problem? Or solve my existing formula for X?

Formula:

Key:

Where o or k is the speed difference between vectors. R.speed / T.speed

Answer 1

My math could be a bit rusty, but try this:

p and q are the position vectors, d and e are the direction vectors. After time t, you want them to be at the same place:

(1) p+t*d = q+t*e

Since you want the direction vector e, write it like this

(2) e = (p-q)/t + d

Now you don't need the time t, which you can calculate using your speed constraint s (otherwise you could just travel to the other point directly):

The direction vector e has to be of the length s, so

(3) e₁² + e₂² = s²

After some equation solving you end up with

(4)

I) a = sum(p-q)/(s²-sum(d²))

II) b = 2*sum(d*(p-q))/(s²-sum(d²))

III) c = -1

IV) a + b*t + c*t² = 0

The sum goes over your vector components (2 in 2d, 3 in 3d)

The last one is a quadratic formula which you should be able to solve on your own ;-)

Answer 2

1. Let's assume that the first point, A, has zero speed. In this case, it should be very simple to find the direction which will give the fastest intersection.
2. Now, A does have a speed. We can force it to have zero speed by deducting it's speed vector from the vector of B. Now we can solve as we did in 1.

Just a rough idea that came to mind...

Some more thoughts:

If A is standing still, then the direction B need to travel in is directly towards A. This gives us the direction in the coordinate system in which A is standing still. Let's call it d.

Now we only need to convert the direction B needs to travel from the coordinate system in which A is still to the coordinate system in which A is moving at the given speed and direction, d2.

This is simply vector addition. d3 = d - d2 We can now find the direction of d3.

And a bit more formal:

A is stationary:

Sb = speed of B, known, scalar

alpha = atan2( a_y-b_y, a_x-b_x )

Vb_x = Sb * cos(alpha)

Vb_y = Sb * sin(alpha)

A moves at speed Sa, direction beta:

Vb_x' = Sb * cos(alpha) + Sa * cos(beta)

Vb_y' = Sb * sin(alpha) + Sa * sin(beta)

alpha' = atan2( Vb_y', Vb_x' )

Haven't tested the above, but it looks reasonable at first glance...

Answer 3

OK, if I understand you right, you have

R = [ xy0, v, r ] T = [ xy1, v ]

If you are concerned about the shortest intersection point, this will be achieved when your positions are identical, and in an Euclidean space this also forces the direction of the second "thing" being perpendicular to the first. You can write down the equations for this and solve them easily.

Answer 4

In nature hunters use the constant bearing decreasing range algorithm to catch prey. I like the explanation of how bats do this link text

We need to define a few more terms.

Point A         - the position associated with vector R.
Point B         - the position associated with vector T.
Vector AB    - the vector from point A to point B
Angle beta  - the angle between vector R and vector AB.
Angle theta - the angle between vector T and vector AB

The formula is usually given as

theta = asin( |R| * sin(beta) / |T| )

where

beta = acos( AB.x*R.x + AB.y*R.y )

You don't want to use this directly, since asin and acos only return angles between -PI/2 to PI/2.

beta  = atan2( R.y, R.x  ) - atan2( AB.y, AB.x )
x        = |R| * sin(beta) / |T|
y        = 1 + sqrt( 1 - x*x )
theta = 2*atan2( y, x )

Of course if x > 1 R is too fast and intersection doesn't exist

EG