CODEWITHSUNDEEP
matlabnearest-neighbor
opmfan
opmfan

Reputation: 191

how to find k-th nearest neighbor of a point in a set of point

I have a set of point (x,y) on a 2d plane. Given a point (x0,y0), and the number k, how to find the k-th nearest neighbor of (x0,x0) in the point set. In detail, the point set are represented by two array: x and y. The point (x0,y0) is given by the index i0. It means x0=x(i0) and y0=y(i0).

Is there any function or something in Matlab helps me this problem. If Matlab doesn't have such kind of function, can you suggest any other effective ways.

EDIT: I have to calculate this kind of distance for every point (x0,y0) in the set. The size of the set is about 1000. The value of k should be about sqrt(1500). The worst thing is that I do this many times. At each iteration, the set changes, and I calculate the distances again. So, the running time is a critical problem.

Upvotes: 7

Views: 10795

Answers (5)

3lectrologos
3lectrologos

Reputation: 9652

If you have the statistics toolbox, you can use the function knnsearch.

Upvotes: 4

zamazalotta
zamazalotta

Reputation: 433

if you will do this check for many points you might want to construct a inter-point distance table first

squareform(pdist([x y]))

Upvotes: 6

Pursuit
Pursuit

Reputation: 12345

The brute force approach looks something like this:

%Create some points
n = 10;
x = randn(n,1);
y = randn(n,1);

%Choose x0
ix0 = randi(n);

%Get distances
d = sqrt(...
    (x - x(ix0) ).^2 + ...
    (y - y(ix0) ).^2 );

%Sort distances
[sorted_Dstances, ixSort] = sort(d);

%Get kth point
k = 3;
kth = [x(ixSort(k+1)); y(ixSort(k+1))]; %+1 since the first element will always be the x0 element.

Upvotes: 2

Maurits
Maurits

Reputation: 2114

The free and opensource VLFeat toolbox contains a kd-tree implementation, amongst other useful things.

Upvotes: 2

ardnew
ardnew

Reputation: 2086

A brute force algorithm would be something like this:

array x[n] = ()
array y[n] = () 
array d[n] = ()

... populate x and y arrays with your n points ...

/* step over each point and calculate its distance from (x0, y0) */
for i = 1 to n
do
  d[i] = distance((x0, y0), (x[i], y[i])
end 

/* sort the distances in increasing order */
sort(d)

/* the k'th element of d, is the k'th nearest point to (x0, y0) */
return d[k]

Upvotes: 2

Related Questions