快速射线交叉口线段容器？(2D)

Question

我有一条射线，我需要找到它碰到的最接近的线段。如果我先对线段进行排序，我认为可以在O(log n)时间内完成，但我不记得如何对它们进行排序.我认为某种类型的树是最好的，但我如何按起点和终点对它们进行排序？如果可能的话，我也希望快速插入到这个数据结构中。

一条射线和一条线段有很多代码，但是我需要一条射线和很多线段对应的代码.我不知道谷歌的条款是什么。

链接到适当的文章是很好的，C++代码甚至更好。谢谢！:)

PS:线段实际上是一个非自交多边形的边缘，按CCW顺序排序.但我认为以不同的方式对它们进行分类可能有一些好处吗？

这都是二维的。

再想一想，我不完全确定这是可能的。某种空间分区可能会有所帮助，但否则，我想不出任何方法来对线条进行排序，以便将它们与任意射线进行比较。

Answer 1

您可以使用多边形的边界框(max x，y坐标)，并在该框内构建一个网格。然后，对于每个细胞，记住跨越细胞的所有线。

找一个像这样的句子：

• 找出射线首先击中的单元格(O(1))
• 使用网格遍历算法在网格中“绘制”一条射线。当您点击非空单元格时，检查它的所有行，检查该单元格内是否有交集，并选择最接近的交点。如果所有交叉点都在单元格之外，请继续(这是O(网格长度))。

您也可以使网格分层(即。四叉树 --一棵你想要的树)，并使用相同的算法行走它。这是在三维光线跟踪中完成的的时间复杂度为O(sqrt(N))。

或者，使用我在射线追踪仪中所做的方法：

• 构建一个包含行的四叉树 (在本文中描述了构建四叉树)--如果节点包含太多的对象，则将它们拆分为4个子节点(子区域)。
• 收集被光线击中的四叉树的所有叶节点： 计算根的射线-矩形相交(不困难)。如果根目录被射线击中，则递归地处理它的子元素。

最酷的一点是，当树节点未被击中时，您已经跳过处理整个子树(可能是一个很大的矩形区域)。

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

这是O(sqrt(N))。

在网格遍历中，当您找到一个交集时，您可以停止搜索。要通过四叉树遍历来实现这一点，您必须按照正确的顺序对子节点进行划分--要么按距离对4个直角交叉口排序，要么聪明地遍历4单元格网(我们将返回遍历)。

这只是一种不同的方法，比较难实现，而且运行良好(我在实际数据上测试了它-O(sqrt(N)。同样，只有在至少有几行的情况下，你才能从这种方法中受益，当多边形有10条边时，与仅仅测试所有这些边相比，我认为好处很小。

Answer 2

你怎么确定你会打到他们中的任何一个？如果是台词，那就不太可能了。

如果它真的是你要测试的多边形(即平面)，通常做这类事情的方法是先与平面相交，然后测试这个点(在2d坐标下)内/外多边形。

也许我误解了你在做什么。

通常，使用复杂图形加速交叉口是通过空间分区来完成的(如果您的测试很昂贵，那么还可以使用类似mailboxing之类的技术)。

更新:我误解了最初的意图，您仍然可以使用(2d)空间分区，但是开销可能不值得。个人测试很便宜，如果你的多个测试不复杂的话，那么走路就更便宜了。很难用描述来形容。

Answer 3

您正在寻找基于scanline/Active边缘表的方法吗？您可以查看维基百科的扫描线绘制条目，也可以在图形宝石目录中搜索算法(主要是C，但也有一些C++代码)。