3

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.

tytamu
  • 555
  • 3
  • 11
  • 20
  • Can elements from A and/or B be reused? What sort of distance do you want to minimize? – aschepler Aug 23 '12 at 01:16
  • @ aschepler, the elements from A and B can not be reused. I do not quite understand your second question, but what I want is the minimum point to point distance. Hope this clarify my question. – tytamu Aug 23 '12 at 01:19
  • @ aschepler, I guess I understand your second question now, I modify my question a bit, hope this clarify the second point you made. – tytamu Aug 23 '12 at 01:27
  • Have you looked into using `dsearchn`? – Ansari Aug 23 '12 at 01:36
  • @ Ansari, I guess dsearchn may not be useful here because the elements from A and B can not be reused. – tytamu Aug 23 '12 at 01:55
  • Have a look at my response to this question: http://stackoverflow.com/questions/10639925/how-to-find-the-closest-vector-to-a-given-vector-in-matlab/10648151#10648151 Although I was finding a mean closest difference, on the way to finding that it will have to compute what you are looking for. – Dan Aug 23 '12 at 07:12
  • Related question: http://stackoverflow.com/questions/11631934/sort-coordinates-points-in-matlab/11632176#11632176 – Gunther Struyf Aug 23 '12 at 07:15

2 Answers2

4

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.

Gunther Struyf
  • 11,158
  • 2
  • 34
  • 58
  • @ Gunther, Just found a bug, if A=[1 2; 3 4], B=[1 3]; when I run the code, both [1 2] and [3 4] are group with [1 3], what should I do to get C{1,1}=[1 2;1 3] and C{1,2}=[3 4]? thanks – tytamu Aug 23 '12 at 21:34
  • It's not a bug, read my code: '2. Looping over the smallest of `A` or `B`'; So if `B` is smaller, switch `A` and `B`! – Gunther Struyf Aug 23 '12 at 21:41
0

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.

Rody Oldenhuis
  • 37,726
  • 7
  • 50
  • 96
  • What about `A=[0 0;1 1]` and `B=[1 1;0 0;2 2]`? For this input, the result is `I= [2 ; 2]`! I don't see how setting lower triangular part of `dists` to `NaN` solves the problem of not using elements of `B` multiple times. You don't know in advance which points lies closest together, unless everything is already sorted, in which this question is useless... – Gunther Struyf Aug 23 '12 at 07:53
  • @GuntherStruyf Yep, my solution was wrong; I was blinded by the correct outcomes for this particular problem. This edit should rectify that. – Rody Oldenhuis Aug 23 '12 at 08:20
  • @GuntherStruyf I still don't like that for loop though...I feel there is a function for that, but it doesn't come to mind... – Rody Oldenhuis Aug 23 '12 at 08:21
  • You _have_ to handle each coordinate in `A` one at a time, because it affects the solution of other coordinates in `A`. There is no straightforward/loop-free/non-iterative solution for this problem imo. – Gunther Struyf Aug 23 '12 at 09:13
  • @GuntherStruyf is that downvote yours? Granted, yours is the more elegant (and faster!) solution, but a downvote...be a sport :) – Rody Oldenhuis Aug 23 '12 at 09:44
  • downvoted because it was wrong in the first place, hadn't time yet to verify your correction, but it looks okay now though ;) I immediately saw the problem with your first solution, the correction looks a bit more complicated to go through quickly :p – Gunther Struyf Aug 23 '12 at 10:18