如何找到一个光线与运动界第一个路口 [英] How to find first intersection of a ray with moving circles

问题描述

我一直在挣扎着一个问题了一会儿，到目前为止还没有找到任何解决办法更好的那么天真之一：

I have been struggling with a problem for a while and so far have not found any solution better then the naive one:

n周期给出一个按照线性规律移动。对于每一个圆圈，我们有它的初始（在时刻0.0）半径，初始坐标，半径和协调，在那一刻1.0（结束时刻）。我们也有自己的原点坐标和沿射线的矢量给出ķ射线。每条射线只存在于某一t时刻<子> K 。我需要能够找到一丝的第一个十字路口与任何圈子。 k的预期数量是相当大的（千万甚至上亿），以及圆（千）的预期数量。我需要的解决方案的速度，然后检查所有的光线对各界。

N circles are given that are moving according to a linear law. For each of the circles we have its initial (at moment 0.0) radius, initial coordinates and its radius and coordinates at moment 1.0 (end moment). We also have k rays given with coordinates of their origin and a vector along the ray. Each ray only exists at a given moment t_k. I need to be able to find the first intersection of a ray with any of the circles. The expected number of k is quite large (millions or billions) as well as the expected number of circles (thousands). I need solution faster then checking all rays against all circles.

我一直在寻找一轮互联网有一段时间了，但是我发现没有什么好办法的办法。即使一个想法的圈子不动将是AP preciated的简单的问题。

I have been searching round the internet for some time but I have found no good solution approach. Even an idea for the easier problem of the circles not moving will be appreciated.

我的感觉是一个kd树应为静态情况下是合适的，也许动能kd树将解决困难之一。我仍然无法弄清楚如何使用kd树，即使是比较容易的。

I have the feeling that a kd-tree should be appropriate for the static case and maybe a kinetic kd-tree will solve the harder one. Still I cannot figure out how to use kd-tree even for the easier one.

推荐答案

您可以看一下这是静态的情况下，在3D与时间作为附加坐标。圆与路径成为视锥和光线是在一个平面上的时间= T <子> K 。如果视锥没有定位不是二进制空间分割过于密集（kd树，...）可以提供帮助。

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

分区X方向：

Partitioning in X direction:

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

这梯形会在这两个分区。

This trapezoid will go in both partitions.

分区在时间方向：

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

这是X左分区梯形会在这两个时间分区，而在X右分区将在分区上只走了。

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

要实现它需要它来计算是有一些平面部分线和轴平面之间的交叉点，如果没有交集在其上的平面的一侧是一条线。计算方法是相同的2D情况下，甚至是在更高的层面。

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.

这篇关于如何找到一个光线与运动界第一个路口的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！