How to implement scipy.cKDTree.query_ball_point() using the available methods in pykdtree

[Mechazo11]

Dear authors,

I have been testing pykdtree for some time now and am impressed by its performance for low-dimensional datasets.

However, in the project where I want to include pykdtree, we are needed to search the nearest neighbors of candidate keypoints each of which has a unique radius in which the nearest neighbors must lie.

Previously I was using scipy.cKDTree.query_ball_point() which averaged around 400 - 600ms in execution.

I tried just the .query method on my dataset and saw an impressive average run time of 10ms. However, using a for loop with the .query method is not yielding accurate (or close-enough) results with respect to scipy.cKDTree.query_ball_point(points, radiuses).

My question is, given the suite of methods available in pykdtree, what the steps I need to implement to produce an equivalent function to scipy.cKDTree.query_ball_point(points, radiuses)?

With best,
@Mechazo11

[djhoese]

I am not an expert on the low-level algorithm, but looking at the C code, I think you/we would have to duplicate all the methods to accept an array of radii (distance upper bounds). I think they should be duplicated because we wouldn't want to hurt the performance of the existing single radius version.

So without knowing the details of the algorithm I think replicating and adjusting the arguments and logic to handle an array of radii would be possible. @storpipfugl would probably know best but is pretty busy these days and may not be able to give any advice any time soon. I know that @mraspaud and I are pretty swamped also so it may fall on you to dive into the C (the .mako file) and see what it would take.

[Mechazo11]

@djhoese Thank you very much for your prompt reply. I will take a shot at it and get back to you soon