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++, kd-tree for matlab, Kdtree implementation in matlab
• MATLAB release: MATLAB 6.5 (R13)

Other Files

kdtree/README,
kdtree/kdrange_demo.m,
kdtree/kdrangequery.m,
kdtree/kdtree.m,
kdtree/kdtree_demo.m,
kdtree/kdtreeidx.m,
kdtree/src/kdrangequery.cc,
kdtree/src/kdtree.cc,
kdtree/src/kdtree_common.cc,
kdtree/src/kdtree_common.h,
kdtree/src/kdtreeidx.cc,
kdtree/mex/glx/kdrangequery.mexglx,
kdtree/mex/glx/kdtree.mexglx,
kdtree/mex/glx/kdtreeidx.mexglx,
kdtree/mex/mac/kdrangequery.mexmac,
kdtree/mex/mac/kdtree.mexmac,
kdtree/mex/mac/kdtreeidx.mexmac,
kdtree/mex/win/kdrangequery.dll,
kdtree/mex/win/kdtree.dll,
kdtree/mex/win/kdtreeidx.dll

[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