MATLAB Answers

Sorting points based on comparing distances.

69 views (last 30 days)
Vance Blake
Vance Blake on 1 Sep 2019
Edited: Bruno Luong on 9 Sep 2019
Hello, I am using matlab 2019a and I am trying to sort points based on comparing the distance between them. I use the pdist2 function to calculate the the distance between the points stored in matricies. One matrix has 2 sets of coordinates
A= [0 0, -5.52181708330649 5.78874218621840]
the other has 7 sets
B = [38.8197976955836 -29.0434116907097
-37.0532684880158 0.644925865563445
-4.49735986053992 57.3402937422674
-43.7442096431328 38.5935144262550
41.5359946082739 41.4696332098067
57.3572679057450 8.87552592324304
-29.8320366435934 -43.1286701525403]
After calculating the distance between each point in A and every point in B i end up with a 2x7 matrix C. C(1,1) is the distance between the first point in A and the first point in B while C(2,1) is the distance between point 2 in A and point 1 in B. I want to compare each of these distances between C(1,2) to C(2,2).... to the end and sort the points in B based on which point in A they are closest to. I hope to end up with a matrix of points closest to the first point in A and another matrix of points closest to the second point in A. If the code works with a variable number of points in A that would be greatly apprecitated. Thanks for the help.

  0 Comments

Sign in to comment.

Accepted Answer

Adam Danz
Adam Danz on 1 Sep 2019
Edited: Adam Danz on 8 Sep 2019
Use the 2nd output to min() to pair the points in B to the nearest points in A. Then use splitapply to segment the points in B into nearest neighbors in A. This works for any amount of coordinates in A.
% Creat demo data
A= [0 0;
-5.52181708330649 5.78874218621840];
B = [38.8197976955836 -29.0434116907097
-37.0532684880158 0.644925865563445
-4.49735986053992 57.3402937422674
-43.7442096431328 38.5935144262550
41.5359946082739 41.4696332098067
57.3572679057450 8.87552592324304
-29.8320366435934 -43.1286701525403];
% compute distances between A, B
C = pdist2(A,B);
% or better: C = sqrt((B(:,1)-A(:,1)').^2 + (B(:,2)-A(:,2)').^2)';
% Split B into groups that are nearest to points in A
[~, minRowIdx] = min(C,[],1); %
neighborGroups = splitapply(@(x){x},B,minRowIdx(:));
neighborGroups{n} are all the coordinates in B that are closest to A(n,:).

  31 Comments

Vance Blake
Vance Blake on 8 Sep 2019
@Stephen @Bruno I know im a bad programmer thats why I on here asking for help lol. But when it comes to creating an array of handle names how do I assign a handle name to an object that doesnt exist yet? I think you guys are assuming that my variables are all created and existing at the same time but thats not the case. If I want to use indexing for storing my plots, handle names, or whatever then wouldnt each of them have to be created already or after creation appended in to the same matrix/cell array?? Unless Im misunderstanding something which could very well be (and probably is) the case. I have read the tutorial documents for not using eval and such but it seems im missing something about indexing.
Either way thank your for all of your help. I would not have gotten to this point without it. I will look into and hopefully understand all the information that has been shown to me.
Stephen Cobeldick
Stephen Cobeldick on 8 Sep 2019
"when it comes to creating an array of handle names how do I assign a handle name to an object that doesnt exist yet?"
I do not know what "handle names" are.
However graphics objects certainly do NOT need to all exist when you create the handles array for their handles, as you can just preallocate a handles array:
or (less optimally) collect the handles into a container array, e.g. a cell array.
"I think you guys are assuming that my variables are all created and existing at the same time but thats not the case."
By the time you have plotted that data, then you have created the graphics objects, so you will certainly be able to store their handles.
"...after creation appended in to the same matrix/cell array??"
Yes. That is how robust code is writen. That is what we are advising you to do store the graphics handles in one handles array, so you can trivially access them later.
"I have read the tutorial documents for not using eval and such but it seems im missing something about indexing."
That intent of that link was to dissuade you from using "different handle names" as you wrote earlier, as it seemed that you were referring to dynamic variable names. But now I notice that you use the term "handle names" to apparently refer to graphics object handles themselves, so perhaps that link was superfluous. Or perhaps not, depending on your meaning of "handle name".
Bruno Luong
Bruno Luong on 9 Sep 2019
Handle "name"? Exists at the creation? Not sure what you are concerned.
I show you a pseudo test code.
% Generate some dummy test data
A = rand(5,2);
B = rand(100,2);
idx = nearestNeighbor(delaunayTriangulation(A),B);
gidx = unique(idx);
ngrp = length(gidx);
h = zeros(1,ngrp); % prealloate a table of graphic handles
ColorTable = jet(ngrp);
figure
hold on
for k = 1:ngrp
Bgrp = B(idx==gidx(k),:); % filter
Color = ColorTable(k,:); % Select the color of your specific group
h(k) = plot(Bgrp(:,1), Bgrp(:,2), 'o', 'Color', Color, 'MarkerFace', Color, 'Markersize', 10);
end
h(k) is array of handles, each correspond to a plot with a group.
You know which plot contains which B from idx. The information is encoded in arrays idx, gidx, ngrp, h. You can further split idx and ngrp of cell, put them in array of structures (or table), gives it a name for each individual structure if you like.
What is the problem with those arrays, what you can't figure out with array of handles h()?

Sign in to comment.

More Answers (1)

Bruno Luong
Bruno Luong on 8 Sep 2019
Edited: Bruno Luong on 8 Sep 2019
You might learn to use Delaunay triangulation that can find nearrest points much more efficiently than pdist2 or such (applicable if the number of points of A is >=3). scatteredInterpolant is based in Delaunay T.
A=rand(1000,2);
B=rand(1000,2);
% pdist2
[~,i]=min(pdist2(A,B),[],1)
% scatteredInterpolant
F=scatteredInterpolant(A(:,1),A(:,2),(1:size(A,1))','nearest');
i = F(B(:,1),B(:,2))'
% Direct call of Delaunay
i = nearestNeighbor(delaunayTriangulation(A),B)'

  6 Comments

Show 3 older comments
Bruno Luong
Bruno Luong on 8 Sep 2019
DELAUNAY is even better in this sense:
When you compute PDIST2 of M x N points it computes O(M x N) arithmetic operations. M is the number of points in A, and N in B.
When you call DELAUNAY for NEAREST search, the complexity is (M log(M)) to build F, and then N*log(M) to query nearest point.
For M = 1000 and N = 1000 you reduce the compuation from billions (pdist2) to few thousands (delaunay based).
It's the complexity of the search not about computing euclidian distance.
First NOTE: As I said you need >= 3 points in A to be able to use Delaunay.
Second NOTE: you don't even need to call SQRT to compute nearest by "dumb" method. Call min(D.^2) leads to the same result.
Bruno Luong
Bruno Luong on 8 Sep 2019
"If you could expand more on what is specifically happening with each step of your code that would be great. "
Well I apply pretty directly scatteredInterpolant or delaunayTriangulation on your data points, there is nothing mysterious about it. Please read the doc of these functions/class. It's pretty straighforward once you know what it supposes to do.
Vance Blake
Vance Blake on 8 Sep 2019
@Bruno thank you for the help! I will have to read more about it and experiment with it but your suggestions have given me a new perspective about matlab's capabilities.

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!

Translated by