用于快速射线相交的线段容器？（二维）
https://stackoverflow.com/questions/732687
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有一条射线，我需要找到它击中的最近的线段。我认为如果我首先对线段进行排序，则可以在 O(log n) 时间内完成此操作，但我不记得如何对它们进行排序......我认为某种树效果最好，但如何按起点和终点对它们进行排序？如果可能的话，我还希望快速插入到这个数据结构中。
对于一根射线与一条线段有很多代码，但我需要一些针对一根射线与多条线段的代码......我不知道谷歌搜索什么条款。
合适文章的链接很好，C++ 代码更好。谢谢！:)
附：线段实际上是非自相交多边形的边，按 CCW 顺序排序......但我认为以不同的方式对它们进行排序可能有一些优势？
这都是二维的。
再想一想，我不完全确定这一点 是 可能的。某种空间分区可能会有所帮助，但除此之外，我想不出任何方法对线进行排序，以便将它们与任意光线进行比较。
解决方案
您可以采用多边形的边界框（最小-最大 x,y 坐标）并在框内构建网格。然后，对于每个单元格，记住穿过该单元格的所有线。
找到这样的交集：
- 找出射线首先击中哪个单元格 (O(1))
- 使用 网格遍历算法 通过网格“绘制”一条射线。当您点击非空单元格时，检查其所有线条，检查交点是否在单元格内部并选择最近的交点。如果所有交叉点都在单元格之外，则继续（这是 O(网格长度)）。
您还可以使网格分层（即。 四叉树 - 你想要的一棵树），并使用相同的算法遍历它。 这是在 3D 光线追踪中完成的 时间复杂度为O(sqrt(N))。
或者，使用我在光线追踪器中所做的方法：
- 建个 四叉树 包含线（文章中描述了构建四叉树） - 如果节点（=区域）包含太多对象，则将其拆分为 4 个子节点（子区域）
收集所有 叶节点 被射线击中的四叉树的：
计算根的射线-矩形交集（并不难）。如果根被射线击中，则递归地处理其子项。
最酷的事情是当一个树节点 不是 命中，您已经跳过了处理整个子树（可能是一个大的矩形区域）。
最后，这相当于遍历网格 - 您收集光线路径上的最小单元，然后测试其中的所有对象是否相交。您只需测试所有这些并选择最近的交叉点（这样您就可以探索光线路径上的所有线）。
这是 O(sqrt(N))。
在网格遍历中，当找到交叉点时，就可以停止搜索。要通过四叉树遍历实现此目的，您必须以正确的顺序搜索子级 - 要么按距离对 4 个矩形交叉点进行排序，要么巧妙地遍历 4 单元格网格（我们回到遍历）。
这只是一种不同的方法，我认为实施起来相对困难，并且效果很好（我在真实数据上测试了它 - O(sqrt(N))）。同样，只有当您至少有几条线时，您才会从这种方法中受益，当多边形有 10 条边时，我认为与仅测试所有边相比，收益会很小。
其他提示
请的整理是O充其量（N log n）的操作。您可能会关闭只是检查各单独更好。
你怎么肯定你会击中任何人？如果他们是行，这是不太可能的。
如果这真是一个多边形，你想测试（即平面），通常的方式做这样的事情是与平面相交，再测试点（在2D坐标）的内部/外部多边形。
也许我误解你实际上在做什么。
在具有复杂的数字一般加速交点与空间分割完成（然后像mailboxing技术，如果测试是昂贵的）。
[更新：我误读原意]仍然可以使用二维（2D）空间分割但是开销可能不值得的。单独测试也很便宜，如果你的多边形并不复杂也可能更便宜，只是走他们。很难从描述说
请求澄清，这个说法正确吗？
- 您有一组动态线段 L.
- 询问：给定 任何 点 (x,y) 和 和 任何 从该点开始的射线方向，您想要确定最接近的线 L （如果有的话）？
那么点 (x,y) 不固定？（可以是任意点、任意方向？）
