如何检测 N 个不同速度的物体中哪一个会发生碰撞?

计算科学 计算几何
2021-11-24 19:10:42

假设我有 N 架不同的飞机在大小为 400 公里 x 400 公里的二维矩形平面上飞行(即,就好像所有飞机都在同一高度飞行)。假设每架飞机都有一个随机生成的起点和终点。此外,假设飞机可以有不同的速度。我们假设两架飞机如果相距不到 10 公里就会“相撞”。根据这些信息,我如何有效地确定哪对飞机将不可避免地发生碰撞?

更新:据我所知,它需要类似于线段相交算法的东西,但不是一条宽度为零的线,它的厚度为 20 公里。我只是不确定如何将时间动态纳入检测算法。我想我可以在每个(小)时间步使用多边形交点来确定它们是否发生碰撞,但我想看看是否有更有效的方法来检测它,而无需在每个时间步通过成对的多边形交点。

3个回答

在某个时间点,每架飞机都有一个位置和一个速度矢量。对于每架飞机 A,从每架其他飞机 B 中减去其位置和速度矢量。这将其他 B 飞机置于 A 相对坐标系中。

然后对于每架 B 飞机,做一点三角学,看看它的速度矢量是否将它带到距原点 10 的距离内。

将平面的轨迹视为三维中的一条线(x,y,t)段给定的空间xstart,ystart,tstartxend,yend,tend. 为了使计算距离之类的事情有意义,使用与距离相同的单位来测量时间可能很有用,例如,使用恒定速度以公里为单位v的飞机。例如一个时间t=940公里然后相当于t=1小时假设速度v=940公里/小时。

对于每一对平面,计算这个三维空间中的最小欧几里得距离是一个简单的练习。这已经表明平面是否彼此靠近,但这并不是您想要的,因为距离不是空间的,而是时空的。您将不得不做一些工作,看看是否可以将一个转换为另一个。(本质上这是一个计算距离的范数的问题,但这没有用,因为除了欧几里得范数之外,计算两条线之间的距离可能并不方便。)

在这方面可行的另一个想法是将每个平面的“安全区”视为围绕每个平面的时空线的空间半径为 20 公里的圆柱体或管子。然后检测碰撞就变成了一个练习,看看两个这样的圆柱体是否有交叉点。

这是对任意两个平面执行计算的一种方法p1p2, 以速度运动v1v2. 您可以对每一对重复此计算。

减去v1从两个速度,所以现在p1是固定的并且p2正在以速度移动v2v1. 想象一下画线Lp2跟随。你想要最接近的方法L到固定点p1. 这是一个简单的计算,可以按如下方式组织。

分配参数t到点p2(t)L. 然后计算||p1p2(t)||. 最小化这个wrtt. 您将获得以p1那是相切的L.