pythonnumpyscipyeuclidean-distancepdist

Sum of distances from a point to all other points


I have two lists

available_points = [[2,3], [4,5], [1,2], [6,8], [5,9], [51,35]]

and

solution = [[3,5], [2,1]]

I'm trying to pop a point in available_points and append it to solution for which the sum of euclidean distances from that point, to all points in the solution is the greatest.

So, I would get this

solution = [[3,5], [2,1], [51,35]]


I was able to select the initial 2 furthest points like this, but not sure how to proceed.

import numpy as np
from scipy.spatial.distance import pdist, squareform

available_points = np.array([[2,3], [4,5], [1,2], [6,8], [5,9], [51,35]])

D = squareform(pdist(available_points)
I_row, I_col = np.unravel_index(np.argmax(D), D.shape)
solution = available_points[[I_row, I_col]]

which gives me

solution = array([[1, 2], [51, 35]])


Solution

  • You can use cdist -

    In [1]: from scipy.spatial.distance import cdist
    
    In [2]: max_pt=available_points[cdist(available_points, solution).sum(1).argmax()]
    
    In [3]: np.vstack((solution, max_pt))
    Out[3]: 
    array([[ 3,  5],
           [ 2,  1],
           [51, 35]])