CODEWITHSUNDEEP
matlabnearest-neighbor
tytamu
tytamu

Reputation: 565

find the nearest point pairs between two sets of of matrix

Assume I have two sets of matrix (A and B), inside each matrix contains few point coordinates, I want to find out point in B nearest to A and output a cell array C listed the nearest point pair coordinates accordingly and one cell array D register the unpaired spot, how should I do it?

To be more specific, here is what I want

Two sets of matrix contain spot xy coordinates;

A=[ 1 2; 3 4]; B=[1 3; 5 6; 2 1];

want to get C{1,1}=[1 2; 1 3]; C{2,1}= [3 4; 5 6]; D{1,1}=[2 1];

Thanks for the help.

Upvotes: 3

Views: 9055

Answers (2)

Rody Oldenhuis
Rody Oldenhuis

Reputation: 38052

Here's my take on the problem: 

A=[1 2
   3 4]; 

B=[1 3
   5 6
   2 1];

dists = pdist2(A,B);

[dists, I] = sort(dists,2);

c = NaN(size(A,1),1);
for ii = 1:size(A,1)    
    newC = find(~any(bsxfun(@eq, I(ii,:), c), 1));
    c(ii) = I(ii,newC(1));
end

C = cellfun(@(x)reshape(x,2,2).',...
        mat2cell([A B(c,:)], ones(size(A,1),1), 4), 'uni', false);
D = {B(setdiff(1:size(B,1),c), :)}

This solution assumes

  • all your vectors are 2D
  • stacked in rows of A and B
  • and A is always the source (i.e., everything is compared to A)

If these assumptions do not (always) hold, you'll have to take a more general approach, like the one suggested by @GuntherStruyf.

Upvotes: 0

Gunther Struyf
Gunther Struyf

Reputation: 11168

There is not exactly one solution to this problem, take for example the (one-dimensional, but expandable to N-D) case:

A= [1; 3];
B= [2];

Then either A(1) or A(2) can be the leftover point. Which one your algorithm spits out, will depend on how it works, ie which point you take first to find the nearest point.

Such algorithm consists imo of

  1. Finding distances between each combination of A(i) and B(j). If you have the statistics toolbox, pdist2 does this for you:

    A=[ 1 2; 3 4];
B=[1 3; 5 6; 2 1];
dist = pdist2(A,B);

  2. Looping over the smallest of A or B (I'll take A, cause it is smallest in your example) and finding for each point in A the closest point in the remaining set of B:

    N = size(A,1);
matchAtoB=NaN(N,1);
for ii=1:N
    dist(:,matchAtoB(1:ii-1))=Inf; % make sure that already picked points of B are not eligible to be new closest point
    [~,matchAtoB(ii)]=min(dist(ii,:));
end
matchBtoA = NaN(size(B,1),1);
matchBtoA(matchAtoB)=1:N;
remaining_indices = find(isnan(matchBtoA));

  3. Combine result to your desired output matrices C and D:

    C=arrayfun(@(ii) [A(ii,:) ; B(matchAtoB(ii),:)],1:N,'uni',false);
D=mat2cell(B(remaining_indices,:),ones(numel(remaining_indices),1),size(B,2));

Note that this code will also work with 1D points or higher (N-D), the pdist2 flattens everything out to scalar distances.

Upvotes: 4

Related Questions