[SciPy-User] scipy.KDTree.query ball tree
Peter Tittmann
works. The documentation says its parameters are:
other : KDTree
The tree containing points to search against
r : positive float
The maximum distance
This is immediately strange to me because it would seem that it needs
a focal point for the search. I understand that this is a search that
references an existing KDTree as opposed to the query_ball_tree. So i
go forth and pass it an existing KDTree:
In [53]: test=spatial.KDTree.query_ball_tree(lasKDTree, 10.)
------------------------------------------------------------
Traceback (most recent call last):
File "<ipython console>", line 1, in <module>
TypeError: query_ball_tree() takes at least 3 arguments (2 given)
It seems that the documentation is missing a parameter. I found an
obscure reference here:
http://article.gmane.org/gmane.comp.python.scientific.user/25517/match=query_ball_tree
that states the the tree should be the second argument. If someone
could help clarify what the first argument should be I'd be grateful.
Thanks!
Peter
_______________________________________________
SciPy-User mailing list
SciPy...@scipy.org
http://mail.scipy.org/mailman/listinfo/scipy-user
josef...@gmail.com
> I'm having some trouble understanding how this query_ball_tree method
> works. The documentation says its parameters are:
>
> other : KDTree
> The tree containing points to search against
> r : positive float
> The maximum distance
>
> This is immediately strange to me because it would seem that it needs
> a focal point for the search. I understand that this is a search that
> references an existing KDTree as opposed to the query_ball_tree. So i
> go forth and pass it an existing KDTree:
>
> In [53]: test=spatial.KDTree.query_ball_tree(lasKDTree, 10.)
> ------------------------------------------------------------
> Traceback (most recent call last):
> File "<ipython console>", line 1, in <module>
> TypeError: query_ball_tree() takes at least 3 arguments (2 given)
since it's a method the first argument should be self, i.e. it should
be called with a KDTree instance and not with the class.
my interpretation.
Josef
Pauli Virtanen
[clip]
> In [53]: test=spatial.KDTree.query_ball_tree(lasKDTree, 10.)
It's an instance method. You should call it as
>>> a = KDTree(points_a)
>>> b = KDTree(points_b)
>>> a.query_ball_tree(b, 10.)
--
Pauli Virtanen
Anne Archibald
In your example you are having two problems. One of them is that the
python error message is confusing; this is a method intended to be
called on an existing kdtree instance, and you are calling it
directly. Some languages simply do not allow this, but python does, so
instead you get the strange "missing argument" message; this occurs
because if you don't call it on an instance, you need to supply an
instance as the normally-invisible "self" argument.
The basic problem you're having, though, is that this method is used
for a "two-tree" query: you use it when you have two kd-trees and you
want to find all the points of one that are near each point of the
other. Think of it as if query_ball were being supplied many points,
but instead of an array you're supplying them stored in a kd-tree. The
reason this exists is that there are some algorithmic shortcuts you
can take when both sets of points are stored in spatial data
structures. But unless you know you want this, this is probably not
the function you want to be using.
In fact, this is probably not just the wrong function but the wrong
kd-tree implementation; the compiled one, available as cKDTree, is
faster in almost every way; the python implementation is there because
it's more flexible (so that for example you could implement your own
algorithms that walk the trees).
Anne
Peter Tittmann
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.
gratefully,
Anne Archibald
> 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