Grouping/Clustering Rectangles

Question

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!

Answer 1

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/2, ymin - CD/2, xmax + CD/2, ymax + CD/2]
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