Closest Points between two datasets without using pdist2

2 views (last 30 days)
Alberto Belvedere on 24 Oct 2020
Commented: Alberto Belvedere on 25 Oct 2020
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
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?

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.
Alberto Belvedere on 25 Oct 2020
Got it, thanks!

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)
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!