algorithm - 如何找到射线与运动圆的第一个交点

我一直在努力解决一个问题，到目前为止，还没有找到一个比幼稚的解决方案更好的解决方案:

给出了根据线性定律运动的N个圆。对于每个圆，我们都有其初始半径(0.0矩)，初始坐标以及半径和1.0矩(终点矩)的坐标。我们还给了k条光线，并给出了它们的原点坐标和沿着该光线的向量。每条射线仅在给定的时刻tk存在。我需要能够找到射线与任何圆圈的第一个交点。 k的预期数量非常大(数百万或数十亿)，并且预期的圈数(千)也很大。我需要更快的解决方案，然后针对所有圈子检查所有光线。

我已经在互联网上搜索了一段时间，但没有找到好的解决方法。甚至对于更简单的圆圈不动的问题的想法也将受到赞赏。

我觉得kd树应该适合静态情况，也许动态kd树可以解决更困难的情况。我仍然不知道如何使用kd-tree甚至更简单。

最佳答案

您可以将其视为3D中的静态情况，并以时间作为附加坐标。带有路径的圆变成了平截头体，射线处于平面时间= tk中。如果视锥的位置不致过于密集，则无法进行二进制空间分区(k-d树，...)。

要查找所有与射线相交的分区，请首先找到分区，该分区的起点是，然后沿射线方向按分区邻居遍历(在树中)。这取决于所使用的分区方法。它与射线交叉的分区数量是线性的。

更新:最好在所有要触摸的分区中放置平截头体。一个截锥体将位于更多的分区中。

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

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

在X方向上分区:

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

该梯形将进入两个分区。

按时间方向划分:

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

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

要实现它，需要计算在某个平面零件上的直线和轴平面之间是否有交点，以及在平面的哪一侧没有直线的交点。在2D情况下，甚至在更高的尺寸下，计算都是相同的。

关于algorithm - 如何找到射线与运动圆的第一个交点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8960089/