Math behind rotation in MS Paint

For those who don't know, MS Paint only has the options to rotate an image by right angles. To carry out an arbitrary rotation ($\theta^\circ$), the following hack is suggested:

1. Horizontal skew by $\theta$

2. Vertical Stretch by $\displaystyle \frac{1}{\cos^2\theta}$

3. Vertical Skew by $-\theta$

4. Horizontal and Vertical Stretch by $\cos \theta$

I would like to know how this works.

(I guess one way would be to show that multiplying the above operations represented as matrices should return the $2$D rotation matrix, but I do not know what are the matrix representations for the intermediate steps.)

• The datagenetics article that explains this, including the maths (which I'm almost certain was the inspiration for the youtube video): datagenetics.com/blog/august32013/index.html Commented Dec 18, 2017 at 10:11
• @Mike Was this thread advertised somewhere recently? There's been a slew of voting today. Not that I complain or anything. I just haven't seen anything like this on an old question before :-). Mind you, the question was asked in 2011, so that youtube video surely predates August '13. Commented Dec 18, 2017 at 12:52
• @JyrkiLahtonen hackernews front page. news.ycombinator.com/item?id=15949626 Commented Dec 18, 2017 at 13:16
• Thanks @Andrew. More than 40 upvotes in a matter of a couple of hours on a post from 2011. There had to be a reason :-) Commented Dec 18, 2017 at 14:56
• This method is known for a long time. I'm not sure this is the original publication but it's one of the earliest I could find: Paeth, Alan W. "A fast algorithm for general raster rotation." Graphics Interface. Vol. 86. No. 5. 1986. Commented Dec 18, 2017 at 15:00

I think the following matrix product gives an explanation.

The first step is given by the matrix $$S_1=\left(\begin{array}{cc}1&\tan\theta\\0&1\end{array}\right).$$

The second step corresponds to $$D_1=\left(\begin{array}{cc}1&0\\0&\frac{1}{\cos^2\theta}\end{array}\right).$$

The second shearing operation corresponds to $$S_2=\left(\begin{array}{cc}1&0\\-\tan\theta&1\end{array}\right).$$

At this point we have done $S_2D_1S_1$ that after a little bit of matrix manipulation and using the identity $\sin^2\theta +\cos^2\theta=1$ becomes $$S_2D_1S_1=\left(\begin{array}{cc}1&\tan\theta\\-\tan\theta&1\end{array}\right).$$

The last step amounts to a scalar multiplication by $\cos\theta$ and gives us the familiar rotation matrix $$\cos\theta S_2D_1S_1=\left(\begin{array}{rc}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{array}\right).$$

Edit: I got to use this as an exercise in a freshman course that just ended. I was actually a bit unhappy with that youtube video, because it doesn't show the transitions from one step to the other. To fix this problem I made an animation, where the four steps are done gradually: in steps one and three I continuously move the shear (skew) parameter from zero to the desired value. Similarly in steps two and four the scaling parameter changes continuously from one to the proper value. All the steps are done sequentially.

Let's call the transformations $T_1,T_2,T_3,T_4$. The horizontal skew $T_1$ through angle $\theta$ should send $e_1=\begin{pmatrix}1\\0\end{pmatrix}$ to $e_1$ and send $e_2=\begin{pmatrix}0\\1\end{pmatrix}$ to $\begin{pmatrix}\tan\theta\\1\end{pmatrix}$. So the matrix implementing this transformation (which I'll also call $T_1$) has these vectors as its columns: $T_1=\begin{pmatrix}1&\tan\theta\\0&1\end{pmatrix}$.

Similar considerations give $T_2=\begin{pmatrix}1&0\\0&1/(\cos^2\theta)\end{pmatrix}$, $T_3=\begin{pmatrix}1&0\\-\tan\theta&1\end{pmatrix}$ and $T_4=(\cos \theta) I$. Multiplying these matrices together: $T_4T_3T_2T_1=\begin{pmatrix}\cos\theta&\sin\theta\\ -\sin\theta&\cos\theta\end{pmatrix}$ which is the matrix of rotation by the angle $\theta$ in a clockwise direction (as you can verify by figuring out what the columns of this rotation transformation should be).

• I apparently beat you to it by 3 minutes, but I vote for your answer, as you kindly included an explanation for the matrix representing a skew. Commented Jun 23, 2011 at 21:55
– mac
Commented Jun 23, 2011 at 22:00

In fact, you can apply any invertible linear transformation $\binom xy\mapsto \begin{pmatrix}a&b\\c&d\end{pmatrix}\binom xy$ to your image by only using a sequence of skew, stretch and flip transformations. This is due to the fact that the invertible matrices are generated by the so-called elementary matrices:

