Find the better intersection of two moving objects

Question

I would like to optimize dramaticaly one of my algorithm, i will try to explain it the best way that i can.

The subject

We are in a 2D euclidian system at the time t = 0. In this system there is two object : O1 and O2.

O1 and O2 are respectively situated at the point PA and PC.

O1 moves at a constant and known speed in direction of the point PB. The object will stop when it reach PB.

O2 can move at a constant and known speed different or not of O1's in any direction. At the time 0, O2 has no direction, we will need to find one for it.

The knowns parameters:

• O1 : Position, direction, speed
• O2 : Position, speed

Here is a little diagram of the system.

We would like to find the point PI and the time ti for which : Position of O1 at the time ti = Position of O2 at the time ti = PI. Then we will make the object O2 move to the point PI to get the O2 direction.

When the direction of O2 (the point PI) is chosen and both objects O1 and O2 are on the move, the objects will never stop or wait for each other.

In this case, the result would be something like this (PI is noted D on this picture).

The algorithm

You can find the working algorithm written in JS at this jsfiddle, it is also a great way to understand the problem.

At this time i use a simple algorithm who works, but can take a lot of operations, i will get the best intersection time, and get the intersection position afterwards.

To get this time, i will check the position of O1 at a moment, and check if O2 could possibly go to this position at this time. If O2 could not reach the object in time, we will increase the time by 150%, however if O2 could cross the O1-B line at the time, we will decrease the time by 50%.

Eventually, after many approximations, we will find the perfect time where both objects could meet.

PseudoCode

function getOptimalIntersectionTime time
   if distance between O1 and O2 at the time `time` < 1
       return time
   else if O2 could not reach the object O1 at the time `time`
       return getOptimalIntersectionTime time * 1.5
   else
       return getOptimalIntersectionTime time * 0.5

Why am I concern ?

My algorithm works, but in some case (e.g. the "Reverse Case" in the jsFiddle) it will take a large amount of calculus to find the best point.

In this jsFiddle, we are using little values for position (-1000 to 1000) and speed (1-200) but this algorithm is dramaticaly slower with bigger numbers.

I know that premature optimization is a bad idea, but I'm at the end of the project (which consists on databases insertions / selection and data analysis, including this algorithm called many many times) and this algorithm take up to 80% of the project system ressources in certain cases so an improvement could really improve the stability and the responsiveness of the system.

Answer 1

Without loss of generality, let O2 be located at (0,0).

Let s and v the location and velocity vectors of O1, v2 the speed of O2, and t the time to intercept. We then have:

|s + v * t| = t * v2

By the definition of distance:

(sx + vx * t) ^ 2 + (sy + vy * t) ^ 2 = (t * v2) ^ 2

Multiplying this out and reordering terms gives:

  sx^ 2 + 2 * sx * vx * t + vx^2 * t^2
+ sy^ 2 + 2 * sy * vy * t + vy^2 * t^2
-                           v2^2 * t^2
= 0

i.e.

  sx^2 + sy^2 + (2 * sx * vx + 2 * sy * vy) * t + (vx^2 + vy^2 - v2^2) * t^2 = 0
  \---   ---/   \------------   ----------/       \--------   ------/
      \ /                    \ /                           \ /
       c                      b                             a

As you can see, this a quadratic equation in t. We can simply apply the quadratic formula to find the two possible values for t (if the equation has no solution, that's because no interception is possible). You'll probably want to use the earliest future interception, i.e. the smaller t that is > 0.

Once you have computed the t, finding the interception point and from that the interception direction should be easy.

To summarize, this problem can be solved in constant time, no iteration is necessary.

Answer 2

You appear to be over-thinking the problem, it should just be simple geometry.

Leaving aside the problem of how you define the nearest point, let's solve for the situation where the desired point is midway between PA and PB.

We have to assume a time period for the entire cycle, let's call that T.

PI = (PB - PA) / 2;  // simplified
TI = T / 2;          // simplified

[decompose all formulae for the x and y coordinates separately].

There are relatively simple formulae for determining the closest intersection of a point (PC) with a line (PA -> PB), although how that's defined is complicated when that line isn't infinitely long.

Then you need:

V1 = (PB - PA) / T;  // O1's velocity
V2 = (PI - PC) / T;  // O2's velocity

These last two lines don't depend on the earlier assumptions - if you know the interception point then the velocity is simply the distance travelled divided by the time taken.

Hence unless you impose some additional constraints on V2, there is always a solution and it's calculated in a few trivial math operations.