Найдите лучшее пересечение двух движущихся объектов

Я хотел бы радикально оптимизировать один из моих алгоритмов, я постараюсь объяснить его как можно лучше.

Субъект

Мы находимся в двумерной евклидовой системе в момент t = 0 . В этой системе есть два объекта:O1 и O2 .

O1 и O2 расположены соответственно в точках PA и PC .

O1 движется с постоянной и известной скоростью в направлении точки PB . Объект остановится, когда достигнет PB.

O2 может двигаться с постоянной и известной скоростью, отличной или отличной от скорости O1 в любом направлении. В момент времени 0 у O2 нет направления , нам нужно будет найти его для него.

Известные параметры:

• O1 :Положение, направление, скорость
• O2 :Положение, скорость

Вот небольшая диаграмма системы.

Мы хотели бы найти точку PI и время ti , для которых:Position of O1 at the time ti = Position of O2 at the time ti = PI. Затем мы заставим объект O2 переместиться в точку PI, чтобы получить направление O2 .

Когда выбрано направление O2 (точка PI )и оба объекта O1 и O2 находятся в движении, объекты никогда не остановятся и не будут ждать друг друга.

В этом случае результат будет примерно таким (PI отмечен буквой D на этой картинке ).

Алгоритм

Рабочий алгоритм, написанный на JS, можно найти по этому jsfiddle , это также отличный способ понять проблему.

В настоящее время я использую простой алгоритм, который работает, но может потребовать много операций, я получу лучшее время пересечения,и получить позицию пересечения впоследствии.

Чтобы получить это время, я проверю положение O1 в данный момент и проверю, может ли O2 перейти в это положение в это время. Если O2 не смог вовремя добраться до объекта, мы увеличим время на 150%, однако, если O2 смог вовремя пересечь линию O1 -B, мы уменьшим время на 50%.

В конце концов, после многих приближений, мы найдем идеальное время, когда оба объекта могут встретиться.

Псевдокод

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

Почему я беспокоюсь?

Мой алгоритм работает, но в некоторых случаях (, например. «Обратный случай» в jsFiddle )потребуется большое количество вычислений, чтобы найти лучшую точку.

В этом jsFiddle мы используем небольшие значения для позиции (-от 1000 до 1000 )и скорости (1 -200 ), но этот алгоритм значительно медленнее с большими числами.

Я знаю, что преждевременная оптимизация — плохая идея, но я нахожусь в конце проекта (, который состоит из вставки/выборки баз данных и анализа данных, включая этот алгоритм, вызываемый много раз )и этот алгоритм в некоторых случаях занимает до 80% системных ресурсов проекта, поэтому улучшение действительно может повысить стабильность и скорость отклика системы.