用于快速射线相交的线段容器？ （二维）
我有一条射线，我需要找到它击中的最近的线段。 我认为如果我首先对线段进行排序，则可以在 O(log n) 时间内完成此操作，但我不记得如何对它们进行排序...我认为某种树效果最好，但我该如何排序他们的起点和终点？ 如果可能的话，我还希望快速插入到这个数据结构中。
有很多关于一根射线与一条线段的代码，但我需要一些关于一根射线与多条线段的代码......我不知道要谷歌搜索什么术语。
合适文章的链接很好，C++ 代码更好。 谢谢！ :)
PS：线段实际上是非自相交多边形的边缘，按 CCW 顺序排序...但我认为以不同的方式对它们进行排序可能有一些优势？
这都是二维的。
再想一想，我并不完全确定这是可能的。 某种空间分区可能会有所帮助，但除此之外，我想不出任何方法对线进行排序，以便它们可以与任意光线进行比较。
I have a ray, I need to find the closest line segment that it hits. I think it's possible to do this in O(log n) time if I sort the line segments first, but I can't remember how to sort them... I think some sort of tree would work best, but how do I sort them by both start and end point? I would also like fast insertions into this data structure if possible.
There's lots of code for one ray vs one line segment, but I need something for one ray vs many line segments... I don't know what terms to google for.
A link to an appropriate article is good, C++ code is even better. Thanks! :)
PS: The line segments are actually the edges of a non-self-intersecting polygon, sorted in CCW order... but I think there may be some advantage to sorting them in a different fashion?
This is all 2D.
On second thought, I'm not entirely sure this is possible. Some sort of spatial partitioning might help, but otherwise, I can't think of any way to sort the lines so that they could be compared with an arbitrary ray.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您可以采用多边形的边界框（最小-最大 x,y 坐标）并在框内构建网格。 然后，对于每个单元格，记住穿过该单元格的所有线。
找到这样的相交：
您还可以使网格分层（即 quadtree - 您是一棵树要求），并使用相同的算法遍历它。 这是在 3D 光线追踪中完成的，时间复杂度为 O(sqrt( N））。
或者，使用我在光线追踪器中所做的方法：
收集该节点的所有叶节点被射线击中的四叉树：
计算根的射线与矩形的交集（不难）。 如果根被射线击中，则递归地处理其子节点。
这样做的一个很酷的事情是，当一个树节点没有被击中时，您就跳过了处理整个子树（可能是一个大的矩形区域）。
最后，这相当于遍历网格 - 您收集光线路径上的最小单元，然后测试其中的所有对象是否相交。 您只需测试所有这些并选择最近的交叉点（这样您就可以探索光线路径上的所有线）。
这是 O(sqrt(N))。
在网格遍历中，当找到交叉点时，就可以停止搜索。 要通过四叉树遍历实现此目的，您必须以正确的顺序搜索子级 - 要么按距离对 4 个矩形交集进行排序，要么巧妙地遍历 4 单元格网格（我们回到遍历）。
这只是一种不同的方法，我认为实施起来相对困难，并且效果很好（我在真实数据上测试了它 - O(sqrt(N))）。 同样，只有当您至少有几条线时，您才会从这种方法中受益，当多边形有 10 条边时，我认为与仅测试所有边相比，好处很小。
You could take a bounding box of the polygon (min-max x,y coordinates) and build a grid inside the box. Then, for each cell, remember all lines that cross the cell.
Find an intesection like this:
You could also make the grid hierarchical (ie. quadtree - a tree you were asking for), and walk it using the same algorithm. This is done in raytracing in 3D and the time complexity is O(sqrt(N)).
Or, use the approach I did in my raytracer:
Collect all leaf nodes of the quadtree that are hit by the ray:
Compute ray-rectangle intersection (not hard) for the root. If the root is hit by the ray, proceed with its children recursively.
The cool thing about this is that when a tree node is not hit, you've skipped processing whole subtree (potentially a large rectangular area).
In the end, this is equivalent to traversing the grid - you collect the smallest cells on the ray's path, and then test all objects in them for intersection. You just have to test all of them and pick the closest intersection (so you explore all lines on ray's path).
This is O(sqrt(N)).
In grid traversal, when you find an intersection, you can stop searching. To achieve this with quadtree traversal, you would have to seach the children in the right order - either sort the 4 rect intersections by distance or cleverly traverse the 4-cell grid (an we are back to traversal).
This is just a different approach, comparatively same difficult to implement I think, and works well (I tested it on real data - O(sqrt(N))). Again, you would only benefit from this approach if you have at least a couple of lines, when the polygon has 10 edges the benefit compared to just testing all of them would be little I think.
您是否正在寻找基于扫描线/活动边缘表的方法？ 您可以查看 Wikipedia 条目 扫描线渲染 或搜索 Graphics Gems 算法目录（主要是 C，但也有一些 C++ 代码） 。
Are you looking for scanline/Active Edge Table based methods? You can take a look at the Wikipedia entry for Scanline Rendering or search the Graphics Gems directory for the algorithms (mostly C, but some C++ code as well).
请记住，排序最多是 O(n log n) 操作。 您最好单独检查每一项。
Keep in mind that sorting is an O(n log n) operation at best. You may be better off just checking each individually.
你怎么确定你会击中他们中的任何一个？ 如果是线，那就不太可能了。
如果您要测试的确实是一个多边形（即平面），则执行此类操作的通常方法是首先与平面相交，然后测试该点（在二维坐标中）的内部/外部多边形。
也许我误解了你实际上在做什么。
一般来说，加速与复杂图形的交叉是通过空间分区来完成的（如果你的测试很昂贵，然后使用邮箱等技术）。
[更新：我误读了初衷]您仍然可以使用（2d）空间分区，但开销可能不值得。 单独的测试很便宜，如果你的多边形不复杂，那么步行可能会更便宜。 从描述上很难说。
How are you certain that you'll hit any of them? If they're lines, it's unlikely.
If it's really a polygon (i.e. planar) that you're trying to test, the usual way to do this sort of thing is intersect with the plane first, then test that point (in the 2d coordinates) for inside/outside polygon.
Maybe I misunderstood what you're actually doing.
In general accelerating intersections with complex figures is done with spatial partitioning (and then techniques like mailboxing, if your tests are expensive).
[Update: I misread the original intent] You can still use (2d) spatial partitioning but the overhead may not be worth it. Individual test are cheap, if your polys aren't complicated it might be cheaper to just walk them. Hard to say from description.
请求澄清，这个说法正确吗？
那么点 (x,y) 不固定？ （可以是任意点、任意方向？）
Ask for clarification, is this correct?
So the point (x,y) is not fix? (It could be any point, and any direction?)