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

[Christian Jauvin]

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.

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