How to find nearest points from two different sized sets with Matlab?

Question

I have two sets each containing x,y coordinates for a series of points and codes respectively.

Considering the huge sizes of files I'm looking for an optimized way in Matlab to connect each point from the first set with the point from the second set that is the nearest based on Eucledian distance calculated with the help of coordinates values.

    X        Y

A=[155413 4564566; 156464 456585; ... ; n]


   code   X       Y
B=[1001 155413 4564566; 1015 156464 456585; ... ; m]

The tricky part is they are of different length. For each point (line from A) I need the corresponding "code" variable from B as being found as the closest.

Thanks.

Just a suggestion without knowing more about your data but you could try something involving convex hulls of the 2 sets if they form disjoint sets. — mathematician1975
See my answer here:stackoverflow.com/questions/10639925/… mine works for x,y,z though, so you might have to change some of the 3s to 2s (but not all of them) — Dan

Luis Mendo Luis Mendo · Accepted Answer · 2013-07-25T10:39:24

Since there are two coordinates, an approach based on complex numbers can be used, which results in a very easy solution:

A = [1 2; 3 4; 5 6; 7 8; 9 10]; % GPS points
B = [1001 0 0; 1002 7 7]; % postcode points

A_compl = A(:,1) + j*A(:,2); % transform to complex
B_compl = B(:,2) + j*B(:,3);
[AA BB] = meshgrid(A_compl, B_compl); % generate all combinations
distance = abs(AA-BB); % Euclicean distance in R^2 is modulus in C
[min_distance min_index] = min(distance);
code = B(min_index,1) % solution

This requires two complex arrays, AAand BB, of size numA times numB, where numA and numB denote the number of A and B points. If they are too large for your computer's memory you'll need a for loop to divide A into chunks of an acceptable size.

How to find nearest points from two different sized sets with Matlab?

1 Answers