Find the nearest point in a regular grid

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

Answer 1

[Mauro Gaggero]

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.

[Sudheer Nuggehalli]

There is actually an option to use this function to perform the search without using a triangulation. This is the third option under the "Description" section for this function:

k = dsearchn(X,XI)

With large X and small XI, this approach is faster and uses much less memory.

Answer 2

[Sudheer Nuggehalli]

We have a function "dsearchn", which does a N-D nearest point search and returns the indices of the nearest points. Using this function might be another option to compute the point of a regular grid that is nearest to a given sample and return the indices. The documentation for this function is here: dsearchn

With regard to improving code performance, there are several programming best practices that can help speed up your code. Some of these include preallocation, vectorization, and placing independent operations outside of loops to avoid redundant computations. The following link describes some of the techniques to improve performance and contains examples of how to implement these techniques: Techniques to Improve Performance

I hope this helps!

Answer 3

[Mauro Gaggero]

Dear Sudheer,

thank you for the suggestion, the function

k = dsearchn(X,XI)

without triangulation does a perfect job!

[Semion]

Hi. Could you explain, how does method "dsearchn" select an index of multi closest points with the same distance to target point? BW, the method "dnsearch" with and without triangulation produce different results.