我一直在努力解决问题,到目前为止还没有找到比天真的更好的解决方案:
给出了根据线性定律移动的N个圆.对于每个圆,我们的初始(在0.0时刻)半径,初始坐标及其半径和坐标在1.0时刻(结束时刻).我们还有k射线,它们的原点坐标和沿光线的矢量.每条射线仅存在于给定时刻t k.我需要能够找到光线与任何圆圈的第一个交点.预期的k数量非常大(数百万或数十亿)以及预期的圆数(数千).我需要更快的解决方案,然后检查所有光线的所有光线
我一直在网上搜索一段时间,但我找不到好的解决办法.即使是对于不移动的圆圈更容易问题的想法也将受到赞赏.
我觉得kd树应该适合静态情况,也许动能kd树将解决更难的问题.我仍然无法弄清楚如何使用kd-tree甚至更容易.