我有一堆 3D 点(x、y、z)和一条射线(原点、方向)。我正在寻找最快的方法来找到距射线小于一定距离的所有点。
到目前为止最好的是迭代每个点的 O(n) 算法，但我希望有更好的东西可能使用 Kd 树。尽管不确定如何使用它来查询射线附近的点而不是另一个点。
编辑:如果我将点放入八叉树中，然后仅测试光线相交的八叉树体素中的点，那么速度应该要快得多。但还有更快的方法吗？
最佳答案
首先将您的点“膨胀”为半径等于相关距离的球体。这将您的查询简化为简单的对象射线相交查询——将这些球体放入空间分割结构(八叉树、k-d 树等)中，然后简单地查询它的射线相交。射线相交的球体对应于距射线的距离小于球体半径(即给定距离)的点。
对于空间分割结构，我绝对建议考虑使用 Bounding Volume Hierarchy (BVH) 就像 AABB 树或以球体为叶子的球体树；它们比大多数固定的空间分割结构更加紧凑，并且非常容易实现。然而，任何空间分割方法都应该足够了。
关于algorithm - 找到射线附近所有点的最快方法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59168207/