[SciPy-User] scipy.KDTree.query ball tree

Anne Archibald aarchiba@physics.mcgill...
Tue Oct 12 00:20:13 CDT 2010


> Would it be possible to search the cKDTree with the python
> query_ball_tree? My application could use the efficiency of the
> cKDTree  but I'm not clear how I query distance instead of # of points
> using the existing methods in cKDTree.

Unfortunately, the cKDTree does not support "give me all neighbours
within distance d"; the basic reason is that this must return python
lists, which for some reason I didn't want to include in compiled
code. This should be fixed, but unfortunately I don't have time to add
it right now. (It wouldn't be too hard.)

I should check, though: are you looking to query all neighbours of a
single point (or unstructured list of points), or of a tree? If the
former, what you want is query_ball, not query_ball_tree.

It's still possible to use cKDTree to find all neighbours, though it's
not as efficient as it might be. The first thing to point out is that
the .query method supports an upper limit on the distance. So you can
ask for "up to m neighbours within distance d". An array is still
returned, so that the missing neighbours must be indicated with
infinite distances and invalid indices. But if you were determined,
you could run a query with up to (say) ten neighbours and a fixed
distance, then re-query any points that actually had the full ten
neighbours. Not terribly efficient, but if you have many points still
possibly faster than the python KDTree. Or not. Try the python one
before going to heroic lengths.

Anne


More information about the SciPy-User mailing list