Find the nearest point in a regular grid

43 次查看（过去 30 天）
Mauro Gaggero
Mauro Gaggero 2017-12-26
评论： Semion 2020-4-14
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

请先登录，再回答此问题。

采纳的回答

Mauro Gaggero
Mauro Gaggero 2018-1-2
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.
  1 个评论
Sudheer Nuggehalli
Sudheer Nuggehalli 2018-1-2
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.

请先登录，再进行评论。

更多回答（2 个）

Sudheer Nuggehalli
编辑：Sudheer Nuggehalli 2018-1-2
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!
Mauro Gaggero
Mauro Gaggero 2018-1-3
Dear Sudheer,
thank you for the suggestion, the function
k = dsearchn(X,XI)
without triangulation does a perfect job!
  1 个评论
Semion
Semion 2020-4-14
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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Correlation and Convolution 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by