I have a list of shapes (list of points) e.g. rectangles which I want to group/cluster together.

This is what I have:

And this is what I want to achieve.

How to do it?

I already looked at some clustering techniques, e.g., kmeans but it seems there must be a better way.

Thanks!

CodePudding user response：

I would suggest using a variant of the k-means algorithm where instead of computing the L2 distance from the center of each cluster to the points, compute the L1 distance. then update the centroids of the cluster in the regular k-means method.

After finishing the clustering you can bound each cluster in a box by taking the maximal and minimal x and y coordinates for each cluster, making a rectangle.

CodePudding user response：

1. Select a 'clustering distance' CD, i.e. the maximum distance between 2 rectangles at which they would be considered a cluster
2. Compute a second set of rects, each of which correspond to their source rects as follows:
   [xmin', ymin', xmax', ymax'] = [xmin - CD, ymin - CD, xmax CD, ymax CD]
3. Sort all xmin'-s and xmax'-s and select all pairs of rectangles where either xmin' or xmax' of the first is within (xmin', xmax') range of the second; these are the potential clustering targets
4. Sort all ymin'-s and ymax'-s and check if the pairs from the previous step do indeed intersect; form clusters
5. Iteratively merge clusters that intersect on at least 1 of the rects they contain' e.g. cluster (rect #3, rect #10) and cluster (rect #10, rect #7) are to be merged, thus becoming a (rect #3, rect #7, rect #10) cluster