# Affine transformation on a pixel grid

I'm implementing affine transformations on images. Currently I'm doing rotation, but general transformation will be added later.

Basically each pixel is mapped by the rotation matrix R:

$\begin{bmatrix} cos(a) & -sin(a) \\ sin(a) & cos(a) \end{bmatrix}$

The problem is that mapping back does not always come back to a grid point, so I basically rounding it using a brute force approach. What is a better approach (similarly to Bresenham's line drawing algorithm)?

-

• bi-linear interpolation (Select 4 nearest points, interpolate by x and y according to distance) (see here)
@DzungNguyen, I am not sure what is n in your notation, but assuming that it is number of pixels, then no, it is a linear algorithm O(n) –  Andrey Feb 18 '13 at 17:33