python - 满足条件的最近 k 个邻居(python)

Question

我对“找到 k 个最近的邻居” 算法有一个轻微的变体，它涉及拒绝那些不满足特定条件的算法，我想不出如何有效地做到这一点。

我要做的是找到当前视线内的 k 个最近的邻居。不幸的是，scipy.spatial.cKDTree 没有提供使用过滤器进行搜索以有条件地拒绝点的选项。

我能想到的最佳算法是查询 n 个最近的邻居，如果视线中没有 k 个，则再次查询 2n 个最近的邻居并重复。不幸的是，这将意味着在最坏的情况下反复重新计算 n 个最近的邻居。我必须重复此查询的次数越多，性能损失就越严重。另一方面，如果不需要返回的大部分点，则将 n 设置得太高可能会造成浪费。

视线经常变化，所以我也无法每次都重新计算 cKDTree。有什么建议么？

Answer 1

如果你正在寻找视线内的邻居，不能使用像

这样的方法

cKDTree.query_ball_point(self, x, r, p, eps)

它允许您查询 KDTree 中 x 数组点周围 r 大小半径内的邻居。除非我误解了你的问题，否则视线似乎是已知的并且相当于这个 r 值。