# nearest point from two matrices

5 views (last 30 days)
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 CommentsShowHide 1 older comment
Walter Roberson on 28 Apr 2018
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?

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
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
thanks in advance for time and attention
John BG
##### 2 CommentsShowHide 1 older comment
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?
I you attach data sample to your question I will run my answer with the data you provide.
Regards
John BG