algorithm - 碰撞检测优化

Question

我正在搜索有关碰撞检测优化的信息。

有一个物体(圆圈)正在从点a 移动到点b。这个物体的半径是r，场内也有很多障碍物(圆)。

我有一个算法(函数)来检查圆和胶囊之间的碰撞，我目前为每个障碍物调用这个函数:

for-each (o : obstacles)
  if collide(o, Capsule(a,b,r))
    return true;

return false;

许多障碍物离运动物体很远，用碰撞检测功能检查时可以忽略。

我的问题是:

是否有解决方案可以忽略检查具有碰撞检测功能的所有障碍物？像最近邻搜索 或KD 树？

编辑:所有障碍物具有相同的半径。

Answer 1

作为第一步，您可以忽略所有不在特定框架/框中的障碍物。

例如所有y-坐标(障碍物形状的y-最低点)大于a和b的最大y坐标+移动物体半径相同距离的所有障碍物都可以忽略。下 y 边界和 x 边界类似。您可以将 similar 进一步分支为两个(或更多)框，而不是一个框。例如，将 a-b 的距离分成两个距离，并对 (a, (b-a)/2),/(b-a)/2, b 中的每一个执行上述过程。

但这完全取决于您将这些值与您的碰撞程序进行比较的效率如何。