Given two sets of points $A$ and $B$ (of equal length, $(x,\:y)\in\mathbb{Z}^2$) you are asked to group those points into $n$ groups.
Each group is associated with a number of operations $T$ such that for every point $A_i$ in the group, there exists another point $B_i$ where $T(A_i)=B_i$. In other words, within each group, the set of points from $A$ should precisely map into the set of points from $B$ after performing the same sequence of operations.
The allowed operations are:
- Uniform scailing $(x_i,\: y_i)\to(x_i*a,\: y_i*a)$
- Rotation $(x_i,\: y_i)\to(x_i\cos\theta - y_i\cos\theta,\: x_i\cos\theta + y_i\cos\theta)$
- Translation $(x_i,\: y_i)\to(x_i+a,\: y_i+b)$
Note that the operations can be performed in any order, any amount of times.
There are many possible ways to group two sets of points, but the goal is to find the solution with the least groups.
Example:
$A = (3,\ 4), (9,\ 3), (1,\ 1)$
$B = (3,\ 1), (2,\ 3), (6,\ 9)$
$g_1 = (3,\ 4), (6,\ 9), (1,\ 1), (2,\ 3)\; \Rightarrow\; (x_i*2, \:y_i*2+1)$ $g_2 = (9,\ 3), (3,\ 1)\; \Rightarrow\; (x_i*\frac13, \:y_i*\frac13)$
This question would be relatively easy without translation as the order of rotation and scaling doesn't matter, thus we would've been able to find the transformations between every pair of points and compare them.
But with translation, there is are infinite ways to go from one point to another.
The solution for this problem doesn't have to be perfect; I am just searching for an algorithm that could consistently produce a relatively small amount of groups for two sets of arbitrary points.
I am struggling to find a way to approach this task, so I would really appreciate any suggestions or ideas.