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

[Sturla Molden]

Den 30.05.2011 20:20, skrev Anne Archibald:
> If this is not fast enough, it might be worth trying a two-tree query
> - that is, putting both the query points and the potential neighbours
> in kd-trees. Then there's an algorithm that saves a lot of tree
> traversal by using the spatial structure of the query points. (In this
> case the two trees are even the same.) Such an algorithm is even
> implemented, but unfortunately only in the pure python KDTree. If the
> OP really needs this to be fast, then the best thing to do would
> probably be to port KDTree.query_tree to cython. The algorithm is a
> little messy but not too complicated.

In this case we just need one kd-tree. Instead of starting from the 
root, we begin with the leaf containing the query point and work our way 
downwards. We then find a better branching point from which to start 
than the root. That is not messy at all :-)

Another thing to note is that making the kd-tree is very fast whereas 
searching it is slow. So using multiprocessing is an option.

Sturla