C# – How to Calculate Figure Rotation Efficiently

algorithmscgeometry

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:

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?

Best Answer

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.

Related Solutions

Java Algorithms – Matrix Pattern Recognition in 2D Space

Now I'm using an algorithm that worked very well for me.

This is the pseudo code:

for each pair of points (p1, p2):
    let d be the distance vector (x and y) between them
    if d.x > (image.width-p1.x)/3 or d.y > (image.height-p1.y)/3:
        continue
    let d_t be d turned 90 degrees (d.y, -d.x)
    for i from 0 to 3:
        for j from 0 to 3:
            if there is no point at p1 + i*d + j*d_t:
                continue outer loop
    if you get here, you have a 4*4 grid

Python – How to rotate an array of bits

If you always want to rotate an image by a specific angle each time, you only need to do the heavy math once (and really, it's not that heavy). The best way to do this is by working the process backwards. For every pixel in the destination image, you calculate the corresponding location in the starting image. This "source" pixel coordinate is saved in what is called a Lookup Table or LUT. Once you build this LUT for the angle and origin of location that you want, then it is very quick to use each entry of the LUT to "move" the pixels of a source image to the correct pixel of the destination image. Where this gets tricky and involves more math is whn deciding how to weight the source date to come up with the destination data. When you work backwards from the integer destination image coordinates, you will end up with floating point coordinates in the source image. These floating point coordinates need to be interpolated. The simplest method is to use the "Nearest Neighbor" integer pixel coordinate to the calculated floating point values, but there are other algorithms such as "Bi-Linear" or "Bi-Cubic" that will provide a better quality of the finished image (but are of course slower than Nearest NEighbor"

Related Topic