algorithm - 并行查找多个最近的射线段交叉点

Question

我知道如何找到以 2D 兴趣点 (POI) 为根的光线是否与给定的 2D 线段相交，以及如何为给定的光线有效地找到最接近 POI 与多个线段的交点。

但是，我有几个(不是太多)射线 Root 于许多(我的意思是 许多 )POI 和许多(我的意思是 许多 再次)段，我需要找到最接近相应 POI 交叉点的每个射线的段。

这是我对这件事的看法:将光线视为一侧在相应 POI 处而另一侧在正确方向上非常远的线段，然后运行 ​​sweep line algorithm找到所有的交点，然后为每条射线输出最接近 POI 的交点。这应该在 O(N log N) 中运行，因此有点足够好。

然而，这部分恰好是整个系统的瓶颈，我想做得更好，而不是有点足够好。特别是因为真的有许多 要排序的对象 我想让这个算法并行。不幸的是，扫描线算法似乎本质上是顺序的，如果使用它会损害我原本相当并行的系统的整体性能。

因此，问题是:您对上述问题的有效并行化有何建议？

此外，是否有任何已知的高度并行的交叉路口检测算法能够利用 CUDA并行度？

Answer 1

你可以尝试基于 quadtree 做一个算法或其他一些空间索引的二维数据结构。

这是一个想法:

在四叉树的每个叶子中，您存储对与该正方形相交的任何段的引用。首先，您的分辨率为零，即所有段都在边界框节点中，根本没有分割。

然后，对于每条射线，查看射线的原点并分割包含它的节点，直到该节点仅与一个线段相交。如果在分割后节点不与任何线段相交，则跟随光线移动到下一个节点。如果节点与节点内部的线段相交，我们就找到了第一个交点，可以停止沿着这条射线的搜索。如果光线不与节点内的线段相交，我们可以从搜索中修剪该线段，并移动到光线相交的下一个节点。

通过沿每条射线并行执行搜索，该算法显然可以并行运行。仍然会有共享的四叉树，但是当它被分割时，线程很快就不会竞争访问。

运行时间:

运行时间有点难以分析，因为它取决于线段和射线的二维结构。也许有人可以帮助更好地分析运行时间，但这是我最好的镜头:

如果有一个小的距离 d，它小于任意一条射线到最近的非相交线段的距离，并且小于同一条射线上任意两个交点之间的距离，那么我们就可以得到一个上界。然后我们可以称 r=D/d 为问题的“分辨率”，其中 D 是边界框的维度。

运行时间将以 N * r 为界但这是一个非常粗略的界限，因为它基本上假设每条射线都必须沿其整个长度解析为分辨率 d。

让我们试着细化这个界限。

对于任何射线，请考虑其原点与其第一个交点之间的射线截面。对于沿射线那部分的任何点，我们可以询问哪个非相交线段最接近该点。然后我们可以问有多少不同的非相交线段最接近光线的这一部分的某个点。换句话说，如果我们做了一个 Voronoi diagram在不相交的部分中，我们要问的是这部分光线将与多少个单元格相交。如果我们让 p 成为任何射线的这个问题的最大答案，那么我们可以得到一个更好的上限

 N*p*log(r)

通过在沿射线搜索时考虑所需的最大分辨率。

所以如果 p 和 r 是常数，我们就有了一个线性时间算法!

不幸的是，我很确定 p、N 和 r 之间存在某种关系，这会阻止 p 和 r 保持大致恒定。作为粗略的猜测，我会说 r ~ sqrt(N) ，意味着它回到 N log N运行时间。

并行化很有趣。如果我们假设 C 核，我们的搜索运行时间为 N/C*p*log(r) ，但仍然存在划分子树的瓶颈。有log(r)层，每个段最多需要在N个位置划分到这个层，所以需要N/C*log(r)时间，意味着总运行时间将是

(N/C)*p*log(r)

这基本上意味着它是完全可并行的，假设 C < N。

结论
在我看来，作为一个单核算法，这可能不是那么好，但是对于特殊结构和/或并行化的问题，它可能会很好地工作。我不建议尝试实现这个算法，除非你已经考虑了很多，并且你确定可以平滑粗糙的边缘，而且我的分析没有出错。我还建议搜索基于类似概念的已发布算法。