View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Kdtree implementation in matlab

4.8 | 5 ratings Rate this file 32 Downloads (last 30 days) File Size: 59.4 KB File ID: #26649 Version: 1.4
image thumbnail

Kdtree implementation in matlab



11 Feb 2010 (Updated )

The code contains a kd tree implementation in Matlab

| Watch this File

File Information

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 ........


K D Tree, Ataiya/Kdtree, and Kd Tree Nearest Neighbor And Range Search inspired this file.

MATLAB release MATLAB 7.4 (R2007a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (13)
04 Jan 2016 JR

JR (view profile)

There seem to be some issues with the closestpointgood function. The following code shows that the distance according to this function is 0.0662 which is twice as much as the coordinates of another node: 0.0386.

X = 0.1321;
Y = 0.9393;
[index_vals,vector_vals,final_node] = kd_closestpointgood(tree,[X Y]);

X(2,1) = tree(final_node).nodevector(1,1);
Y(2,1) = tree(final_node).nodevector(1,2);

%nearest node:
a = 0.1582 - X(1,1);
b = 0.9677 - Y(1,1);
c = sqrt(a^2+b^2)

%nearest node according to kd_closestpoint
a = X(1,1) - X(2,1);
b = Y(1,1) - Y(2,1);

c = sqrt(a^2+b^2)

Comment only
03 Feb 2014 kenza

kenza (view profile)

thank you for all kd codes. So, i have one question. I want use kd_knn for each 3D point of matrix (X). I built kd tree for matrix (X) and i want to find knn for each point of this matrix. In kd_knn code i can use only one point. Thank you for you help and suggestions.

18 Jul 2013 Baoqiang Cao

Just wonder any thoughts on parallelize this implementation if applicable?

Comment only
13 Jun 2013 David Navega

05 Nov 2011 fzec

fzec (view profile)

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

I am using R2008a.

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


Comment only
14 May 2011 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

Comment only
04 Oct 2010 C. Peng

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

Comment only
03 Oct 2010 C. Peng

the same in kd_closestpointfast.m line 66

although this program is good

22 Jun 2010 Ilia Zveda

The same error also occurs on line 80.

Comment only
22 Jun 2010 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))

Comment only
11 Apr 2010 Erik

Erik (view profile)

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!

12 Feb 2010 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...

Comment only
12 Feb 2010 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...

12 Feb 2010 1.1

Wanted to acknowledge some of the other submissions on the topic

12 Feb 2010 1.2

Fixed a bug in kd_knn.m , Also wanted to acknowledge the contribution of Steven Michael

17 Feb 2010 1.4

Fixed a bug in the tree generation code ... and made corresponding changes in the other files

Contact us