c++ - 用于快速射线相交的线段容器？ (二维)

Question

我有一条射线，我需要找到它命中的最近线段。我认为如果我先对线段进行排序，可以在 O(log n) 时间内完成此操作，但我不记得如何对它们进行排序......我认为某种树最有效，但我该如何排序他们的起点和终点？如果可能的话，我还想快速插入到这个数据结构中。

一条射线与一条线段有很多代​​码，但我需要一些关于一条射线与多条线段的代码...我不知道要用谷歌搜索什么术语。

适当文章的链接很好，C++ 代码更好。谢谢! :)

PS:线段实际上是非自相交多边形的边，按 CCW 顺序排序...但我认为以不同的方式排序它们可能有一些优势？

这都是二维的。

---

再三考虑，我不完全确定这是否可能。某种空间划分可能会有所帮助，但除此之外，我想不出任何方法来对线进行排序，以便将它们与任意射线进行比较。

Answer 1

您可以采用多边形的边界框(最小-最大 x,y 坐标)并在框内构建网格。然后，对于每个单元格，记住穿过该单元格的所有线。

找到这样的交叉点:

• 找出射线首先击中哪个细胞 (O(1))
• 使用Grid traversal algorithm通过网格“绘制”一条射线。当您点击非空单元格时，检查其所有行，检查交叉点是否在单元格内并选择最近的交叉点。如果所有交点都在单元格外，则继续(这是 O(grid length))。

您还可以使网格分层(即 quadtree - 您要求的树)，并使用相同的算法遍历它。 This is done in raytracing in 3D时间复杂度为O(sqrt(N))。

---

或者，使用我在光线追踪器中所做的方法:

• 构建一个 quadtree包含线(文章中描述了构建四叉树)- 如果节点(=区域)包含太多对象，则将它们拆分为 4 个子节点(子区域)

• 收集四叉树中被射线击中的所有叶节点:

  计算根的射线-矩形交点(不难)。如果根被光线击中，则递归地处理它的子节点。

这很酷的一点是，当一个树节点没有被命中时，您就跳过了处理整个子树(可能是一个大的矩形区域)。

最后，这相当于遍历网格 - 您收集光线路径上的最小单元格，然后测试其中的所有对象是否相交。您只需测试所有这些并选择最近的交点(这样您就可以探索射线路径上的所有线)。

这是 O(sqrt(N))。

在网格遍历中，当找到路口时，可以停止搜索。要通过四叉树遍历实现此目的，您必须以正确的顺序搜索子项 - 按距离对 4 个矩形交叉点排序或巧妙地遍历 4 单元网格(我们回到遍历)。

这只是一种不同的方法，我认为实现起来比较困难，而且效果很好(我在真实数据上测试过 - O(sqrt(N)))。同样，如果您至少有几条线，您将只能从这种方法中受益，我认为当多边形有 10 条边时，与仅测试所有边相比，好处微乎其微。