Image rotation algorithm

General solution: For each pixel in the destination image, take the pixel in the source image with coordinates of the destination pixel, rotated in the opposite direction.

Enhancement to solution: The rotation usually won't give exact pixel coordinates. Do a weighted average of the source pixel with its neighbors, according to the percentage it overlaps them.

Faster solution for binary images: Convert the image into "runs" of consecutive foreground pixels. Then rotate the endpoints of these lines and draw them into the destination.

Normally this will produce slight gaps due to integer roundoff, so when one or both endpoints are more than 10% away from an integer, patch by drawing TWO lines for the single source line, using the integer coordinates rounded up and down.

If one endpoint is within 10% and the other isn't, the two lines will form a 'V' shape. If both are off by more than 10%, the two lines will form an 'X' shape.

This can be done with respect to the X axis or the Y axis . Use the one with the smallest angle between the axis and the rotation angle. (I.e. if the rotation angle is between 45 and -45, use the X axis.)

Still faster solution for binary images: If there are fewer background pixels than foreground pixels, fill the destination with foreground, and follow the above algorithm with background pixels.

One of the best pages describing image rotation algorithms I've found on the internet is tied to Dan Bloomberg's excellent leptonica library. While the leptonica library itself is written in C and won't help you, his page on image rotation algorithms:

http://www.leptonica.org/rotation.html

is definitely worth a read. You will most likely want to implement something like the Rotation by Area Mapping algorithm he describes in the second portion of the page.