File Exchange

image thumbnail

k-D tree

version (15.4 KB) by Guy Shechter
Perform closest point search or range query using a k-D tree implementation.


Updated 29 Oct 2013

View License

This distribution contains the KDTREE, KDTREEIDX, and KDRANGEQUERY functions.

KDTREE Find closest points using a k-D tree.

CP = KDTREE( REFERENCE, MODEL ) finds the closest points in
REFERENCE for each point in MODEL. The search is performed in an efficient manner by building a k-D tree from the datapoints in REFERENCE, and querying the tree for each datapoint in MODEL.

IDX = KDTREEIDX( REFERENCE, MODEL ) finds the closest points in REFERENCE for each point in MODEL. The search is performed in an efficient manner by building a k-D tree from the datapoints in REFERENCE, and querying the tree for each datapoint in MODEL.

PTS = KDRANGEQUERY( ROOT, QUERYPT, DISTLIM ) finds all the points stored in the k-D tree ROOT that are within DISTLIM units from the QUERYPT. Proximity is quantified using a D-dimensional Euclidean (2-norm) distance.

Two demo scripts are provided (kdtree_demo.m & kdrange_demo.m).

You will need to compile the code in the kdtree/src library using the
MATLAB mex compiler. Place the compiled mex files in the kdtree/lib directory. Finally, add the kdtree/lib directory to your MATLAB path.

** Refer to the README file for more detailed instructions.

Comments and Ratings (58)

Thanks Guy for a very useful set of functions. However, I get random crashes. Would be 5 stars otherwise.


Trying to mex the kd tree files gives me errors on win10 64 matlabR2017:

