Finding the 10 nearest points to every point (with corresponding distances) within a single variable

Question

Steve 2019-9-30

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/482865-finding-the-10-nearest-points-to-every-point-with-corresponding-distances-within-a-single-variable

评论： Adam Danz 2020-2-28

F_points.mat

Hi,

I need to find the 10 nearest points (with distances) to every other point within a group of points (i.e., 10 nearest neighrbors). Attached is the file containing all the points in question. I have previously tried to use "knnsearch" but to no avail. Can anyone produce the code that will do what I need?

Any help you could offer would be greatly appreciated.

Thanks,

Steve D.

2 个评论
显示无隐藏无

the cyclist 2019-9-30

编辑：the cyclist 2019-9-30

I don't see an attachment. (A *.mat file would be most useful.) Also, describing the exact output shape/size will probably be useful as well.

Steve 2019-9-30

Hi,

Thanks for your response. I need to store the 10 closest (indexed) points to every set of coordinates contained in the attached file. Each set of 10 points should be specified with index numbers, so that they can be plotted along with their "source" point. For example point 1, could be plotted with its 10 closest points. Hope this helps.

Thanks,

Steve

请先登录，再进行评论。

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

Answer 1

Adam Danz 2019-9-30

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/482865-finding-the-10-nearest-points-to-every-point-with-corresponding-distances-within-a-single-variable#answer_394175

编辑：Adam Danz 2019-10-1

在 MATLAB Online 中打开

After loading F_points, select one of the points by indicating its row index in the variable "pt". This solution computes the euclidean distance between that target point and all other points and then selects the 10 closest points. It then plots the results.

The index of all coordinates in order of proximity to the target point is stored in ascendIdx. The coordinates for the closest 10 points is stored in xyNearest.

