mpe*_*pen 4 c++ geometry intersection line-segment
我有一条光线,我需要找到它所触及的最近的线段.如果我先对行段进行排序,我认为可以在O(log n)时间内执行此操作,但我不记得如何对它们进行排序...我认为某种树最适合,但我如何排序它们的起点和终点都是？如果可能的话,我还想快速插入这个数据结构.
一条光线与一条线段有很多代码,但我需要一条光线对比很多线段...我不知道google的条款.
指向相应文章的链接很好,C++代码甚至更好.谢谢!:)
PS:线段实际上是非自相交多边形的边缘,按CCW顺序排序......但我认为以不同的方式对它们进行排序可能有一些优势？
这都是2D.
第二个想法,我不完全确定这是可能的.某种空间分区可能有所帮助,但除此之外,我无法想出任何方式对线进行排序,以便可以将它们与任意射线进行比较.
您可以采用多边形的边界框(min-max x,y坐标)并在框内构建网格.然后,对于每个单元格,记住穿过单元格的所有线条.
找到这样的部分:
您还可以使网格分层(即四叉树 - 您要求的树),并使用相同的算法进行处理.这是在3D光线跟踪中完成的,时间复杂度为O(sqrt(N)).
或者,使用我在光线跟踪器中执行的方法:
收集被光线击中的四叉树的所有叶节点:
计算根的光线矩形交叉(不硬).如果根被光线击中,则递归继续其子节点.
关于这一点很酷的是,当没有命中树节点时,你已经跳过处理整个子树(可能是一个大的矩形区域).
最后,这相当于遍历网格 - 您收集光线路径上的最小单元格,然后测试其中的所有对象以进行交叉.您只需测试所有这些并选择最近的交叉点(因此您可以探索光线路径上的所有线条).
这是O(sqrt(N)).
在网格遍历中,当您找到交叉点时,可以停止搜索.要通过四叉树遍历实现这一目标,您必须以正确的顺序搜索子项 - 按距离对4个矩形交叉点进行排序或巧妙地遍历4格单元格(我们将返回遍历).
这只是一种不同的方法,我认为相对难以实现,并且效果很好(我在实际数据上测试了它 - O(sqrt(N))).再次,如果你至少有几行,你只会受益于这种方法,当多边形有10条边时,与仅仅测试所有这些边相比,我认为很少.
| 归档时间： |
|
| 查看次数： |
4988 次 |
| 最近记录： |