Search neighboring points using k-d trees
Question: I have a bunch of coordinates contained in three `numpy` arrays: `xarr`,
`yarr` and `zarr` (corresponding positions in each array belong to the same
point - i.e the first point is at `xarr[0]`, `yarr[0]`, `zarr[0]`). Given
another point in space at `P(x,y,z)` I would like to find all the points that
are within a distance _r_ of `P(x,y,z)`.

My current (and very inefficient) method of doing this is to simply iterate
through and calculate the distance to each point and see if it is within _r_
of `P(x,y,z)`.

However, I'd like to use SciPy's k-d tree algorithm to do this, but I'm not
really sure how to start implementing it (I'm very new to Python). I'd really
appreciate it if someone could briefly outline some code that demonstrates
_how to set up_ a k-d tree given data in the format I've got.

I know of [SciPy documentation of its k-d tree
implementation](http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.html#scipy.spatial.KDTree),
I've looked over it but I'm still confused on how to create the tree given the
data in the format I have (`np.mgrid` and `ravel()` were called and I don't
quite understand why).

Thanks!


Answer: Here's an explanation of the example provided in the scipy docs :

    
    
    from scipy import spatial
    x, y = np.mgrid[0:4, 0:4] 
    

`np.mgrid` creates a mesh grid x,y from 0 to 4. Since you already have your
x,y,z coordinates, you are going to skip this step.

    
    
    points = zip(x.ravel(), y.ravel())
    points = zip(xarr.ravel(), yarr.ravel(), zarr.ravel()) #in your case
    points = zip(xarr, yarr, zarr) # if x,y,z are already 1-d
    

`zip` creates a list of tuples containing each x,y point pair (associate
together the coordinates for each point). `ravel` flattens the x, y mesh grid
(converts a n-d array to 1-d) so that `zip` can be used. In your case you will
only use `ravel` if `xarr`, `yarr`, `zarr` are not already 1-d.

    
    
    tree = spatial.KDTree(points)
    

Create index the points to provide rapid neighbour look up.

    
    
    tree.query_ball_point([2, 0], 1)
    

Look up points within `r=1` of the point `[2,0]`

Hope this helps.

