Given two lists of points $L_1=[(0,0), (0,2), (2,0), (2,2), (0,0)]$ and $L_2=[(5,2),(3,2),(5,0),(3,0),(5,2)]$, is there an algorithm to determine if they are the same shape, just rotated, reflected, and/or translated?
$L_1:$
$L_2$:
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
1 I think this will work, but a more efficient algorithm would be nice.
For every point $p_n$ in $L_1$, find the set, $S_n$, of all 2x2 matrices, $M$, such that $Mp_n \in L_2$. If $S_1 \cap S_2 \cap \dots \cap S_{|L_1|} \neq \emptyset$, then they are equivalent.
Obviously, one wouldn't need to compute the whole intersection if one computed it serially as the $S$ sets are computed and it is found that $S_1 \cap S_2 \cap \dots S_n=\emptyset$, where $n < |L_1|$.
But in the case where they are equivalent (apparently the worst case), I think that all points would have to be considered.
The algorithm could be sped up by only considering matrices that are still left in the intersection. That is, when computing $S_3$, one would only need to consider matrices in $S_1 \cap S_2$, for example.
- $\begingroup$ This won't work because translation, as I recently discovered, is not representable in a 2D matrix. So one would need to search 3D affine transformation matrices. $\endgroup$Tyler– Tyler2014-09-18 17:21:50 +00:00Commented Sep 18, 2014 at 17:21