Clustering a set of point by affine transform
I would suggest you try using RANSAC.  Randomly pick a triplet of $a$ points and $b$ points, find an affine transformation that maps the former to the latter, find all other points that it maps well, and create that as a candidate cluster those.  Repeat many times, and keep the best cluster.  Remove the points in that cluster, and then repeat.
This might perform better than your $O(n^3)$ time solution if you expect to have a few large clusters (but probably it is not better if you expect to have many small clusters).