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 ........
Pramod Vemulapalli (2020). Kdtree implementation in matlab (https://www.mathworks.com/matlabcentral/fileexchange/26649-kdtree-implementation-in-matlab), MATLAB Central File Exchange. Retrieved .
I've corrected the minor bugs below, but there is are still errors with the code. I can't find the last error. The image below shows a heatmap of "closest point", and as you can see there are many defects.
Before using this code, please refer to comments below to correct some minor bugs!
Thank Pramod for posting this out!
Similar to what Bharath pointed out, it should read "right" instead of (isempty(tree_cell(node_number).right)) instead of if (isempty(tree_cell(node_number).left)) on line 110 of kd_rangequery
I think there is a critical error in the submission. Line 66 of the kd_closestpointfast function should read if (isempty(tree_cell(node_number).right)) instead of if (isempty(tree_cell(node_number).left)) ?
in functionn kd_closestpointfast
final_node=node_number; %the value assigned to variable "final_node" might be unused
why is that so?
Why I have this error:
Error using strcmp
Not enough input arguments.
when using my input of 12x12 matrix where the dimension I changed to 144.
Please guide. Thank you.
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);
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)
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.
Just wonder any thoughts on parallelize this implementation if applicable?
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..
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 email@example.com
In addition, kd_nclosestpoints.m needs lots of change in order to use it. Even different type structure.
the same in kd_closestpointfast.m line 66
although this program is good
The same error also occurs on line 80.
There is a bug in file kd_closestpointgood.m on lines 111 and 112
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:
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!
I didn't mean to give a 5/5 as I haven't tried it...
The form froze and it got ranked automatically...
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...
Fixed a bug in the tree generation code ... and made corresponding changes in the other files
Fixed a bug in kd_knn.m , Also wanted to acknowledge the contribution of Steven Michael
Wanted to acknowledge some of the other submissions on the topic