xy = cell2mat(F_points)';  %[n x 2] matrix of (x,y) coordinates
pt = 20; % choose a target point in xy and we'll find the 10 nearest neighbors. 
% Euclidean distance between xy(p,:) and all other points
dist = sqrt((xy(:,1)-xy(pt,1)).^2 + (xy(:,2)-xy(pt,2)).^2); 
% Find the n closest values (excluding the point selected)
n = 10; 
[~, ascendIdx] = sort(dist); 
ascendIdx(ascendIdx==pt) = [];  %remove the pt point
xyNearest = xy(ascendIdx(1:n),:); 
% Plot
figure()
plot(xy(:,1),xy(:,2),'bo')
hold on
% Show the selected point
plot(xy(pt,1),xy(pt,2),'bo','MarkerFaceColor', 'y')
% Show nearest 'n' dots
plot(xyNearest(:,1),xyNearest(:,2),'r+')
% draw lines betwween target point and neightbors
% (not shown in figure below)
plot([xy(pt,1)*ones(n,1), xyNearest(:,1)]',...
    [xy(pt,2)*ones(n,1), xyNearest(:,2)]', 'k-')

Results when pt = 20. The yellow dot is the one selected, the red + indicate the 10 closest neighbors.

[update]

To apply that for every point rather than just for one selected point, dist(n,m) below is a square matrix of the distance between point xy(n,:) and xy(m,:). ascendIdx is a square matrix of index values for each coordinate, sorted by closest distances. So, ascendIdx(p,q) is row index of q_th furthest point from xy(p,:).

xy = cell2mat(F_points)';  %[n x 2] matrix of (x,y) coordinates
dist = cell2mat(arrayfun(@(i)sqrt((xy(:,1)-xy(i,1)).^2 + (xy(:,2)-xy(i,2)).^2), 1:size(xy,1), 'UniformOutput', false)); 
n = 10; 
[~, ascendIdx] = sort(dist); 

See comments below for a comparison between this method and knnsearch() which is much slower.

7 个评论
显示 5更早的评论隐藏 5更早的评论

Adam Danz 2019-10-1

在 MATLAB Online 中打开

Comparison between the lower-level solution and knnsearch()

Below is an implementation of knnsearch() compared to the lower-level solution in my answer. They both produce the same output.

% load the data 
xy = F_points.'; 
pt = 50;         % identify target point (row number of xy)
n = 10;          % number of nearest neighbors
% knnsearch method
xyTemp = xy(~ismember(1:size(xy,1),pt),:);  %remove the target point from the list
nnidx = knnsearch(xyTemp,xy(pt,:),'K',n);   %find row index of nearest neighbors
xyNearest1 = xyTemp(nnidx,:);               %store coordinates of NN
% lower level method
dist = sqrt((xy(:,1)-xy(pt,1)).^2 + (xy(:,2)-xy(pt,2)).^2); %distance to each point
[~, ascendIdx] = sort(dist);       % sort distances
ascendIdx(ascendIdx==pt) = [];     % remove the pt point
xyNearest2 = xy(ascendIdx(1:n),:); % store coordinates of NN 
% show that the results match
isequal(xyNearest1,xyNearest2)

To compare speeds between these methods, I ran each of them 10k times and recorded the execution time using tic/toc. According to the median speeds, the lower level method was 30x faster than knnsearch().

Konstantina Bantra 2020-2-28

Hello,

I have a very similar problem and I was wondering how would you loop through each point to extract each time the 10 closest points and specifically how you would set the value for pt in each loop iteration .

Adam Danz 2020-2-28

I think what you're looking for is the "update" section of my answer where you can apply the algorithm to every point to find the 10 closest points.

If you really want a loop, you can easily embed the first part of the answer within a for-loop.

请先登录，再进行评论。

Answer 2

meghannmarie 2019-9-30

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/482865-finding-the-10-nearest-points-to-every-point-with-corresponding-distances-within-a-single-variable#answer_394180

编辑：meghannmarie 2019-9-30

Try this:

load('F_points.mat')
f = cell2mat(F_points)';
Mdl = KDTreeSearcher(f);
[idx,distance] = knnsearch(Mdl,f,'k',11);
idx = idx(:,2:end); 
distance = distance(:,2:end);

Each row in idx ocorresponds to the 10 closest points in each row in f. The first column is removed because that is the point itself so I search to 11 closest points.

2 个评论
显示无隐藏无

Steve 2019-9-30

Hi,

Thank you for the input. How do I know which point is associated to each row? Also, Can I plot each point along with their 10 neighbors? Thanks again.

meghannmarie 2019-10-1

编辑：meghannmarie 2019-10-1

I put the data in a structure so you could see points with corresponding index to nearest neightbors and the distances.

The plot function here plots each point and its 10 neighbors in a separate figure and saves it. (is that what you want?) .This will save 953 figures in your working folder.

load('F_points.mat')
T = table();
T.xy = cell2mat(F_points)';
Mdl = KDTreeSearcher(f);
[idx,distance] = knnsearch(Mdl,xy,'k',11);
T.nearestIdx = idx(:,2:end); 
T.nearestDistance = distance(:,2:end);
S = table2struct(T);
for n = 1:size(xy,1)
% Plot
h = figure();
plot(S(n).xy(1),S(n).xy(2),'bo','MarkerFaceColor', 'y')
hold on
% Show nearest 'n' dots
plot(xy(S(n).nearestIdx,1),xy(S(n).nearestIdx,2),'r*')
savefig(h,['pt_' num2str(n,'%03.0f') '.fig'])
close(h)
end

请先登录，再进行评论。

Finding the 10 nearest points to every point (with corresponding distances) within a single variable

2 个评论
显示无隐藏无

采纳的回答

7 个评论
显示 5更早的评论隐藏 5更早的评论

更多回答（1 个）

2 个评论
显示无隐藏无

另请参阅

类别

标签

Community Treasure Hunt

Finding the 10 nearest points to every point (with corresponding distances) within a single variable

2 个评论 显示 无隐藏 无

采纳的回答

7 个评论 显示 5更早的评论隐藏 5更早的评论

更多回答（1 个）

2 个评论 显示 无隐藏 无

另请参阅

类别

标签

Community Treasure Hunt

2 个评论
显示无隐藏无

7 个评论
显示 5更早的评论隐藏 5更早的评论

2 个评论
显示无隐藏无