k-D tree

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

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.

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.

Included are the source code files in kdtree/src, as well as precompiled mex files for the following systems:

  - Mac OS X (Matlab 6.5)
  - Win2K (MATLAB 6.1)
  - Redhat Linux (MATLAB 6.5)

• Acknowledgements: This submission has inspired the following:; Iterative Closest Point Method, C++, Kdtree implementation in matlab , kd-tree for matlab
• MATLAB release: MATLAB 6.5 (R13)

[Carles Matabosch]

 

[Dimitris Nicoloutsopoulos]

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

Big thanx

[Brian Bonnlander]

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

[Chris Kelly]

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

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

[Hong zhou]

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

[ambrose thompson]

Lovely Useful and Fast.

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

[martin richards]

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

[Ray Hu]

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

[A James]

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

[Xu Chenghua]

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

[j p]

 

[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!

[wenchao hu]

i cannnot run the demo in windows,why?

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

[Anders Wiklund]

Easy to use and great support by the author.

[Mandar Joshi]

great work by author

[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

[Samy Samy]

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

[Deepak Trivedi]

Great job! It's fast.

[Quan Ho]

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

[Quan Ho]

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

[ramanathan natarajan]

 

[Mert Sabuncu]

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

[Norah .]

very good code
thanks

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

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

[Cengiz Oztireli]

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

[Alok]

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

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

[Markus Leuthold]

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

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

[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?

[blue ice]

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

[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

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

[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

[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

[vineet]

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.

[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