[SciPy-User] Mistake in the scipy-wiki/cookbook/KDTree

Gero Putzar gputzar@beckarndt.com...
Wed Mar 9 22:55:47 CST 2011

Preferably to Mike Toews or whoever supplied this wiki page.


first: Thank you very much for putting this explanatory code into the wiki.

I think there is a minor mistake in the code displayed on
http://www.scipy.org/Cookbook/KDTree in the subsection "Searching a
kd-tree", function radius_search(): Within this function the radius is
supplied as second argument to the function intersect(). But intersect()
expects the square of the radius as argument.

I suggest the following modified version. Note that this modified version
now returns the square distances very much like the corresponding knn_search
function above.

--- snip ---
def radius_search(tree, datapoint, radius):
    """ find all points within radius of datapoint """
    stack = [tree[0]]
    inside = []
    radsq = radius**2
    while stack:

        leaf_idx, leaf_data, left_hrect, \
                  right_hrect, left, right = stack.pop()

        # leaf
        if leaf_idx is not None:
            distsq = ((leaf_data -
            near = numpy.where(distsq<=radsq)
            if len(near[0]):
                idx = leaf_idx[near]
                distsq = distsq[near]
                inside += (zip(distsq, idx))


            if intersect(left_hrect, radsq, datapoint):

            if intersect(right_hrect, radsq, datapoint):

    return inside
--- snap ---

I did not test this modification nor the original code. And I might be wrong
all together, of course.

Please cc directly to me if you want an answer because I'm not subscribed to
the list.

Thanks, kind regards,

More information about the SciPy-User mailing list