# How to calculate figure rotation efficiently?

I have a Figure represented through a matrix of bytes (bitmap-like matrix). Example Figure is shown on the `Picture 1`.

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. In the `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:

1. Loop through angles from 0 to 45.
2. For the current angle, for every figure point calculate new, rotated, location
3. Find bounds of rectangle that contains figure (minimum and maximum x,y) and register it if is the best match so far
4. 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?

It looks like you can find the arbitrarily aligned minimum bounding box using the linear time Rotating calipers algorithm.

Once you have the bounding box, you just need to determine the angle of rotation by calculating the slope of one of the sides.

• This is a great solution, very good one. Commented Nov 11, 2014 at 21:48
• Great, since I already have sorted points by x and y, I can find convex hull with this en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/… and use existing algorithm with hull points. Commented Nov 11, 2014 at 21:49

The first step of your approach is flawed - there are an infinite number of real values between 0 and 45, so it makes no sense to "loop through them". However, your algorithm can be repaired:

• find the convex hull of the polygon

• loop through the finite (!) number of angles given by the outer edges of the convex hull

• now apply the steps 2 to 4 using these angles.

This works because it can be shown that the minimum enclosing rectangle must touch one of the outer edges of the convex hull.

• Yes, that's exactly what I am going to do, already found wit help of the Dan's answer. Thank you. Commented Nov 11, 2014 at 21:50
• @Dusan: I am not sure the other answer describes the same approach, thus I tried to describe the solution in a simpler way, hopefully a little bit clearer. Found a description here: cgm.cs.mcgill.ca/~orm/maer.html Commented Nov 11, 2014 at 21:54
• Yes, you are right, your approach is much more concrete and simpler and clearer, but I have concluded the same approach myself by the hints given in Dan's answer, so I gave him an accept. Hope your answer will gain much more up-votes. No hard feelings. Cheers! Commented Nov 11, 2014 at 21:58