找到两个移动物体的更好交点

Question

我想优化我的算法之一,我将尝试以最佳方式解释它.

主题

我们在t = 0时处于2D欧几里得系统中.在这个系统中有两个对象: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移动到点P1以获得O2方向.

当选择O2的方向(点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中的"反向情况"),需要大量的微积分才能找到最佳点.

在这个jsFiddle中,我们使用较小的位置值(-1000到1000)和速度(1-200),但是这个算法在数字较大的情况下显得较慢.

我知道过早优化是一个坏主意,但我在项目的最后(包括数据库插入/选择和数据分析,包括这个算法多次调用),这个算法需要高达80%的项目系统在某些情况下需要资源,因此改进可以真正提高系统的稳定性和响应性.

Answer 1

不失一般性,让O2位于(0,0).

让s和vO1,的位置和速度矢量v2O2的速度,和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中的二次方程.我们可以简单地应用二次公式来找到两个可能的值t(如果方程没有解,那是因为没有拦截是可能的).您可能希望使用最早的未来拦截,即较小的t> 0.

一旦你计算了t,找到拦截点,从那里拦截方向应该很容易.

总而言之,这个问题可以在恒定的时间内解决,不需要迭代.