Matlab calculating nearest neighbour distance for all (u, v) vectors in an array

Question

I am trying to calculate the distance between nearest neighbours within a nx2 matrix like the one shown below

point_coordinates =

   11.4179  103.1400
   16.7710   10.6691
   16.6068  119.7024
   25.1379   74.3382
   30.3651   23.2635
   31.7231  105.9109
   31.8653   36.9388





%for loop going from the top of the vector column to the bottom
for counter = 1:size(point_coordinates,1) 
    %current point defined selected 
    current_point = point_coordinates(counter,:);

    %math to calculate distance between the current point and all the points 
    distance_search= point_coordinates-repmat(current_point,[size(point_coordinates,1) 1]);
    dist_from_current_point = sqrt(distance_search(:,1).^2+distance_search(:,2).^2);

    %line to omit self subtraction that gives zero
    dist_from_current_point (dist_from_current_point <= 0)=[];

    %gives the shortest distance calculated for a certain vector and current_point
    nearest_dist=min(dist_from_current_point);

end

%final line to plot the u,v vectors and the corresponding nearest neighbour
%distances
matnndist = [point_coordinates nearest_dist]

I am not sure how to structure the 'for' loop/nearest_neighbour line to be able to get the nearest neighbour distance for each u,v vector.

I would like to have, for example ; for the first vector you could have the coordinates and the corresponding shortest distance, for the second vector another its shortest distance, and this goes on till n

Hope someone can help.

Thanks

Luis Mendo · Answer 1 · 2015-01-22T21:44:13.040

I understand you want to obtain the minimum distance between different points.

You can compute the distance for each pair of points with bsxfun; remove self-distances; minimize. It's more computationally efficient to work with squared distances, and take the square root only at the end.

n = size(point_coordinates,1);
dist = bsxfun(@minus, point_coordinates(:,1), point_coordinates(:,1).').^2 + ...
       bsxfun(@minus, point_coordinates(:,2), point_coordinates(:,2).').^2;
dist(1:n+1:end) = inf; %// remove self-distances
min_dist = sqrt(min(dist(:)));

Alternatively, you could use pdist. This avoids computing each distance twice, and also avoids self-distances:

dist = pdist(point_coordinates);
min_dist = min(dist(:));

score 4 · Accepted Answer · edited May 23 '17 at 11:54

If I can suggest a built-in function, use knnsearch from the statistics toolbox. What you are essentially doing is a K-Nearest Neighbour (KNN) algorithm, but you are ignoring self-distances. The way you would call knnsearch is in the following way:

[idx,d] = knnsearch(X, Y, 'k', k);

In simple terms, the KNN algorithm returns the k closest points to your data set given a query point. Usually, the Euclidean distance is the distance metric that is used. For MATLAB's knnsearch, X is a 2D array that consists of your dataset where each row is an observation and each column is a variable. Y would be the query points. Y is also a 2D array where each row is a query point and you need to have the same number of columns as X. We would also specify the flag 'k' to denote how many closest points you want returned. By default, k = 1.

As such, idx would be a N x K matrix, where N is the total number of query points (number of rows of Y) and K would be those k closest points to the dataset for each query point we have. idx indicates the particular points in your dataset that were closest to each query. d is also a N x K matrix that returns the smallest distances for these corresponding closest points.

As such, what you want to do is find the closest point for your dataset to each of the other points, ignoring self-distances. Therefore, you would set both X and Y to be the same, and set k = 2, discarding the first column of both outputs to get the result you're looking for.

Therefore:

[idx,d] = knnsearch(point_coordinates, point_coordinates, 'k', 2)
idx = idx(:,2);
d = d(:,2);

We thus get for idx and d:

As such, this tells us that for the first point in your data set, it matched with point #3 the best. This matched with the closest distance of 17.3562. For the second point in your data set, it matched with point #5 the best with the closest distance being 18.5316. You can continue on with the rest of the results in a similar pattern.

If you don't have access to the statistics toolbox, consider reading my StackOverflow post on how I compute KNN from first principles.

Finding K-nearest neighbors and its implementation

In fact, it is very similar to Luis Mendo's post to you earlier.

Good luck!

Matlab calculating nearest neighbour distance for all (u, v) vectors in an array

2 Answers2