带方向矢量的点的最近邻居搜索警告

Question

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

非常感谢提前。

Answer 1

考虑使用R * - 树。这种基于矩形的数据结构对于复杂的查询非常适合。

I.e.如果您可以检查一个矩形是否可以包含满足约束条件的点，那么可以使用R * -tree来加速此查询。 ELKI中的索引是可扩展的，所以这可能是一个很好的起点。根据我的理解，您应该能够将其作为ELKI中的距离函数进行表达，如this tutorial in their wiki：如果矩形不能满足约束条件，则返回无限距离。

Answer 2

对我而言，当前公式中的主要问题是角比较是核化的（即需要比较矢量）。如果将每个角度的方向扩展到单独的二维矢量（cos theta，sin theta），那么您应该能够在该空间中进行另一个有限半径的最近邻居搜索（KDTree应该没问题）两个结果集。

Answer 3

你很早以前发布过，但我正在研究类似的问题，并找到了一些答案，所以我会发布并希望它仍然有用。

这在文献中被称为约束最近邻搜索。 This paper在R树上的工作方式上有一个很好的部分，即使这篇论文是关于其他东西的。

您的KD树是一个很好的起点。本文中针对R树的算法也适用于KD树案例。

该论文描述了一种特殊版本的正常最近邻搜索，如下所示。

首先建立一个深度优先的搜索，它将遍历所有包含至少一个满足警告的点的单元格。搜索应该从查询点以增加mindist的顺序访问单元格。 mindist是从查询点到单元中最近点的距离。

现在修改遍历跳过下降到mindist大于最佳点（最接近查询和满足警告）的单元格到目前为止。