Error using mex
C:\matlabSandbox\kdtree\src\ In function 'void
mexFunction(int, mxArray**, int, const mxArray**)':
C:\matlabSandbox\kdtree\src\ warning: cast to
pointer from integer of different size [-Wint-to-pointer-cast]
if ( (tree = (Tree *) ((long) pointer_to_tree[0]))== NULL
C:\matlabSandbox\kdtree\src\ error: cast from
'Tree* {aka tree*}' to 'long int' loses precision
pointer_to_tree[0] = (long) tree;

And many more...

Vial Clemence

thanks guy


Jan (view profile)

The compilation of the files worked under R2016b/64, WinSDK7.1, but running the demo let Matlab crash immediately. I guess it could be a conflict with the width of the "unsigned int" and "size_t" in the 64 bit environment.

It would be simpler and safer to use #include "mex.h" instead of letting the user modify the include path manually.

It is a strange idea to display a warning by mexPrintf if a malloc failed. Of course the code will crash immediately by a NULL pointer access soon, so better use a hard mexErrMsgTxt to stop the function.

Magic constants are a bad idea in general. See

min_distance=calcdistance(leaf->pt, pt,D )+0.001;

There is not even a comment why 0.001 is chosen. Perhaps the data are in the range of 1e-10 or 1e+20 and this limit is nonsense.

A standard code indentation will be much nicer. I do not think that a reader can understand what is happening here (spaces replaced by dots, because the ugly display in the FEX comments removes leading spaces):

..if (!LL) {
....if (ReturnType == RETURN_INDEX)
..closest_pt[i] = -1;
..for (j=0; j< D; j++)
....mexPrintf("Null LL\n");

This is not an error, but at least confusing.

The documentation is useful, if you open the M-files manually. Including the \lib path in the Matlab path can lead to errors due to the uppercase "FUNCTION ..." at the beginning of the files. The code crashes and therefore this tool is not usable at least on my computer. I hesitate to give it a 1 star rating, because the submission is nice, well documented and *almost* working - at least I assume this.


gujax (view profile)

Hi Guy,
thanks for the code. I am unable to build mex on Mac. Seems something incompatible with clang++. Anybody solved this for El Capitan?

Mohan Raj

woww it's fatastic

Han Jingwen

i really need this

Lena Veis


Yasin (view profile)

how to download this code


Ahmad (view profile)

I could run this code in my computer, but I can't use this code for my work.
I have a point cloud in 3D space. how can I cluster my points using this code?
thank U


BESMA (view profile)

please the steps to use this code i dont undrestand how to use mex file and how after use kdtree file?? thank you


how to download this code


it's very good

Muhammad Amir

Kuan_Ting Yu, how to your write mex.... instruction in matlab, i get a lot of error when i do like this

Kuan-Ting Yu

I'm using windows 7 64 bit
I was not able to use those dll file
But I use mex command to recompile it, it works.

Some points need to notice:

1. use mex -setup to find your compiler. E.g. VS 2010
2. in "kdtree_common.h", replace #include "c:/.../mex.h" with "mex.h"
3. dir to ./src and mex all .cc file

Kuan-Ting Yu

Andrei Gh.

Andrei Gh.

Very good code.

P.S. Dear Vineet and Tarek,

Just copy the .dll files from the folder kdtree\mex\win directly to the root \kdtree folder.


Tarek (view profile)

me too. I had the same problem
"Attempt to execute SCRIPT kdtree as a function:"
Error in ==> kdtree_demo at 11
[tmp, tmp, TreeRoot] = kdtree( ReferencePts, []);

Im using windows 7 64 bit with Matlab 2011b


thanks for the work.
I am having the same problem of getting an error "Attempt to execute SCRIPT kdtree as a function".
Any idea so that i can implement the code.
---currently using R2010b on windows 7 64 bit.


S R (view profile)

I use the kdtree tools in matlab on a windows XP system, and ran into a problem when processing too large data sets. If I call kdtreeidx with a too large data set, matlab disappears (closes) after being busy for about half an hour. No error message is provided. A sample code that reproduces the problem on my machine:
My machine has 3.46GB of RAM, which I think should be enough to process a million data points? Are there any configuration settings that can increase the processable size for kdtreeidx?

Thanks for your help!

Duy Nguyen

when I used the function kdtrridex to find closest index in 6-D a space, the one of the return value is 0 and the message "NULL LL" show up. I tracked the source code and found that variable "LL" in run_queries function got the value "NULL" but I don't understand the reason. Someone explain for me please


Thanks for your great work on this piece of code.
Since I have changed my operating system to Win7 64 Bit with Matlab R2010a 64 Bit, I'm not able to execute your mex-Files anymore. Would it be possible to provide the mex-files in a 64-Bit-version too?
This could be the reason why some others here mentioned the problem with the error message: "Attempt to execute SCRIPT kdtree as a function".


hello, kdtree.m is a script it includes this command, which i need to use
please tell me how to get this function file of kdtree ,
regards, ghiayas

blue ice

hey ram and where to add this path....tell me plzzzzzzzzz

Ram Lakshmi


I tried to run the demo program and getting the following error.

"??? Attempt to execute SCRIPT kdtree as a function."

Added path first as .. \kdtree\mex\win and then added the ..\Kdtree as path it didn't work and also interchanged the sequence it did not work.

Any help?

blue ice

while running this code i found the following error,any 1 help me in this regard???

??? Error using ==> class
The CLASS function must be called from a class constructor.

Error in ==> kdrange_demo at 13
[tmp, tmp, TreeRoot] = kdtree( ReferencePts, []);

Peter, make sure ..\kdtree\mex\win appears BEFORE ..\kdtree. You can change the order of paths in File->Set Path

Peter Iles

I'm having the same problem as others - when I try to run kdtree I get the "Attempt to execute SCRIPT kdtree as a function" error. Does this have something to do with the Matlab path? Can someone tell me what I need to do here? - Many thanks.


Alok (view profile)

Hi, guys .. could you tell me how to use these files in MATLAB. I am a complete novice in the area.

Nicely written! I would really like to have add point to the tree functionality rather than adding them all at once.

Andrea Tagliasacchi

There is a bug somewhere in the range search. One of my experiments worked fine when I used a random dataset but when I used a customized one (namely, one for which I knew perfectly the structure), returned points were scattered without much meaning.

Since this was buggy and the one released with "fileid:7030" had problems compiling I am building a new "personal" one. I hope to keep the code as simple and easy to understand/edit as possible.

Steven Boege

Thank you, Guy!
You saved me a lot of work!

Users please note that if you tweak the kdrange_demo by putting in a third left-hand-side argument, you will then get the ReferencePts indices of the points in the neighborhood in addition to the coordinates and distance you already were getting. This is useful when trying to find the interstitial spacing of the points within ReferencePts. Getting the index allows you to ignore the case where a point in ReferencePoints is its own nearest neighbor.

Norah .

very good code

Yi Cao

The search is not very efficient. I have compared it against linear search for various size of data. Seems it is only suitable for very small dimension (<5). FEX ID 7030 is better than this one.

Mert Sabuncu

great code!

ramanathan natarajan

Quan Ho

OK! Now I know how to use the kdrangequery to return indexes of nearest rows. It's excellent.

Quan Ho

It could be better if you add kdrangequeryidx that works like kdtreeidx.

Deepak Trivedi

Great job! It's fast.

Samy Samy

I'm sure like me you've searched the web over and over looking for free ringtones only

Marzia De Lucia

I am trying to run kdtree_demo in matlab 7.1 but returns "Attempt to execute SCRIPT kdtree as a function"


Mandar Joshi

great work by author

Anders Wiklund

Easy to use and great support by the author.

Babak Taati

in response to wenchao hu:

> i cannnot run the demo in windows,why?

you need to add the DLL path to your Matlab path. But make sure you do NOT add the path to where the .m files stored to your Matla path.

wenchao hu

i cannnot run the demo in windows,why?

João Ferreira

As James said, a K nearest neighbours search option would be a definive plus. Otherwise, an excelent package --- helped me a great deal on distance range queries!

j p

Xu Chenghua

It seems very good. But i haven't the full code.

A James

Useful but finding the K nearest neighbours rather than just the nearest would be a real improvement.

Ray Hu

Very good. I don't need use my own classic KNN :-(

martin richards

the file kdtree just seems to contain information and no code. is it just me who has found this??

ambrose thompson

Lovely Useful and Fast.

Using it to find nearby points in a scattered set for interpolation

Hong zhou

Very useful program and very kind author. This speed up my programe a lot.
Thanks Guy for your patient and useful help

Steven Knudsen

very easy to implement. All that is needed is an N x d matrix, where d is the dimension of a point in some space, and N is the number of points. Needs a p-nearest neighbor search.

Chris Kelly

Very useful program. I used it to get correspondance between isosurface vertices and matrix subscripts, with great success. Thanks to the author.

Brian Bonnlander

Author was prompt and responsive to enhancement requests and bug reports. Code appears to work efficiently.

Dimitris Nicoloutsopoulos

Very useful. Quite happy, especially with the KDTREEIDX function. This new release (June 2004) includes improvements in memory usage aswell.

Big thanx

Carles Matabosch


More detailed instructions on how to create the mex runtimes.

More detailed instructions on how to create the mex runtimes.

MATLAB Release Compatibility
Created with R2013b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Discover Live Editor

Create scripts with code, output, and formatted text in a single executable document.

Learn About Live Editor