View License

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

» Watch video

Highlights from
k-D tree

4.2 | 32 ratings Rate this file 31 Downloads (last 30 days) File Size: 15.4 KB File ID: #4586 Version: 1.2

k-D tree


Guy Shechter (view profile)


06 Mar 2004 (Updated )

Perform closest point search or range query using a k-D tree implementation.

| Watch this File

File Information

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.


This file inspired Measures Of Analysis Of Time Series Toolkit (Mats), Iterative Closest Point Method, C++, and Kdtree Implementation In Matlab.

MATLAB release MATLAB 8.2 (R2013b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (53)
03 Feb 2017 Mohan Raj

woww it's fatastic

16 Mar 2015 Han Jingwen

i really need this

Comment only
28 Aug 2014 Lena Veis

12 May 2014 Yasin

Yasin (view profile)

how to download this code

Comment only
18 Apr 2014 Ahmad

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

Comment only
28 Oct 2013 BESMA

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

Comment only
27 Mar 2013 jianfeng

how to download this code

27 Mar 2013 jianfeng

it's very good

13 Mar 2012 Muhammad Amir

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

Comment only
29 Feb 2012 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

Comment only
13 Feb 2012 Andrei Gh.

13 Feb 2012 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.

Comment only
29 Jan 2012 Tarek

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

Comment only
20 Dec 2011 dopedmind

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.

Comment only
16 Aug 2011 S R

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!

Comment only
25 Mar 2011 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

Comment only
05 Aug 2010 Sebastian

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

12 Jun 2010 ghiayas

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

Comment only
03 Jun 2010 blue ice

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

Comment only
25 May 2010 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?

Comment only
24 Apr 2010 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, []);

Comment only
07 Jan 2010 Markus Leuthold

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

Comment only
12 Nov 2009 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.

Comment only
16 Oct 2009 Alok

Alok (view profile)

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

Comment only
20 Mar 2009 Cengiz Oztireli

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

16 Sep 2008 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.

11 Sep 2008 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.

08 Aug 2008 Norah .

very good code

25 Mar 2008 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.

18 Jan 2008 Mert Sabuncu

great code!

18 Dec 2007 ramanathan natarajan

14 Mar 2007 Quan Ho

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

14 Mar 2007 Quan Ho

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

24 Nov 2006 Deepak Trivedi

Great job! It's fast.

06 Nov 2006 Samy Samy

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

Comment only
20 Sep 2006 Marzia De Lucia

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


Comment only
26 May 2006 Mandar Joshi

great work by author

05 Dec 2005 Anders Wiklund

Easy to use and great support by the author.

29 Sep 2005 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.

Comment only
17 Sep 2005 wenchao hu

i cannnot run the demo in windows,why?

28 Jul 2005 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!

18 Jul 2005 j p

27 Jun 2005 Xu Chenghua

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

16 Mar 2005 A James

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

30 Dec 2004 Ray Hu

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

03 Dec 2004 martin richards

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

18 Nov 2004 ambrose thompson

Lovely Useful and Fast.

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

09 Nov 2004 Hong zhou

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

09 Nov 2004 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.

26 Sep 2004 Chris Kelly

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

27 Jul 2004 Brian Bonnlander

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

20 Jun 2004 Dimitris Nicoloutsopoulos

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

Big thanx

27 Apr 2004 Carles Matabosch

29 Oct 2013 1.1

More detailed instructions on how to create the mex runtimes.

29 Oct 2013 1.2

More detailed instructions on how to create the mex runtimes.

Contact us