GLTree Matlab Example: KNNSearch Function
Filed under: Algorithms, Computational Geometry, Optimization
Leave a Comment
KNNSearch2D query a GL-tree for k nearest neighbor(kNN)
SYNTAX
[kNNG]=KNNSearch2D(p,qp,ptrtree,k); short
[kNNG,Dist]=KNNSearch2D(p,qp,ptrtree,k); long
INPUT PARAMETERS
- p: [2xN] double array coordinates of reference points
- qp: [2xNq] double array coordinates of query points
- ptrtree: a pointer to the previously constructed GLtree.Warning if the pointer is uncorrect it will cause a crash, there is no way to check this in the mex routine, you have to check it in your script.
- k: number of neighbors
OUTPUT PARAMETERS
- kNNG: [Nqxk] array, each rows contains the kNN indexes So in row one there are kNN to first query point, in row two to the second etc…
- Dist: [Nqxk] array, Facultative output, each rows contains the distance values of the found kNN.
GENERAL INFORMATIONS
- This function is faster if all query points are given once instead of looping and passing one point each loop.
For question, suggestion, bug reports
giaccariluigi@msn.com
EXAMPLE
Let’s consider a set of random points formed by reference points and query points:
For each query points we want to find the k closest in the reference points.
Here is the Matlab code:
N=50;%reference points Nq=50;%query points k=3;%k neigh p=rand(N,2);%reference points qp=rand(Nq,2);%query points fprintf('RANDOM POINTS GENERATED\n\n') fprintf('BUILDING THE DATA STRUCTURE:\n') tic ptrtree=BuildGLTree2D(p'); fprintf('\tGLTree built in %4.4f s\n\treturned pointer %4.0f:\n\n',toc,ptrtree); fprintf('START K NEAREST NEIGHBOR SEARCH:\n') tic [KNNG,distances]=KNNSearch2D(p',qp',ptrtree,k); fprintf('\t NNsearch of%4.0f neighbors in %4.0f reference points and %4.0f query points took: %4.4f s\n\n',k,N,Nq,toc); [KNNG2, distances2]=BruteSearchMex(p',qp','k',k); fprintf('DELETING THE TREE\n\n') DeleteGLTree2D(ptrtree); fprintf('TEST SUCCESFULLY COMPLETED !!!\n\n') %plot the NNG figure(1) title([num2str(k),' Neighbours'],'fontsize',14); axis equal hold on h1=plot(p(:,1),p(:,2),'g.'); h2=plot(qp(:,1),qp(:,2),'b.'); legend([h1,h2],'Reference points','Query Points'); p1x=qp(:,1); p1y=qp(:,2); for j=1:k%loop trough all l p2x=p(KNNG(:,j),1); p2y=p(KNNG(:,j),2); plot([p1x,p2x]',[p1y,p2y]','r-') end
Results:
RANDOM POINTS GENERATED
BUILDING THE DATA STRUCTURE:
GLTree built in 0.0031 s
returned pointer 94835456:
START K NEAREST NEIGHBOR SEARCH:
NNsearch of 3 neighbors in 50 reference points and 50 query points took: 0.0016 s
DELETING THE TREE
TEST SUCCESFULLY COMPLETED !!!
Popularity: 1% [?]
Related Posts
Comments
Tell me what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!
Include MATLAB code in your comment by doing the following:
<pre lang="MATLAB">
%insert code here
</pre>
Translator
Follow Us
Video Posts
