MATLAB: Find the nearest point in a regular grid

nearest neighbourvectorization

Dear all,
I would like to compute the point of a regular grid that is nearest to a given sample. I need also to keep track of the indexes of the nearest point.
I have implemented the following code, which works fine for small grids:
N = 100; %number of points
pp1 = linspace(0, 1, N);
pp2 = linspace(0, 1, N);
[P1, P2] = ndgrid(pp1, pp2); %regular grid of points
querypoints = rand(2,N); %points for which I want to compute the nearest neighbour
neighbours = zeros(N, 2); %it contains the indexes of the points in [P1,P2] nearest to the querypoints
distances = zeros(N*N, 1);
indexes = zeros(N*N, 2); %indexes of the matrices P1 and P2 of the nearest point
for j=1:N
    % I compute the distances of the j-th point from the other ones
    z = 1;
    for k=1:N
        for l=1:N
            distances(z) = norm(querypoints(:,j)-[P1(k,l);P2(k,l)]);
            indexes(z,:) = [k, l];
            z = z + 1;
        end
    end
    [~, idx] = min(distances);
    neighbours(j,:) = indexes(idx,:);
end
Unfortunately, if the number N of points increases my code become very very slow due to the three for cycles. Any idea to make my code faster (for instance through code vectorization)?
Any help is really appreciated. Thank you in advance!
Mauro

Best Answer

Dear Sudheer,
thank you for your kind reply. I have checked the documentation of the function dsearchn, and I noticed that it requires a triangulation. I don't know if this is the best option since I have no triangulations but only a regular grid and some other points.
Related Question