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

发布于 2024-12-28 11:02:13 字数 399 浏览 0 评论 0原文

我已经在一个问题上苦苦挣扎了一段时间，到目前为止还没有找到比天真的解决方案更好的解决方案：

给出了 N 个按照线性定律移动的圆圈。对于每个圆，我们都有其初始（时刻 0.0）半径、初始坐标及其半径和时刻 1.0（结束时刻）坐标。我们还有 k 条射线，给出了它们的原点坐标和沿射线的向量。每条射线仅存在于给定时刻 t_k。我需要能够找到射线与任何圆的第一个交点。 k 的预期数量非常大（数百万或数十亿），并且圆的预期数量（数千）。我需要更快的解决方案，然后检查所有圆圈的所有光线。

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

我感觉 kd 树应该适合静态情况，也许动态 kd 树可以解决更难的问题。我仍然不知道如何使用 kd-tree，即使是更简单的一种。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

苏大泽ㄣ 2025-01-04 11:02:13

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

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

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

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

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

X 方向分区：

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

该梯形将进入两个分区。

时间方向分区：

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

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

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

You can look at this as static case in 3D with time as additional coordinate. Circle with path became frustum and ray is in a plane time=t_k. If frustums are not positioned too dense than binary space partitioning (k-d tree, ...) can help.

To find all partitions crossed by ray first find partition where is origin and than traverse (in tree) by partition neighbour in ray direction. It depends on partitioning method used. It is linear in number of partitions crossed by ray.

Update: It is idea to put frustum in each partition it is touching. One frustum will be in more partitions.

This is an example in 1 dimension plus time. Everything is same, circles have starting and ending point and starting and ending radius.

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

Partitioning in X direction:

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

This trapezoid will go in both partitions.

Partitioning in time direction:

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

Trapezoid from X left partition will go in both time partitions, while in X right partition it will go only in upper partition.

To implement it it is needed to calculate is there an intersection between line and axis plane on some plane part and if there is no intersection on which side of a plane is a line. Calculation is same in 2D case, or even in higher dimensions.

回复收藏 0 原文