如何快速找到靠近射线的所有点？

Question

我有一堆三维点（x，y，z）和一条射线（起点，方向）。我正在寻找最快的方法来找到所有距离该射线小于某个距离的点。

目前最好的算法是O(n)，需要遍历每个点，但我希望有更好的方法，也许使用Kd树。虽然不确定如何使用它来查询靠近射线而不是另一个点的点。

编辑：如果我把我的点放在八叉树中，然后仅测试射线相交的八叉树体素中的点，那么速度应该会更快。但还有更快的方法吗？

- nickponline

---

最优数据结构取决于点和查询射线的分布。关于它们，你能说些什么？ - Nico Schertler

你能否在不影响查询复杂度的情况下预处理这些点呢？否则，你将始终需要n次迭代，因为你需要访问每个点。 - Juan Carlos Ramirez

@NicoSchertler 我认为这些点和查询射线是均匀分布的。 - nickponline

@JuanCarlosRamirez 是的！ - nickponline

在这种情况下，我会尝试使用稀疏网格，其中每个单元格的大小等于您查询的“特定距离”。 - Nico Schertler

请注意，如果半径与域的大小相比较小，则网格将会非常巨大。空间和初始化时间可能会成为问题。而且你可能会穿越许多空单元。使用八叉树会更加安全。 - user1196549

Answer 1

首先，将您的点“膨胀”成半径等于所讨论距离的球体。这将把您的查询简化为一个简单的物体-射线相交查询--将这些球体放入空间细分结构（八叉树、k-d树等）中，并对其进行射线相交查询。与射线相交的球体对应于距离该射线小于球体半径（即给定距离）的点。

对于空间细分结构，我强烈建议使用Bounding Volume Hierarchy（BVH），如AABB树或球树，将您的球体作为叶子节点；它们比大多数固定空间细分结构更紧凑，而且很容易实现。但是，任何空间细分方法都应该足够。

- EvilTak

Answer 2

正如@eviltak所说，一组边界球的层次结构可能是一个不错的选择。

球体具有等向性的优点，当您沿着射线方向查看（使用正交投影），树将投影到一组圆盘和另一个圆盘的射线，形成一个二维问题。（当然，您只在需要时执行投影。）

在这种情况下，膨胀点没有真正的好处，因为点在圆内和圆重叠测试没有显着差异。

- user1196549