3

想象一下，我们有一个 2D 天空（10000x10000坐标）。在这个天空的任何地方，我们都可以拥有一架飞机，根据它的位置来识别(x, y)。任何飞机都可以开始移动到另一个坐标（直线）。

有一个组件可以管理所有这些定位和运动。当飞机想要移动时，它会以(start_pos, speed, end_pos). 我如何在组件中判断一架飞机何时会在另一架飞机的视线内移动（每架飞机都将其作为视线半径的属性）以通知它。请注意，许多飞机可以同时移动。此外，该算法非常有效，因为它可以处理约 1000 个平面。

如果有一些限制，那就是限制您的解决方案 - 它可能会被删除。问题没有解决。

4

5 回答 5

3
  • 使用一条线来表示飞行路径。
  • 将每条线转换为包围它的矩形。矩形的宽度由您对“接近”的定义决定（安全距离越大，矩形应该越宽）。
  • 对于每个新的飞行计划：
    • 检查新矩形是否与另一个矩形相交。
      • 如果是这样，计算每架飞机何时到达碰撞点。如果时间差太小（根据场景定义太小），拒绝新的飞行计划。
于 2010-12-08T11:04:12.503 回答
3

如果你想处理时间方面（即处理飞机移动的事实），那么我认为潜在的简化是通过时间维度解决问题（增加一个维度 - 因此，原始问题是 2D，成为 3D 问题）。

然后，问题变成了找到一条线与（倾斜的）圆柱体相交的点的问题。找到所有可能的交叉点将是 n^2；不太确定这是否足够有效。

于 2010-12-08T11:18:59.057 回答
2

请参阅Wikipedia:Quadtree，了解一种数据结构，可以轻松找到哪些飞机靠近给定飞机。它将使您免于进行 O(N^2) 测试来进行接近性测试。

于 2010-12-08T11:19:33.173 回答
1

你有很好的答案，我只会评论一个方面，可能不正确

  • 你说你的飞机以形式移动（start_pos，speed，end_pos）
  • 如果所有飞机都有这样的，让我们称之为飞行计划，那么你应该能够直接计算它们何时何地彼此相距一定距离，或者它们何时会在彼此最近的点，或者是否会发生碰撞/得到太近了

因此，如果它们确实按照飞行计划移动并且不偏离它们，那么您的问题就是确定性的 - 它归结为求解一组方程，对于大约 1000 架飞机来说，这并不是一项艰巨的任务。

如果您确实需要更快地求解这些方程，您可以使用其他答案中描述的技术

  • 使用可以加速计算距离的有效结构（四叉树、八叉树、kd树），
  • 仅针对某些相关的未来时间片拆分问题以求解方程
  • 优先求解距离变化最快的对的方程

当然，将时间转换为三维会将飞机从点变成线，最终您会搜索两条 3d 线之间最近的点（这里有一些数学）

于 2010-12-08T11:52:17.127 回答
-1

我实际上找到了这个问题的答案。

它在《实时碰撞检测》一书中，p。223. 最好将其命名为：Intersecting Moving Sphere Against Sphere，其中 2D 球体是一个圆。在这里解释不是那么简单（而且我可能也侵犯了某些权利），但基本思想是将其中一个圆固定为一个点，将其半径添加到移动圆的半径上。移动的新方向是两个原始向量的和。

于 2011-02-26T19:14:07.267 回答