[SciPy-User] efficient computation of point cloud nearest neighbors

[Ralf Gommers]

On Sat, May 28, 2011 at 1:13 AM, Christian Jauvin <cjauvin at gmail.com> wrote:

> Hi,
>
> I need to compute the k nearest neighbors of every point in a point
> cloud of at least a million points.
>
> I've been looking at the documentation for the scipy.spatial.KDTree
> and cKDTree classes, but it's not clear to me how I should use their
> query() method (and possibly their distance_upper_bound parameter) to
> optimize the computation.
>
> I've also been looking at the ANN and FLANN C++ libraries, but in both
> cases I've had trouble compiling/installing their Python bindings on
> my Ubuntu system.
>

This is the second issue with ANN bindings reported in a week, so I had a
look at scikits.ann. Then I found http://blog.physionconsulting.com/?p=17.
So it looks like there should be a big "this is deprecated" warning on
scikits.ann. It would be helpful if someone can confirm that KdTree/cKdTree
in scikits.spatial is about as fast as ANN/FLANN.

Thanks,
Ralf


> I'd appreciate some advice as to what would be the ideal strategy to
> solve this problem (either with Scipy or some other package that I
> wouldn't know about).
>
> Thanks in advance,
>
> Christian
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20110529/03fd2dc4/attachment.html>