Closest Points between two datasets without using pdist2

2 views (last 30 days)
Hi, i have two matrices A, of size mx2, and B, of size nx2.
Each row of both matrices identifies a point in 2D space. What i want to do is to write a code, that does not involve loops and pdist2, as fast as possible, that tells me the indices of the row of both A and B such that the distance squared of the two points is the minimum one.
Example:
A=[5 6;
1 2;
3 4
1 8];
B=[3 0;
2 1;
4 1;
3 5;
1 2];
My function must be like [indA,indB]=function(A_matrix,B_matrix)
I want as output [2,5]=function(A,B)
I found a solution using for-loops but i really would like to find a solution using repmat that involves vectorization.
Thanks
  4 Comments
Alberto Belvedere
Alberto Belvedere on 25 Oct 2020
How could i use implicit expansion in this case? Furthermore, is it better to use a combination of find+min or to use sort twice (first by rows, then by columns) on the resultant matrix?

Sign in to comment.

Accepted Answer

Walter Roberson
Walter Roberson on 25 Oct 2020
A=[5 6;
1 2;
3 4
1 8];
B=[3 0;
2 1;
4 1;
3 5;
1 2];
P = permute(sum((A-permute(B,[3 2 1])).^2,2),[1 3 2]) %will be size(A,1) by size(B,1)
P = 4×5
40 34 26 5 32 8 2 10 13 0 16 10 10 1 8 68 50 58 13 36
A_idx_in_B = sum(cumprod(P ~= min(P,[],1),1),1)+1
A_idx_in_B = 1×5
2 2 2 3 2
B_idx_in_A = sum(cumprod(P ~= min(P,[],2),2),2)+1
B_idx_in_A = 4×1
4 5 4 4
This code resolves ties in favor of the first match.
  3 Comments

Sign in to comment.

More Answers (1)

Mitchell Thurston
Mitchell Thurston on 24 Oct 2020
Edited: Mitchell Thurston on 24 Oct 2020
Came up with a solution:
[m,~] = size(A);
[n,~] = size(B);
A_rep = repmat(A,n,1);
B_rep = B';
B_rep = repmat(B_rep(:)',m,1);
dist = hypot( A_rep(:,1)-B_rep(:,1:2:end), A_rep(:,2)-B_rep(:,2:2:end) );
ind = find(dist == min(dist));
indB = floor((ind-1)./m)+1
indA = mod(ind-(indB-1)*m,n)
  3 Comments
Alberto Belvedere
Alberto Belvedere on 25 Oct 2020
I'll try some minor tweaks tomorrow starting from your excellent job. Thank you so much for your time!

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!