nearest-neighbor - 最近邻搜索带有方向向量警告的点

Question

我有一组 3D 点，每个点都与一个方向相关联(例如单位向量)。给定另一个点 + 方向，我想找出集合中最近的点(使用标准 2 范数)，该点也满足方向向量的特定条件(例如，两个方向向量之间的角度在特定角度量内)。到目前为止，我对 3D 点进行了基于 KD 树的范围搜索，然后检查这些点中的任何一个是否符合角度约束，但意识到这是一个高度未优化的 hack。想知道是否有明显更好的方法来做到这一点。

非常感谢。

Answer 1

对我来说，您当前公式中的主要问题是角度比较是核化的(即需要向量之间的比较)。如果将每个角度的方向扩展为单独的 2D 向量(cos theta，sin theta)，那么您应该能够在此空间中以有限的半径进行另一个最近邻搜索(KDTree 应该没问题)并取交集两个结果集。