我一直在苦苦挣扎，但到目前为止都没有比朴素方法更好的解决办法：
给定N个圆，它们按线性规律移动。对于每个圆，我们有其初始（在0.0时刻）半径、初始坐标以及在1.0时刻（终止时刻）的半径和坐标。我们还有k条射线，给出其起点坐标和沿射线的向量。每条射线只存在于给定时刻tk。我需要能够找到任何一个圆与射线的第一个交点。预期的k数量非常大（数百万或数十亿），圆的数量也很大（数千个）。我需要比逐个检查所有射线与所有圆更快的解决方案。
我已经在互联网上搜索了一段时间，但没有找到好的解决方案。即使是对于不移动的圆的简单问题的想法也会受到赞赏。
我感觉kd树应该适用于静态情况，也许动态kd树可以解决更难的问题。但我甚至无法想象如何在更简单的情况下使用kd树。
您可以将其视为带有时间附加坐标的三维静态情况。具有路径的圆锥体变成了平截头体，射线在平面时间=tk中。如果截头体位置不太密集，则二进制空间分割（k-d树等）可以提供帮助。
要查找射线穿过的所有分区，首先要找到起点所在的分区，然后按射线方向遍历（在树中）分区的相邻分区。这取决于使用的分区方法。射线穿过的分区数量是线性的。
更新：将截头体放在每个它接触到的分区中是一个好主意。一个截头体会在多个分区中。
这是1维加时间的示例。一切都相同，圆有起始点和结束点以及起始半径和结束半径。
1 | E /
| . /
| . /
| . /
| . /
0 | S /
t/X
X方向的分区：
| E : /
| . :/
| . :
| . /:
| . / :
| S / :
X
这个梯形将会被放置在两个分区中。
按时间方向进行分区：
| E : /
| . :/
| . :
t-------------------
| . / :
| S / :
X
梯形从X左分区将进入两个时间分区，而在X右分区中它只会进入上部分。
要实现这一点，需要计算线和轴平面在某个平面部分是否相交，如果没有相交，则计算线在平面的哪一侧。在2D情况下，或者甚至在更高维度的情况下，计算方式是相同的。