Nearest k neighbors satisfying conditions (python)

Question

I have a small version of the "find k nearest neighbors" algorithm, which involves rejecting those that do not satisfy a certain condition, and I can’t figure out how to do this effectively.

What I need is to find the nearest neighbors in the current visibility range. Unfortunately, scipy.spatial.cKDTree does not provide the ability to search with a filter for conditionally rejecting points.

The best algorithm I can come up with is a query for n nearest neighbors, and if there is no k in the line of sight, then query it again for 2n nearest neighbors and repeat. Unfortunately, this will mean re-spinning n closest neighbors in the worst cases. The performance degradation is getting worse, the more I have to repeat this request. On the other hand, setting n is too high, potentially wasteful if most of the return points are not needed.

The line of sight changes frequently, so I cannot recalculate cKDTree every time. Any suggestions?

Answer 1

If you are looking for neighbors in line of sight, you cannot use a method such as

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

which allows you to query KDTree for neighbors that are inside a radius of size r around the points of the array x. If I do not understand your question, it seems that the line of sight is known and equivalent to this r value.