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

[Gero Putzar]

Preferably to Mike Toews or whoever supplied this wiki page.


Hi,

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:
            param=leaf_data.shape[0]
            distsq = ((leaf_data -
datapoint.reshape((param,1)))**2).sum(axis=0)
            near = numpy.where(distsq<=radsq)
            if len(near[0]):
                idx = leaf_idx[near]
                distsq = distsq[near]
                inside += (zip(distsq, idx))

        else:

            if intersect(left_hrect, radsq, datapoint):
                stack.append(tree[left])

            if intersect(right_hrect, radsq, datapoint):
                stack.append(tree[right])

    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,
Gero.