This implements a KDTree for nearest neighbor and range searching.The KDTree stores a N-dimensional set of points. The tree can be queried for all points within a Euclidian range in order O(sqrt(p)+k) time, where p is the number of points and k is the number of reported points. A nearest neighbor search can be done in order O(log(p) time. The m-files are binary MATLAB functions written in C++. Source code is included as well as binaries for Linux on i386 and x86_64 systems and Windows (i386).
First thanks to the Author for a nice submition I am using often to work with lidar point clouds.
But now I wish to use kdtree_range with multiple boxes & single call (making a loop takes for ages!). This is, I define the "range" as 3D array. An example what I did:
>> r = rand(5,2);
>> tree = kdtree(r);
>> boxm
boxm(:,:,1) =
0 0
0.5000 0.5000
1.0000 1.0000
boxm(:,:,2) =
0.5000 0.5000
1.0000 1.0000
1.5000 1.5000
>> kdtree_range(tree,boxm)
Multple range input must have size (N,ndim,2)
But the boxm HAS the size (N - number of boxes, ndim - which is two, 2)!?!
Any suggestios how to make it work?
For one dimensional data I am searching, the range search gives some results which are outside the specified range by a tiny bit. e.g. 4-5 orders of magnitude relative to the search window size.
example for reproducing this : (takes a few minutes to complete run)
rng('default')
for i=1:1000
x=rand(100000,1);
tree=kdtree(x);
r=[0.3331 1/3];
idx=kdtree_range(tree,r);
found=x(idx);
if any(found<r(1))
disp(i)
disp(found(found<r(1))-r(1))
end
if any(found>r(2))
disp(i)
disp(found(found>r(2))-r(2))
end
end
I had some troubles compiling this on MacOSX Snow Leopard.
In order to compile correctly this package I just added the following line to the CXXFLAGS
" -undefined dynamic_lookup -bundle "
and also removed the other options specifically:
" -mtune=pentium4 -msse -msse2 -fPIC"
However, I doubt that keeping them would harm the compilation.
It is a very nice and well implemented package.
Many thanks for sharing it.
I just managed to compile mex files for this submission on windows 64.
It wasn't that easy, and I wasted a few good hours on that, but it works now.
I also admit I know almost nothing about compiling and so forth so there might be better ways to do it, but anyway these were my steps:
1. Installed MS Visual Studio 2010 (warning: it's not free, but luckily my helpdesk had a licensed copy)
2. Opened Matlab, typed
>> mex -setup
and went through the setup process.
3. opened the options file:
C:\Users\apaster\AppData\Roaming\MathWorks\MATLAB\R2011b\mexopts.bat
(find the right location by typing
and added the folder P:\Documents\MATLAB\kdtree\src that contained the source files of kdtree to the options file (lines 25-26):
set PATH=P:\Documents\MATLAB\kdtree\src;%VCINSTALLDIR%\bin\amd64;%VCINSTALLDIR%\bin;%VCINSTALLDIR%\VCPackages;%VSINSTALLDIR%\Common7\IDE;%VSINSTALLDIR%\Common7\Tools;%LINKERDIR%\bin\x64;%LINKERDIR%\bin;%MATLAB_BIN%;%PATH%
set INCLUDE=P:\Documents\MATLAB\kdtree\src;%VCINSTALLDIR%\INCLUDE;%VCINSTALLDIR%\ATLMFC\INCLUDE;%LINKERDIR%\include;%INCLUDE%
seems like if we don't do that, the compiler won't be able to find the kdtree.h file
4. from Matlab, typed:
>> cd 'P:\Documents\MATLAB\kdtree\src'
>> mex kdtree.cpp kdtree_create.cpp
>> mex kdtree_range.cpp kdtree.cpp
>> mex kdtree_closestpoint.cpp kdtree.cpp
5. That's it ! Now just copied the .mexw64 files to \kdtree\@kdtree folder.
The code is very well written. But the description is misleading. It says that "The tree can be queried for all points within a Euclidian range". But actually the range we specify is rectangular range in each dimensions.
# The below two lines don't seem to work -- I'll do it manually
#{$(OUTDIR)}.mexw64{$(OUTDIR)}.obj:
# $(LINK) $(OUTDIR)$< $(LINKFLAGS) /OUT:$(OUTDIR)$<.mexw32
Hello, I am trying to do this:
>> r = rand(10,3);
>> tree = kdtree(r);
There is error
??? Error using ==> kdtree
Must have at least two input arrays.
How can I solve this?
Thank you
12 Sep 2008
Andrea Tagliasacchi
I have been trying to use this utilities for OSX under Matlab2008a.
In the Makefile I changed the compiler to standard g++ (g++4.3.1):
CXX = g++
Also I had to remove some of the CXX options to compile successfully:
-mtune=pentium4 -msse -msse2 -fPIC
The make clean didn't remove the symbolic link so an error would be generated if you tried to recompile the source.
Also I had to change several inclusion directives to comply with the standard in almost all the *.cpp files:
With these changes I tried to compile under linux, which with these changes was finally successfully. However, when I try to run the script provided as an example in README.txt I get the following:
>> r = rand(1000,3);
>> tree = kdtree(r)
??? Attempt to execute SCRIPT kdtree.kdtree as a function:
/cs/grad1/ata2/temp/kdtree 3/@kdtree/kdtree.m
I also tried to compile under OSX and i686-apple-darwin9-g++-4.0.1 and I get the following:
I finally give up using this utility...
At least it should have worked in Linux properly
21 Aug 2008
Paul Le
please Post it a gain! The zip file does not contain enough files as described.
Thanks,
Paul
01 Aug 2008
Kim A
I think because I am using older Matlab version, 2006a, I cant run the program. I tried to use mex .cpp but still not successful. Anyone can help me for this?
23 Jul 2008
Nils **********
10 Jul 2008
David Doria
Would it be possible to include a "NearestNeighborExceptThisPoint" function? For example, I need to find the nearest neighbor to each point in a set. So I build the kdtree, then the "nearest neighbor" to each point is itself!
06 Jul 2008
David Doria
I see some odd behavior when my data set has NaN members - it returns some random point as the best match rather than complaining. Other than that, this code was very helpful!
25 Mar 2008
Yi Cao
Excellent work. Very efficient. Better than the kdtree provided in MATLAB Image Processing Toolbox. Would you like to upgrade the single nearest point search to a k-NN search?
04 Nov 2007
saurabh agrawal
>> r = rand(1000,3);
>> tree = kdtree(r)
??? Error using ==> class
Class kdtree is not a valid class name.
12 Aug 2007
Sam Dambreville
Stellar(as usual)
Thanks+++++++++
08 Jul 2006
Liu Shuyong
It is a very good performance. But if I want to display the tree,how can I modify the programme. and if I want to count the searching times of this algorithm, how can I do.thank you.
31 Jan 2006
J. Knight
Good, but supporting doubles would make it even better.
11 Nov 2005
Zach Buckner
Absolutely perfect. Very well designed and packaged.
30 Aug 2005
hu wenchao
could you give your algorithms and time complexity analysis
08 Jun 2005
T M
Very good. Speeds up my program a lot
21 Apr 2005
João Ferreira
As Alaa said, great AND fast. Thank you, Steven!
20 Apr 2005
Alaa Halawani
Great and fast
Updates
07 Apr 2005
A small but important change -- the border searching for the closest point function now compares |r|^2 instead of |r|. Removing the square root function siginificanly speeds up the closest point algorithm.
20 Apr 2005
Fix memory leak in kdtree creation
29 Jun 2005
Update such that the tree is serialized instead of stored in an abstract pointer. This means that the tree can be saved in a MATLAB file (or to disk) and loaded again quickly. Also, the implementation is now done using MATLAB classes.
11 Nov 2005
Update so that kdtree_range searches can be done on multiple volumes with a single call. Also, the tree creation switches from using a quicksort to a heapsort -- seems to be a little faster.
09 May 2006
1. Significantly speed up tree creation
2. Lower latency (removed tree "unserialization" for each function call)
3. fixed kdtree_closestpoint bug that returned incorrect points (but not indices) when querying closest point.
11 May 2006
Fix an error that allocates too much memory when creating tree
06 Jun 2006
Fix a memory error that sometimes causes incorrect results.