找出射线附近所有点的最快方法是什么?

问题描述 投票:2回答:1

我有一堆3D点(x,y,z)和射线(原点,方向)。我正在寻找最快的方法来查找所有距离射线小于一定距离的点。

到目前为止,O(n)算法可以遍历每个点,但是我希望可以使用Kd-tree更好。尽管不确定如何使用它来查询射线附近的点,而不是另一点。

编辑:如果我将点放在八叉树中,然后仅在光线相交的八叉树体素中测试点,那应该要快得多。但是还有更快的方法吗?

algorithm computational-geometry
1个回答
0
投票

首先将您的点“膨胀”到半径等于所讨论距离的球体。这将您的查询简化为简单的对象射线相交查询-将这些球体放入空间细分结构(八叉树,k-d树等)中,并简单地对其进行射线相交查询。射线相交的球体对应于距离球体半径小于球体半径(即给定距离)的点。

对于空间细分结构,我绝对建议您研究使用Bounding Volume Hierarchy(BVH),例如AABB树或以球为叶的球树;它们比大多数固定的空间细分结构要紧凑得多,并且易于实现。但是,任何空间细分方法都足够。

© www.soinside.com 2019 - 2024. All rights reserved.