14

我想极大地优化我的算法之一,我会尽量用最好的方式来解释它。

主题

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

O1O2分别位于点PAPC处。

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

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

已知参数:

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

这是系统的小图。

系统示意图

我们想找到点PI和时间tiPosition of O1 at the time ti = Position of O2 at the time ti = PI。然后我们将物体 O2 移动到点 PI 以获得O2 的方向

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.

在这种情况下,结果将是这样的(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%在某些情况下项目系统资源,因此改进可以真正提高系统的稳定性和响应能力。

4

4 回答 4

9

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

svO1 的位置和速度向量,O2v2的速度,以及 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

IE

  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(如果方程没有解,那是因为不可能截取)。您可能希望使用最早的未来截取,即 > 0 的较小 t。

一旦你计算了t,找到拦截点和拦截方向应该很容易。

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

于 2012-04-28T00:14:54.407 回答
1

您似乎过度思考了这个问题,它应该只是简单的几何图形。

撇开如何定义最近点的问题不谈,让我们解决所需点位于 和 之间的PA情况PB

我们必须假设整个周期的时间段,我们称之为T.

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

[分别分解 x 和 y 坐标的所有公式]。

有相对简单的公式可以确定点 (PC) 与线 (PA -> PB) 的最近交点,尽管当该线不是无限长时,如何定义是复杂的。

然后你需要:

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

最后两行不依赖于之前的假设——如果你知道拦截点,那么速度就是行进的距离除以所用的时间。

因此,除非您对 V2 施加一些额外的限制,否则总会有一个解决方案,并且它是通过一些简单的数学运算来计算的。

于 2012-04-27T21:40:03.703 回答
1

更新:@Meriton 后来的回答比我的要好。我建议先试试他的。

正如你所意识到的,我们在三个未知数 vx2、vy2 和 t 中具有三个联立方程——分别是 02 的 x 和 y 速度以及时间。不幸的是,这些方程并不都是线性的:

x1o + vx1*t == x2o + vx2*t
y1o + vy1*t == y2o + vy2*t
vx2*vx2 + vy2*vy2 == vy*vy

(这里,x1o、y1o、x2o 和 y2o 是初始位置的坐标。)

如果有办法使问题线性化,我看不到。但是,您可以通过GPS 用来从卫星信号中计算出您的位置的相同Newton-Raphson 技术反复快速地求解。当然,要填写细节并实施这将需要一些工作!

更新:认为@Alnitak 可能已经相当巧妙地线性化了您的问题。因此,也许他的方法和我的方法相结合会成功。(我仍然认为你会想要使用 Newton-Raphson 迭代来收敛 @Altinak's T。)

于 2012-04-27T21:41:19.347 回答
0

由于速度是固定的,这应该可以使用并行导航的思想来解决。这样想吧。在时间 0,O1 和 O2 之间有一条线(LOS,或视线)。如果 O2 遵循最佳相交路径,则在时间 1,O1 和 O2 之间的线将平行于时间 0 LOS。由于您有 O2 的速度,因此您可以计算它在时间 0 和时间 1 之间行进的距离,并由此可以计算出与时间 1 LOS 相交的位置。想象在 O2 的原始位置周围画一个圆,半径等于它在该时间间隔内行进的距离。该圆与第二个 LOS 的交点将包含解决方案。如果没有相交,就没有解。这本在线书籍的开头有一个图表和公式,显示了这个概念:

http://www.crcnetbase.com/doi/abs/10.1201/9781420062281.ch2

这个问题有现实世界的应用程序,你也可以在其中找到这个解决方案。例如,潜艇可以使用它来绘制和保持与目标的拦截航向,方法是在接近目标时保持 LOS 方位对目标的恒定。

编辑:

在此处输入图像描述

这张图显示了我在说什么。除了目标 O1 直接朝向或远离导弹 O2 移动的特殊情况(这可以简单地解决),这可以使用三角函数来解决。

在上图中,我们可以花费一些任意的少量时间。在时间 t1 期间,O1 将经过距离 b,O2 将经过距离 f。t0 时刻 O1 和 O2 之间的线平行于 t1 时刻 O1 和 O2 之间的线。因为我们知道了 O1 和 O2 的初始位置,所以我们知道距离 d,并且因为我们知道了 O1 的方向,所以我们可以简单地计算角度 A。

So given A, b, f, and d, using the law of Cosines,
a = sqrroot(c^2 + b^2 - (2cb * cos(A)))
and
B = arccos((a^2 + c^2 - b^2)/2ac)
Using the law of Sines
E = arcsin((a * sin(B))/f)  or the ambiguous value of 180 - that value
and with that
BC = 180 - E   (because C = 180 - B - E so C+B = 180 - E

有了BC我们就有了解,O1和O2的初始位置和交点的三角形的任何其他方面都可以类似地计算出来。自从我使用高中三角以来已经有很多年了,所以我可能错过了这个简化,但这希望能解释我最初描述的解决方法。

于 2012-04-27T23:08:21.213 回答