满足条件的最近k个邻居（python）

Question

我对“find k nearest neighbors”算法有一个小小的变化，它涉及到拒绝那些不满足某个条件的算法，我想不出如何有效地做到这一点。在

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

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

视线变化频繁，所以我也不能每次都重新计算cKDTree。有什么建议吗？在

Answer 1

如果你在寻找视线范围内的邻居，就不能用这样的方法

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

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