Kdtree implementation in matlab

The code contains a kd tree implementation in Matlab

Description

Most of the kdtree code for matlab has been implemented via mex files. I decided to come up with a purely matlab based implementation and so here it is .... The code is obviously expected to be slower than some of the c/c++ implementations that are out there but the fact that its implemented in matlab might make it useful in certain circumstances. Matlab doesnot have pointers and so i mimicked the pointer functionality by using a global cell array. I will appreciate any feedback on my submission ........

Acknowledgements

K D Tree, Kd Tree For Matlab, and Kd Tree Nearest Neighbor And Range Search inspired this file.

• MATLAB release: MATLAB 7.4 (R2007a)

[fzec]

I have some bugs while using the function kd_nclosestpoints. It throws errors about the number of elements that the members of the kdtree struct have. i.e.:

??? Error using ==> gt
Too many input arguments.

Error in ==> kd_nclosestpoints at 21
if(n>tree.numpoints)

I am using R2008a.

This is the same for tree.type, etc..

Thanks.

[gurleen Sohi]

hi..actually i need matlab code for the design of IIR filter low pass filter i.e magnitude and group delay using genetic algorithm in matlab...reply me on my email address [e-mail]

[kale Peng]

In addition, kd_nclosestpoints.m needs lots of change in order to use it. Even different type structure.

[kale Peng]

the same in kd_closestpointfast.m line 66

although this program is good

[Ilia Zveda]

The same error also occurs on line 80.

[Ilia Zveda]

There is a bug in file kd_closestpointgood.m on lines 111 and 112
They are:
if (~isempty(tree_cell_2(node_number).left)) kd_closestpointgood(0,point,tree_cell_2(node_number).right);

Line 111 should instead check right not left:
if (~isempty(tree_cell_2(node_number).right))

[Erik]

Works great.
As you say the other implementations out there makes use of mex files. This being pure m files and with w ell commentated code makes it easy to modify for altered use. I added a stored functionvalue at every node. Works great so far!

Well done!

[Andrea Tagliasacchi]

I didn't mean to give a 5/5 as I haven't tried it...
The form froze and it got ranked automatically...

[Andrea Tagliasacchi]

I haven't tried it but it's a very good idea, so people don't have to compile any source and still achieve some speedup.

I think you should provide comparison in terms of running time though. That will guide the visitors to make the correct choice...