clustering a set of rectangles

Question

I have a set of rectangles which I need to cluster together, based on euclidean distance between them.The situation is explained in the attached image. .

One possible approach is to take the center of each rectangle and cluster the center points using K means (distance function would be euclidean distance in XY plane). However, I would like to know if there is any other approach to this problem, which does not approximate a rectangle by it's central point, but also takes the actual shape of the rectangle into consideration.

Answer 1

Have a look at algorithms such as DBSCAN and OPTICS that can be used with arbitrary data types as long as you can define a distance between them (such as the minimum rectangle-to-rectangle distance).

K-means is probably not so good, as it is designed for point data with squared euclidean distance (= sum of squares, within-cluster-variance).

Answer 2

One way to formulate this problem is to look at each rectangle i, and each pair of rectangles (i,j) having distance d(i,j), and then forming a distance matrix from those. This distance measure d could be distance between rectangle centers or something more fancy like distance between closest points on rectangles.

Then, apply a clustering algorithm that takes a distance matrix as input, where you define your distance matrix D as the matrix where element (i,j) is d(i,j).

Related: Clustering with a distance matrix

Anony-Mousse's answer has some nice suggestions for algorithms you could use to cluster given the distance matrix.

Answer 3

We used Spectral Clustering with left_x, right_x, top_y, bottom_y coordinates as features with pretty good results.