MATLAB Answers

nearest point from two matrices

3 views (last 30 days)
Busy Bee
Busy Bee on 28 Apr 2018
Commented: John BG on 30 Apr 2018
I have two matrices, A and B containing the position of points in 2-d space. Both the matrices have same number of entries, say 10. I need to find the nearest neighbor of each point in A from B. Each point from A should have a unique neighbor from B i.e. if one point from B is assigned as nearest neighbor to a point in A, it should not be assigned to any other point from A. I tried using dsearchn but it will sometimes assign the same point from B to two different points from A. I understand this happens because the same point is equidistant from both the points but is there any other function that can be used so that the indices are not repeated?
  2 Comments
Walter Roberson
Walter Roberson on 28 Apr 2018
Let us start with a small example:
3
++
+ +
+ +
1++2+++4
Now let B be the same as A.
The shortest distance from 1 to the points is 1--2, distance 3.
The shortest distance from 2 to the points is 2--1, distance 3. So far no duplication.
The shortest distance from 3 to the points is 3---1, distance 4. But that's a duplication of 2--1, so we have to rule that out? As each point is presumably not intended to be its own nearest neighbour, and 1 and 2 are both used up, that leaves 4, distance sqrt(65)
The shortest distance from 4 to the other points is 4--2, distance 4. But that's a duplication of 1--2, so we have to rule that out? That leaves 3, distance sqrt(65) ?
So 1--2 would group together, and 3<....>4 would group together?
But... if we followed in reverse order, then
The shortest from 4 to the points is 4---2, distance 4. This being the first probe, there is no duplication.
The shortest from 3 to the points is 3---1, distance 4. So far no duplication.
The shortest from 2 to the points is 2--1, distance 3. But that's a duplication of 3---1, so we have to rule that out? Next closest is 2---4, distance 4.
The shortest from 1 to the points is 1--2, distance 3. But that's a duplication of 4---2, so we would have to rule that out? Next closest is 1---3, distance 3.
So, 1->3, 2->4, 3->1, 4->2 -- a completely different configuration than above.
It thus appears that the ordering depends upon the order attempted. Is there any rule about which order to make the attempts?

Sign in to comment.

Answers (1)

John BG
John BG on 29 Apr 2018
Hi Busy Bee
1.-
Generating data
.
clear all;clc;close all
N=10
Ln=[1:N]
A=randi([0 50],N,2);
B=randi([0 50],N,2);
plot(A(:,1),A(:,2),'r*');grid on
axis([0 50 0 50])
axis equal
hold on
for k=1:1:N
text(A(k,1),A(k,2),[' ' num2str(Ln(k))],'FontSize',12,'Color','red')
end
plot(B(:,1),B(:,2),'*','Color',[.2 .7 .2]);grid on
for k=1:1:N
text(B(k,1),B(k,2),[' ' num2str(Ln(k))],'FontSize',12,'Color',[.2 .7 .2])
end
.
.
Now let's define 2 matrices for the results
2.-
Da2=zeros(Na,Nb)
.
Da2 is for the distances of each element of A to all elements of B.
.
Na2=zeros(Na,Nb)
.
Na2 is for the ordered numerals according to distance, the 1st is the nearest.
for k=1:1:Na
% L1=[1:k];L1(end)=[];L1=[L1 k+1:N] % numerals of all B neighbour except kth neighbour
pa=repmat(A(k,:),Nb,1)
Da=(sum((pa-pb).^2,2)).^.5 % distance of a point to all B neighbours
D0=sortrows([Da Lnb'])
Da2(k,:)=D0(:,1) % update sorted distances
Na2(k,:)=D0(:,2) % update sorted numerals
end
3.-
The results
Na2 =
3 4 5 1 6 2
6 2 5 4 1 3
4 1 2 3 6 5
2 6 1 4 5 3
4 3 1 5 2 6
1 4 2 6 3 5
2 1 6 4 5 3
5 6 2 3 4 1
2 6 1 4 5 3
6 2 4 1 5 3
If you focus on the 1st column
Na2(:,1)
=
3
6
4
2
4
1
2
5
2
6
reading it as follows
1st element of A - GREEN, is closest to 3rd element of B - RED.
2nd element of A - GREEN, is closest to 6th element of B - RED.
3rd element of A - GREEN, is closest to 4th element of B - RED.
4th element of A - GREEN, is closest to 2nd element of B - RED.
..
Busy Bee
if you find this answer useful would you please be so kind to consider marking my answer as Accepted Answer?
To any other reader, if you find this answer useful please consider clicking on the thumbs-up vote link
thanks in advance for time and attention
John BG
  2 Comments
John BG
John BG on 30 Apr 2018
If you find repeated locations it's just a matter of how I have generated the data you didn't supply.
If you run again the simulation the chances are that there will be no repeated locations.
Because I have generated locations with integers within a narrow range, it is probable that there are repeated locations across teams.
To avoid this, just use your data, like you mention it may not have repeated locations across teams, or if you want to use simulated data too, increase the resolution and range of the simulated data.
For instance
Na=10
Nb=6
Lna=[1:Na]
Lnb=[1:Nb]
A=.01*randi([0 50000],Na,2);
B=.01*randi([0 50000],Nb,2);
format bank
A
=
395.21 257.21
474.66 442.14
163.78 294.01
335.63 77.37
219.32 99.93
416.75 203.48
384.43 374.36
83.62 412.80
430.99 394.98
494.94 159.26
B
=
267.03 94.85
44.97 247.50
55.85 73.80
68.14 27.48
339.33 425.36
247.59 280.28
Yet this simulated data of no use to you, is it?
Have you tried my answer with your data?
I you attach data sample to your question I will run my answer with the data you provide.
Regards
John BG

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!