我想大幅优化我的一个算法,我会尽我所能来解释它。
主题
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在某些情况下项目系统资源的百分比,因此改进可以真正提高系统的稳定性和响应能力。
最佳答案
不失一般性,令 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
,找到拦截点和拦截方向应该很容易。
总而言之,这个问题可以在常数时间内解决,不需要迭代。
关于javascript - 找到两个移动物体的最佳交点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10358022/