我有一组3D点，每个点都有一个方向（例如单位向量）。给定另一个点和方向，我想找出集合中满足某些方向向量条件（例如两个方向向量之间的角度在一定角度范围内）的最近点（使用标准2-范数）。到目前为止，我对3D点进行了基于KD树的范围搜索，然后检查是否有任何这样的点符合角度约束，但意识到这是一种非常未经优化的方法。想知道是否有更好的方法可以解决这个问题。
提前致谢。
提前致谢。
具有方向向量的点的最近邻搜索注意事项
3
- fred august
2
您能否提供您正在处理的点数大致数量的详细信息？您当前的算法速度快/慢如何？您试图优化什么？速度？内存？代码清晰度？我的第一反应是将其制定为凸优化问题，因为返回到一组点最近点的函数是凸函数，而您的约束似乎是线性的。 - lightalchemist
大约处理8千至15千个点。希望能够针对速度进行优化-内存绝对不是问题。谢谢！ - fred august
3个回答
3
在我看来，你当前公式的主要问题是角度比较被核化了（即需要向量之间的比较）。如果你将每个角度的方向扩展到一个单独的 2D 向量（cos theta，sin theta），那么你应该可以在此空间中使用有限半径进行另一次最近邻搜索（KD树可以胜任），并取两个结果集的交集。
- John Greenall
3
3D方向应该分解为3D向量(cos(phi)*cos(theta), cos(phi)*sin(theta), sin(phi))，对吧？即单位球上的一个点。 - wcochran
@wcochran，您的建议与维基百科 https://en.wikipedia.org/wiki/Spherical_coordinate_system 引用的极坐标->笛卡尔公式略有不同，但仍然可能有效。我的三角/代数太生疏了，无法快速判断它们是否相等。 - John Greenall
从维基百科 - 笛卡尔坐标可以从球坐标（半径r，倾角θ，方位角φ）中获得，其中r = 1，θ ∈ [0，π]，φ ∈ [0，2π)，通过以下公式计算：
x = r cos φ sin θ，y = r sin φ sin θ，z = r cos θ - John Greenall
1
您之前发布了长篇内容，但我正在处理一个类似的问题并找到了一些答案，因此我会发布并希望它仍然有用。
在文献中，这被称为约束最近邻搜索。 这篇论文对其如何在R树上实现有很好的说明，即使该论文是关于其他内容的。
您的KD树是一个很好的起点。该论文中针对R树的算法同样适用于KD树的情况。
该论文描述了一种特殊版本的普通最近邻搜索，具体步骤如下。
首先建立一个深度优先搜索，将遍历所有包含至少一个满足条件的点的单元格。搜索应按照距离查询点最近的单元格的mindist顺序访问单元格。mindist是从查询点到最接近单元格中的点的距离。
现在修改遍历过程，以跳过mindist大于迄今为止找到的最佳点（最接近查询且满足条件）的单元格的降级。
- Gene
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接