I have a Figure represented through a matrix of bytes (bitmap-like matrix).
Example Figure is shown on the
The goal is to find the best rotation angle of some given Figure. When Figure is rotated by best angle, the rectangle that is parallel to X and Y axes and inscribes the Figure has the smallest area.
Rectangles that inscribes the figure are shown as light-gray on the pictures.
Picture 2, you can see that ideal rotation of the Figure is about 30 degrees clockwise.
Now, I know algorithm how to find this angle, but it seems to me that is very inefficient. It goes like this:
- Loop through angles from 0 to 45.
- For the current angle, for every figure point calculate new, rotated, location
- Find bounds of rectangle that contains figure (minimum and maximum x,y) and register it if is the best match so far
- Next angle
This is a kind of brute-force method and works well and reasonably fast for the small figures. However, I need to work with figures that contain up to 10 million points, and my algorithm becomes slow.
What would be good algorithm for this problem?