I am trying to write an algorithm that rotates one square around its centre in 2D until it matches or is "close enough" to the rotated square which started in the same position, is the same size and has the same centre. Which is fairly easy.
However the corners of the square need to match up, thus to get a match the top right corner of the square to rotate must be close enough to what was originally the top right corner of the rotated square.
I am trying to make this as efficient as possible, so if the closeness of the two squares based on the above criteria gets worse I know I need to try and rotate back in the opposite direction.
I have already written the methods to rotate the squares, and test how close they are to one another
My main problem is how should I change the amount to rotate on each iteration based on how close I get
E.g. If the current measurement is closer than the previous, halve the angle and go in the same direction otherwise double the angle and rotate in the opposite direction?
However I don't think this is quite a poor solution in terms of efficiency.
Any ideas would be much appreciated.
How about this scheme:
Rotate in 0, 90, 180, 270 angle (note that there are efficient algorithm for these special rotations than the generic rotation); compare each of them to find the quadrant you need to be searching for. In other word, try to find the two axis with the highest match.
Then do a binary search, for example when you determined that your rotated square is in the 90-180 quadrant, then partition the search area into two octants: 90-135 and 135-180. Rotate by 90+45/2 and 180-45/2 and compare. If the 90+45/2 rotation have higher match value than the 180-45/2, then continue searching in the 90-135 octant, otherwise continue searching in the 135-180 octant. Lather, Rinse, Repeat.
Each time in the recursion, you do this:
A + (A + B) / 2 and the second orthant is B - (A + B) / 2)A + (A + B) / 4. Compare.B - (A + B) / 4. Compare.