0

I have a 3D point cloud P and a point p, I want to find all points q such that d-eps < ||q-p|| < d+eps, where d and eps are given. What is the most efficient way to do such a search in python ?

Usually I'd use a spherical neighbours query with a KD-Tree however this doesn't seem efficient, especially when d is much bigger than eps

Mateo Vial
  • 658
  • 4
  • 13
  • 1
    If the answer is not satisfying, please prepare an example, ways that you have tried and their resulted runtimes, beside the expected runtime range on that example. Questions on SO must be asked in an answerable form. – Ali_Sh Mar 21 '22 at 09:21
  • The only way other than the naïve method would be to make a triangular mesh of the d-radius sphere such that you could tune the mesh size and search radius to do a first pass using `query_ball_tree` methods to filter the majority of points before doing a final naïve pass. But the effectiveness would depend heavily on the sparsity of the original point field and the ratio of eps/d. (and also finding a useable sphere meshing method, which my quick search does not come up with) – Daniel F Mar 21 '22 at 10:05

1 Answers1

1

There are very useful notes on this topic in my previous issue; I think, You can find your answer there. But in summary, I think cKDTree from Scipy and BallTree from scikit-learn be the best choices, but you can do this by pure NumPy (as it is mentioned in that SO post), too. Seek about R-tree's performance on your data, too (I didn't get better performances by that, but this is recommended somewhere).
Based on my experiences, cKDTree is much faster than KDTree in SciPy. As I pointed in my answer, cKDTree will result in memory leaks and more time consumptions, particularly when searching domain grows up (as here, when you increased d). In this regard, I suggest to use BallTree when d is increased.

Furthermore, my another SO issue and its answer may be helpful in this topic, too.

For further evaluations you must prepare an example, ways that you have tried and their resulted runtimes, beside the expected runtime range on that example. It is better to prepare an example with similar data volume to your main data volume due to the reason that I mentioned above.

Ali_Sh
  • 2,667
  • 3
  • 43
  • 66