如何找到光线与移动圆的第一个交点

Question

我一直在努力解决问题,到目前为止还没有找到比天真的更好的解决方案:

给出了根据线性定律移动的N个圆.对于每个圆,我们的初始(在0.0时刻)半径,初始坐标及其半径和坐标在1.0时刻(结束时刻).我们还有k射线,它们的原点坐标和沿光线的矢量.每条射线仅存在于给定时刻t _k.我需要能够找到光线与任何圆圈的第一个交点.预期的k数量非常大(数百万或数十亿)以及预期的圆数(数千).我需要更快的解决方案,然后检查所有光线的所有光线

我一直在网上搜索一段时间,但我找不到好的解决办法.即使是对于不移动的圆圈更容易问题的想法也将受到赞赏.

我觉得kd树应该适合静态情况,也许动能kd树将解决更难的问题.我仍然无法弄清楚如何使用kd-tree甚至更容易.

Answer 1

您可以将其视为 3D 静态情况，并以时间作为附加坐标。具有路径的圆变成截锥体并且射线在平面上 time=t _k。如果平截头体的位置不太密集，那么二元空间分区（kd 树，...）会有所帮助。

要找到射线穿过的所有分区，首先找到原点所在的分区，然后按射线方向上的分区邻居遍历（在树中）。这取决于所使用的分区方法。它与光线穿过的分区数量呈线性关系。

更新：最好将平截头体放在它所接触的每个分区中。一个平截头体将分为多个分区。

这是一维加时间的示例。一切都一样，圆有起点和终点以及起点和终点半径。

1  |    E   /
   |   .   /
   |   .  / 
   |  .  /
   |  . /
0  | S /
t/X

X方向分区：

   |    E : /
   |   .  :/
   |   .  : 
   |  .  /:
   |  . / :
   | S /  :
          X

这个梯形将进入两个分区。

按时间方向划分：

   |    E : /
   |   .  :/
   |   .  : 
t-------------------
   |  . / :
   | S /  :
          X

X 左分区中的梯形将进入两个时间分区，而 X 右分区中的梯形将仅进入上分区。

为了实现它，需要计算在某个平面部分上直线和轴平面之间是否有交点，以及如果没有交点则平面的哪一侧是直线。计算在二维情况下是相同的，甚至在更高维度下也是如此。