javascript - 找到两个移动物体的最佳交点

Question

我想大幅优化我的一个算法，我会尽我所能来解释它。

主题

t = 0 时，我们处于二维欧几里得系统中。在这个系统中有两个对象:O1 和O2。

O1和O2分别位于PA和PC点。

O1 以恒定且已知的速度向点 PB 移动。物体到达 PB 时停止。

O2 可以恒定且已知的速度在任何方向上不同或不 O1。在时间 0，O2 没有方向，我们需要为它找到一个方向。

已知参数:

• O1 : 位置、方向、速度
• O2:位置、速度

这是系统的小图。

我们想找到点 PI 和时间 ti 为: O1 在时间 ti 的位置 = O2 在时间 ti 的位置= 圆周率。然后让物体O2移动到PI点，得到O2方向。

选择O2的方向(Point Pi)并且两个对象O1和O2都在移动时，对象将永远不会停止或等待彼此。

在这种情况下，结果将是这样的(PI 在这张图片上标注为 D)。

算法

你可以在这个 jsfiddle 找到用 JS 编写的工作算法，这也是理解问题的好方法。

此时我使用了一个简单的算法，它可以工作，但是可以进行很多操作，我会得到最佳的交点时间，然后得到交点位置。

为了得到这个时间，我会检查一下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 中的“Reverse Case”)需要大量的微积分才能找到最佳点。

在这个 jsFiddle 中，我们对位置(-1000 到 1000)和速度(1-200)使用了很小的值，但是这个算法使用更大的数字会显着变慢。

我知道过早优化是个坏主意，但我正处于项目的末尾(包括数据库插入/选择和数据分析，包括多次调用该算法)并且该算法最多需要 80在某些情况下项目系统资源的百分比，因此改进可以真正提高系统的稳定性和响应能力。

Answer 1

不失一般性，令 O2 位于 (0,0)。

设 s 和 v 为 O1 的位置和速度矢量，v2 为 O2 的速度，t 为拦截时间。然后我们有:

|s + v * t| = t * v2

根据距离的定义:

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

将其相乘并重新排序得到:

  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

即

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

如您所见，这是一个关于 t 的二次方程。我们可以简单地应用 quadratic formula找到 t 的两个可能值(如果方程无解，那是因为不可能截取)。您可能希望使用最早的 future 拦截，即 > 0 的较小 t。

一旦计算出 t，找到拦截点和拦截方向应该很容易。

总而言之，这个问题可以在常数时间内解决，不需要迭代。