快速射线相交的线段容器？（2D）

Question

快速射线相交的线段容器？（2D）

4

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

有很多关于一条光线与一条线段的代码，但我需要处理一条光线与多条线段...我不知道要搜索什么词汇。

提供适当文章的链接是好的，C++代码更好。谢谢！ :)

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

所有内容都是2D的。

想了想，我不完全确定这是可能的。某种空间分割可能会有所帮助，但否则，我想不出任何方法来对线段进行排序，以便与任意光线进行比较。

- mpen

5个回答

1

你怎么确定你会撞到它们中的任何一个？如果它们是线，那就不太可能。

如果你真的要测试的是一个多边形（即平面），通常做这种事情的方法是先与平面相交，然后测试该点（在2D坐标系中）是否在多边形内部或外部。

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

一般来说，加速与复杂图形的相交是通过空间分区来完成的（然后使用像邮箱技术这样的技术，如果你的测试很昂贵）。

[更新：我误读了原意] 你仍然可以使用（2D）空间分区，但开销可能不值得。单个测试很便宜，如果你的多边形不复杂，直接遍历它们可能更便宜。从描述很难说。

- simon

我可以保证射线至少会击中一个线段。该射线从顶点向多边形内部投射。（这是2D） - mpen

1

如果你知道射线始终会指向多边形中相同的点，那么你可以按照角度对边进行排序。你的射线也有一个角度，因此可以进行对数时间复杂度的二分搜索。 - Martin Konicek

1

你是否正在寻找基于扫描线/活动边缘表的方法？你可以查看维基百科扫描线渲染的条目，或者在图形宝石目录中搜索算法（大多数是C语言，但也有一些C++代码）。

- dirkgently

乍一看，这似乎只能在多边形/线段按y顺序排序且扫描线严格水平的情况下工作。我的光线可以朝任何方向投射...这可能是一个重大问题。 - mpen

@Mark：如果您能够给我们一个大致的想法，您要做什么（例如多边形填充），那么我们可能能够指出一些专门的算法。 - dirkgently

1

请记住，排序最多是O(n log n)的操作。你最好只是逐个检查。

- rlbond

没问题。我的整个算法最多只能达到O(n^2 log n)，而且我需要投射很多光线... - mpen

排序不是O(N log N)操作。仅使用双元素传递比较进行排序是可以的，但一般情况下并非如此。 - SPWorley

0

请问需要澄清的是这个吗？

您有一组动态线段L。
查询：给定任意点（x，y）和从该点出发的任意射线方向，您想确定L中最接近的线（如果有）？

所以点（x，y）不是固定的吗？（它可以是任何点，任何方向？）

- jacob

没错，Jacob。不过方向是由另一个点给出的，而不是角度，如果相关的话。将有多条射线与同一组线段进行比较，因此我想如果有帮助的话，在这些线上执行一些预处理可能是值得的。 - mpen

也许我应该指出，我们可能只需要处理大约20个线段和平均5条射线，但没有硬性的上限。这需要高效是因为它是递归算法的一部分，而递归算法的成本可能非常高昂。（我的一个实现需要大约一分钟才能处理13行，超过这个范围你甚至不想尝试）。 - mpen

即使使用20行和5条射线的暴力实现也应该只需要几毫秒，为什么你的要花这么长时间？ - jacob

你说得对，它只需要几毫秒，但就像我说的一样，这是一个更大算法的一部分。我投射了几条光线，选择了最佳解决方案，然后将多边形分成两个较小的部分并不断重复...一遍又一遍。 - mpen

我如此关注这个子问题的原因是因为它影响了整个算法的渐近运行时间。 - mpen

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martin Konicek · Accepted Answer

你可以取多边形的边界框（最小-最大x，y坐标）并在框内建立网格。然后，对于每个单元格，记住穿过该单元格的所有线。

像这样找到交点：

- 找出光线首先击中的单元格（O（1）） - 使用{{link1：Grid traversal algorithm}}通过网格“绘制”射线。当您遇到非空单元格时，请检查其所有线条，检查交点是否在单元格内，并选择最近的交点。如果所有交点都在单元格外，则继续（这是O（网格长度））。 - 您也可以使网格分层（即{{link2：quadtree}} - 您要求的树），并使用相同的算法遍历它。 {{link3：这在三维光线追踪中完成}，时间复杂度为O（sqrt（N））。

或者，您可以使用我在光线追踪器中使用的方法：

构建一个包含直线的四叉树（在文章中描述了构建四叉树的方法）- 如果节点（=区域）包含太多对象，则将其分成4个子节点（子区域）
收集被光线击中的四叉树的所有叶节点：

计算根的光线矩形交点（不难）。如果光线击中根，则递归处理其子节点。

这样做的好处是，当树节点未被击中时，您已经跳过了整个子树的处理（潜在的大矩形区域）。

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

这是O(sqrt(N))。

在网格遍历中，当您找到一个交点时，可以停止搜索。要使用四叉树遍历实现这一点，您必须按正确的顺序搜索子节点 - 要么按距离对4个矩形交点进行排序，要么巧妙地遍历4单元格网格（然后我们回到了遍历）。

这只是一种不同的方法，相对来说难度大致相同，而且效果很好（我在真实数据上进行了测试-O(sqrt(N))）。再次强调，仅当您至少有几条线时才能从此方法中受益，当多边形有10个边缘时，与仅测试所有边缘相比，收益会很小。