检测2d平面中2个移动物体何时接近

想象一下，我们有一个2D天空（10000x10000坐标）。在这片天空的任何地方，我们都可以拥有一架飞机，由它的位置(x, y)确定。任何飞机都可以开始移动到另一个坐标（直线）。有一个组件可以管理所有这些定位和移动。当飞机想要移动时，它会以(start_pos, speed, end_pos)的形式发送消息。我怎样才能告诉组件，当一架飞机在另一架飞机的视线内移动时（每架飞机将其视为视线范围内的属性）以便通知它。请注意，许多飞机可以同时移动。此外，这种算法很有效，它可以处理~1000架飞机。如果存在一些限制，这限制了您的解决方案 - 它可能会被删除。问题没有解决。

已邀请:

5 个回复

吞睫素

用一条线来表示飞行路径。将每一行转换为包含它的矩形。矩形的宽度由“close”的定义决定（安全距离越大，矩形应该越宽）。对于每个新的飞行计划：检查新矩形是否与另一个矩形相交。如果是，则计算每个平面何时到达碰撞点。如果时差太小（根据场景你应该定义得太小），拒绝新的飞行计划。

诞胃

如果你想处理时间方面（即处理飞机移动的事实），那么我认为可能的简化是通过时间维度解决问题（增加一个维度 - 因此，原始问题是2D，成为3D问题）。然后，问题变成找到线与（倾斜）圆柱相交的点。找到所有可能的交叉点将是n ^ 2;不太确定这是否足够有效。

嫩昧竞莫

请参阅维基百科：四叉树的数据结构，可以轻松找到哪架飞机靠近给定的飞机。它将使您免于进行O（N ^ 2）测试以获得贴近度。

犀寺扦

你有很好的答案，我只会评论一个方面，可能不正确你说你的飞机在形式上移动（start_pos，speed，end_pos）如果所有的飞机都有这样的，让我们称它们为飞行计划，那么你应该能够直接计算它们在彼此之间和距离之间的距离，或者它们何时会在彼此最近的点或者如果碰撞/得到它们太近了因此，如果他们确实根据飞行计划移动并且不偏离它们，那么你的问题就是确定性的 - 它归结为解决一组方程式，这对于~1000个平面来说并不是一项大任务。如果您确实需要更快地解决这些方程式，您可以使用其他答案中描述的技术使用可以加速计算距离的高效结构（四叉树，八叉树，kd树），将问题分解为仅针对某些相关的未来时间片求解方程优先求解距离变化最快的对的方程当然，将时间转换为第三维会将飞机从点变为线，最终您将搜索两条三维线之间的最近点（这里是一些数学运算）

马口

我实际上找到了这个问题的答案。它出现在书中的Real-Time Collision Detection，p。 223.它也更好地命名：将球体与球体相交，其中2D球体是圆形。这里解释它并不是那么简单（我也可能违反某些权利），但基本思路是将其中一个圆作为一个点，将其半径加到移动半径的半径上。移动的新方向是两个原始向量的总和。

要回复问题请先登录或注册

检测2d平面中2个移动物体何时接近

5 个回复

发起人

plane

问题状态

检测2d平面中2个移动物体何时接近

与内容相关的链接

5 个回复

发起人

plane

问题状态