Code covered by the BSD License  

Highlights from
k-D tree

4.58621

4.6 | 31 ratings Rate this file 53 Downloads (last 30 days) File Size: 15.4 KB File ID: #4586

k-D tree

by

 

06 Mar 2004 (Updated )

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

| Watch this File

File Information
Description

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.

Acknowledgements

This file inspired Measures Of Analysis Of Time Series Toolkit (Mats), Kd Tree For Matlab, 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 (51)
28 Aug 2014 Lena Veis  
12 May 2014 Yasin

how to download this code

18 Apr 2014 Ahmad

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

28 Oct 2013 BESMA

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

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
mex kdtree_common.cc kdtree.cc kdrangequery.cc kdtreeidx.cc

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

13 Feb 2012 Andrei Gh.  
13 Feb 2012 Andrei Gh.

Very good code.
Thanks!

P.S. Dear Vineet and Tarek,

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

29 Jan 2012 Tarek

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

20 Dec 2011 dopedmind

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

16 Aug 2011 S R

Hi,
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:
%----
xM=randn(1000000,1);
[tmp,tmp,TreeRoot]=kdtreeidx(xM,[]);
%----
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!
Sietse

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

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
[CP, DIST, ROOT] = KDTREE(REFERENCE, MODEL)
please tell me how to get this function file of kdtree ,
regards, ghiayas

03 Jun 2010 blue ice

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

25 May 2010 Ram Lakshmi

Hello,

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?

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, []);

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

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.

16 Oct 2009 Alok

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

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
thanks

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

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"

Marzia

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.

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  
Updates
29 Oct 2013

More detailed instructions on how to create the mex runtimes.

29 Oct 2013

More detailed instructions on how to create the mex runtimes.

Contact us