找到两个移动物体的更好交集 [英] Find the better intersection of two moving objects

问题描述

我想优化dramaticaly我的一个算法，我会尽力解释它是我能做到的最好的方式。

主题

当时 t = 0 时，我们处于2D欧几里德系统。
在这个系统中有两个对象： O1 和 O2 。
$ b

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

O1 以点 PB 的方向以常数和已知速度移动。该物体在到达PB时会停止。

O2 可以常数和速度移动不同的或不是的O1在任何方向。在0时刻，O2有无方向，我们需要为它找到一个。

知道参数：

• O1：位置，方向，速度
  
• O2：位置，速度
  
ul>



以下是系统的一个简图。 b






我们希望找到 PI 和时间点 ti 其中： O1在时间的位置ti =在时间ti = PI 时O2的位置。然后，我们将使物体O2移动到点PI以获得 O2方向。





当O2的方向（点PI）被选中，并且对象O1和O2都在移动中，对象永远不会停止或等待。





在这种情况下，结果会是这样的（PI在这张图上标注为D）。




算法





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



此时我使用了一个简单的算法，可以运行很多操作，我会得到最佳的交叉路口时间，然后得到路口位置。





为了得到这个时间，我会立即检查O1的位置，并检查O2有可能在这个时候去这个位置。如果O2无法及时到达目标，我们会增加150％的时间，但是如果O2可以通过O1-B线时，我们会减少50％的时间。



最终，在很多近似值之后，我们将找到两个对象可以相遇的完美时间。





PseudoCode

 函数getOptimalIntersectionTime时间
如果在'time'时刻O1和O2之间的距离< 1 
返回时间
否则，如果O2在'time'时间到达对象O1 
返回getOptimalIntersectionTime时间* 1.5 
 else 
返回getOptimalIntersectionTime时间* 0.5 
  





为什么要关注？





我的算法但在某些情况下（例如jsFiddle中的Reverse Case），需要大量的微积分才能找到最佳点。



在这个jsFiddle中，我们使用的位置（-1000到1000）和速度（1-200）的值很小，但是这个算法在数字越大时越慢。我知道过早的优化这是一个坏主意，但我处于项目的最后阶段（其中包括数据库插入/选择和数据分析，包括多次调用此算法），并且此算法在某些情况下占用了项目系统资源的80％这样的情况下的改进可以真正提高稳定性和响应能力系统。

解决方案

不失一般性，让O2位于（0,0）。





让O1的位置和速度矢量 s 和 v c> v2 O2的速度，以及截获的时间。然后我们有：



  | 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 
 \\ --- --- / \ ------------ ---------- / \- ------- ------ / 
 \ / \ / \ / 
cba 
  

正如你所看到的，这是一个二次方程。我们可以简单地应用二次公式来查找 t （如果方程式没有解决方案，那是因为没有拦截是可能的）。你可能会想要使用最早的未来拦截，即小于t> 0。



一旦你计算出 t code>，发现拦截点，并且拦截方向应该很容易。总而言之，这个问题可以在恒定的时间内解决，不需要迭代必要的。




I would like to optimize dramaticaly one of my algorithm, i will try to explain it the best way that i can.

The subject

We are in a 2D euclidian system at the time t = 0. In this system there is two object : O1 and O2.

O1 and O2 are respectively situated at the point PA and PC.

O1 moves at a constant and known speed in direction of the point PB. The object will stop when it reach PB.

O2 can move at a constant and known speed different or not of O1's in any direction. At the time 0, O2 has no direction, we will need to find one for it.

The knowns parameters:

• O1 : Position, direction, speed
• O2 : Position, speed

Here is a little diagram of the system.

We would like to find the point PI and the time ti for which : Position of O1 at the time ti = Position of O2 at the time ti = PI. Then we will make the object O2 move to the point PI to get the O2 direction.

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.

In this case, the result would be something like this (PI is noted D on this picture).

The algorithm

You can find the working algorithm written in JS at this jsfiddle, it is also a great way to understand the problem.

At this time i use a simple algorithm who works, but can take a lot of operations, i will get the best intersection time, and get the intersection position afterwards.

To get this time, i will check the position of O1 at a moment, and check if O2 could possibly go to this position at this time. If O2 could not reach the object in time, we will increase the time by 150%, however if O2 could cross the O1-B line at the time, we will decrease the time by 50%.

Eventually, after many approximations, we will find the perfect time where both objects could meet.

PseudoCode

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

Why am I concern ?

My algorithm works, but in some case (e.g. the "Reverse Case" in the jsFiddle) it will take a large amount of calculus to find the best point.

In this jsFiddle, we are using little values for position (-1000 to 1000) and speed (1-200) but this algorithm is dramaticaly slower with bigger numbers.

I know that premature optimization is a bad idea, but I'm at the end of the project (which consists on databases insertions / selection and data analysis, including this algorithm called many many times) and this algorithm take up to 80% of the project system ressources in certain cases so an improvement could really improve the stability and the responsiveness of the system.

解决方案

Without loss of generality, let O2 be located at (0,0).

Let s and v the location and velocity vectors of O1, v2 the speed of O2, and t the time to intercept. We then have:

|s + v * t| = t * v2

By the definition of distance:

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

Multiplying this out and reordering terms gives:

  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

i.e.

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

As you can see, this a quadratic equation in t. We can simply apply the quadratic formula to find the two possible values for t (if the equation has no solution, that's because no interception is possible). You'll probably want to use the earliest future interception, i.e. the smaller t that is > 0.

Once you have computed the t, finding the interception point and from that the interception direction should be easy.

To summarize, this problem can be solved in constant time, no iteration is necessary.

这篇关于找到两个移动物体的更好交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！