Given 3 sets of 2-dimensional points A, B and C
A = np.asarray([a1, a2, a3, ..., ak])
B = np.asarray([b1, b2, b3, ..., bm])
C = np.asarray([c1, c2, c3, ..., cn])
I want to compute a matrix AC of dimensions k x n which contains the minimum (euclidean) distance from each point in A to each point in C going through the best point in B (the best is such that minimizes the distance of the path a -> b -> c)
So far I have the distance matrices AB and BC with each pair-wise distances between points in A to B, and B to C
AB = scipy.spatial.distance_matrix(A, B)
BC = scipy.spatial.distance_matrix(B, C)
I could now, of course, run a nested for loop to get the matrix AC
My question is whether this can be done using only matrix operations between AB and BC (shape transformations allowed)
It could even be operations between A,B and C directly
Furthermore, is it possible to get a similar matrix BestB of dimensions k x n which contains at each element i,j the index of the point in B which minimizes the distance between A[i] to B[j]?
If there is any efficient algorithm to solve this problem I would also appreciate if you could mention it
You can use broadcasting here:
dist_mat = (AB[...,None] + BC)
min_dist = dist_mat.min()