• The elementary skew matrices are the matrices of the form $\begin{pmatrix}1&a\\0&1\end{pmatrix}$ and $\begin{pmatrix}1&0\\a&1\end{pmatrix}$ for $a\in\mathbb R$. With these you can apply any linear transformation which doesn't change the area of the image and which doesn't change the orientation of the image. In fancier language: the skew matrices generate the special linear group.

• The elementary stretch matrices are of the form $\begin{pmatrix}a&0\\0&1\end{pmatrix}$ and $\begin{pmatrix}1&0\\0&a\end{pmatrix}$ for $a> 0$. Combining these with the matrices above, we can generate any invertible matrix which doesn't change the orientation of the image.

• Finally, we need the flip matrices $\begin{pmatrix}-1&0\\0&1\end{pmatrix}$ and $\begin{pmatrix}1&0\\0&-1\end{pmatrix}$ to change the orientation of the image ("flip it inside out", like turning a paper around and looking at it from behind).

As an example, we can interchange the x and y axes, that is, map $\binom xy$ to $\binom yx$, by the following operations:

1. Shear horizontally by 45 degrees.
2. Shear vertically by -45 degrees.
3. Shear horizontally by 45 degrees.
4. Flip vertically.

As you pointed out, your operations are translation, rotation, shearing (skew) and scaling (stretch). We will represent each point on your image in homogeneous coordinates which allows us to use the composite matrix operations. Homogeneous coordinates just means that we tack on a $1$. So if a point has the coordinates $(x,y)$ the vector in homogeneous coordinates is $$u = \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$$

The transformation matrix to translate the image by $t_x$ and $t_y$ is: $$T = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix}$$

The rotation matrix to rotate it by $\theta$ degrees is: $$T = \begin{bmatrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

The scaling matrix to scale each dimension is: $$T = \begin{bmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

The shearing matrix: $$T = \begin{bmatrix} 1 & a_x & 0 \\ a_x & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

And all you have to do is multiply these matrices to composite these transformations. E.g. suppose you wanted to rotate and shear:

$$\begin{bmatrix}x' \\ y' \\ w' \end{bmatrix} = \begin{bmatrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & a_x & 0 \\ a_y & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix}x \\ y \\ 1 \end{bmatrix}$$

And to obtain the point in screen coordinates just normalize by $w$, i.e. $$(x', y') = (x'/w',y'/w')$$

• That's already much better, thanks! Now it would be great if you spelled out the approximation to rotation used in the OP's question (sorry for being so insistent) :)
– t.b.
Commented Jun 23, 2011 at 21:26
• Where's the translation used? I don't see it - so it would seem more transparent not to use homogeneous coordinates.
– mac
Commented Jun 23, 2011 at 21:26
• Aren't the shear matrices upper or lower triangular depending on whether you have a horizontal or a vertical skew? Also, this time no translation is done, so I fail to see the point of adding that third coordinate. Furthermore, here the question was about an explanation as to why this sequence of shears and scaling operation results in a rotation. Commented Jun 23, 2011 at 21:34

It is worth noting that you can accomplish rotation with only a single trip to the Resize and Skew menu.
Paint applies the operations in the order: Resize, Skew Horizontal, Skew Vertical.

As a sequence of matrix transforms acting on a column vector, that is:

$$(\begin{bmatrix}1&0\\K_v&1\end{bmatrix}(\begin{bmatrix}1&K_h\\0&1\end{bmatrix}(\begin{bmatrix}S_h&0\\0&S_v\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix})))$$

Where $$K_v$$ and $$K_h$$ are the vertical and horizontal skew factors, and $$S_v$$ and $$S_h$$ are likewise the scale factors.

Because matrix multiplication is associative, let's remove the parentheses and multiply these transforms from left to right to give an equivilent single-matrix transform: $$\begin{bmatrix}S_h&K_hS_v\\S_hK_v&K_hK_vS_v+S_v\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}$$

Setting this matrix equal to the rotation matrix, $$\begin{bmatrix} \cos(θ) & \sin(θ) \\ -\sin(θ) & \cos(θ) \end{bmatrix}$$, we get a system of equations which we can solve for our scale and skew factors: $$S_h = \cos(θ)$$ $$K_h = \sin(θ)cos(θ)$$ $$S_v =1/\cos(θ)$$ $$K_v = -\tan(θ)$$

These variables describe factors in an affine transformation, but paint wants "% Resizing" and "degrees skew", so input: $$\%R_h = 100*S_h=100*\cos(θ)$$ $$\%R_v = 100*S_v=100/\cos(θ)$$ $$DegSk_h = \arctan(K_h)=\arctan(\sin(θ)\cos(θ))$$ $$DegSk_v = \arctan(K_v) = \arctan(-\tan(θ))=-θ$$

As an operational note: Paint will automatically resize your selection after a skew if the skew transformation would put the selection outside of the canvas, so make sure you have plenty of room around your selection.