Reducing the number of tuples in a list based on a threshold

user_15761535 0
Viewed 110

i have a list that contains number of tuples.

POIs = [(3,2),(6,2),(6,5),(10,1),(12,-2),(5,7)]

the tuples inside of POIs are 2D-coordinates of detected objects. What i'm trying to do is to check the eucludian distance between these objects so that if the distance between each two objects is smaller than 3, then the two objects are considered as one and the new coordinate would be the average distance between them.

Conceptionally,this looks like a clustering problem and requires to examine the distance of every object with the other and calculate the distance like

# example, hier only the first two points are considered
d = np.sqrt(np.abs(POIs[0][0]-POIs[1][0]) + np.abs(POIs[0][1]-POIs[1][1]))

 if (d<3):
   POIs[0] = (POIs[0][0]+POIs[1][0]/2 , POIs[0][1]+POIs[1][1]/2)

So, my question is if this could be computationally optimized as this becomes worse when the list includes a large number of tuples/objects

tuples list numpy python
2 Answers

I recommend to use the scipy package. Concretely, your issue can be solved with

scipy.spatial.distance.pdist(POIs)

By default, this command will use the traditional Euclidean distance. In your case, for 6 elements il will create an array of 15 elements containing the distances between points.

user_157659980

Here is a solution using SciPy's fclusterdata:

import pandas as pd
from scipy.cluster.hierarchy import fclusterdata

max_dist = 3
points = [(3, 2), (6, 2), (6, 5), (10, 1), (12, -2), (5, 7)]

clusters = fclusterdata(points, t=max_dist, criterion='distance')
clustered_points = (pd.DataFrame(points, columns=['x', 'y'], index=clusters)
                      .rename_axis(index='cluster'))
cluster_centroids = (clustered_points.groupby(clusters).mean()
                                     .rename_axis(index='cluster'))

Here is your desired result:

>>> clustered_points
          x  y
cluster       
1         3  2
1         6  2
1         6  5
2        10  1
3        12 -2
1         5  7
>>> cluster_centroids
          x  y
cluster       
1         5  4
2        10  1
3        12 -2
user_52961060
Related