nearest point from two matrices

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?

[Kaushik Lakshminarasimhan]

The following two requirements are not compatible:

1) I need to find the nearest neighbor of each point in A from B.

2) ...is there any other function that can be used so that the indices are not repeated?

Please think carefully about what exactly you want and edit your question.

[Walter Roberson]

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?

Answer 1

[John BG]

Hi Busy Bee

this is John BG <mailto:[e-mail] [e-mail]>

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

<mailto:[e-mail] [e-mail]>

[Busy Bee]

as you can see in your answer, the second element of B is assigned to 4,7 and 9th element of A. Once an element from B is assigned to A, it should be excluded from the next calculations. There should be no repetition. I need unique neighbors.

[John BG]

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

<mailto:[e-mail] [e-mail]>