我有一条射线，我需要找到它击中的最近的线段。如果我首先对线段进行排序，我认为可以在 O(log n) 时间内完成此操作，但我不记得如何对它们进行排序......我认为某种树会工作得最好，但我该如何排序他们的起点和终点？如果可能的话，我还想快速插入这个数据结构。
一条射线与一条线段有很多代码，但我需要一条射线与许多线段的代码……我不知道谷歌的术语是什么。
适当文章的链接很好，C++ 代码更好。谢谢！:)
PS：线段实际上是非自相交多边形的边缘，按逆时针顺序排序......但我认为以不同的方式对它们进行排序可能会有一些优势？
这都是二维的。
再三考虑，我不完全确定这是可能的。某种空间分区可能会有所帮助，但除此之外，我想不出任何方法来对线条进行排序，以便将它们与任意光线进行比较。
您可以获取多边形的边界框（最小-最大 x,y 坐标）并在框内构建一个网格。然后，对于每个单元格，记住所有穿过单元格的线。
找到这样的交叉点：
您还可以使网格分层（即四叉树-您要求的树），并使用相同的算法对其进行遍历。这是在 3D 光线追踪中完成的，时间复杂度为 O(sqrt(N))。
或者，使用我在光线追踪器中使用的方法：
收集被射线击中的四叉树的所有叶节点：
计算根的射线-矩形交点（不难）。如果根被射线击中，则递归地处理其子项。
很酷的一点是，当一个树节点没有被命中时，你就跳过了处理整个子树（可能是一个大的矩形区域）。
最后，这相当于遍历网格——收集光线路径上最小的单元，然后测试其中的所有对象是否相交。您只需要测试所有这些并选择最近的交叉点（这样您就可以探索光线路径上的所有线）。
这是 O(sqrt(N))。
在网格遍历中，当你找到一个交叉点时，你可以停止搜索。要通过四叉树遍历来实现这一点，您必须以正确的顺序搜索孩子 - 要么按距离对 4 个矩形交叉点进行排序，要么巧妙地遍历 4 单元格网格（我们回到遍历）。
这只是一种不同的方法，我认为实施起来相对困难，并且效果很好（我在真实数据上对其进行了测试 - O(sqrt(N))）。同样，如果您至少有几条线，您只会从这种方法中受益，当多边形有 10 条边时，与仅测试所有边相比，我认为优势很小。
你怎么确定你会击中他们中的任何一个？如果它们是线条，则不太可能。
如果它确实是您要测试的多边形（即平面），则执行此类操作的通常方法是首先与平面相交，然后测试该点（在 2d 坐标中）的内部/外部多边形。
也许我误解了你实际上在做什么。
一般来说，加速与复杂图形的交叉点是通过空间分区来完成的（如果你的测试很昂贵，那么可以使用邮箱等技术）。
[更新：我误读了原意]您仍然可以使用（2d）空间分区，但开销可能不值得。个人测试很便宜，如果您的多边形不复杂，那么步行可能会更便宜。从描述很难说。
您是否正在寻找基于扫描线/活动边缘表的方法？您可以查看扫描线渲染的 Wikipedia 条目或在Graphics Gems目录中搜索算法（主要是 C，但也有一些 C++ 代码）。
请记住，排序最多是一个 O(n log n) 操作。您最好单独检查每个。
要求澄清，这是正确的吗？
所以点 (x,y) 不固定？（它可以是任何一点，任何方向？）