通过剪切旋转

我们知道，像素排列在一个方形的网格上，而这个网格是没法旋转的。那么该怎么旋转一张图片？

这篇文章我想向大家介绍这些算法中的一个，它是我目前为止见过的最优美的算法之一。它的核心想法是：

能不能把一个旋转拆分为几个简单的，能进行的操作？

分而治之

线性代数告诉我们，旋转是一个线性变换，它可以用一个矩阵表示。

这个算法的目标是，将一个旋转表示为 几个线性变换的叠加 ，使得这些简单的线性变换能在像素网格上完成。它利用了以下两个观察。

1. 对于一张像素图，剪切（shear）操作，另一种线性变换，可以 近似地 进行；只要我们限制剪切方向只沿坐标轴方向。

方法很简单：对于X轴方向的剪切，选定中心行 了以后，行 的移动量可以用 计算；Y轴方向同理。

2. 一个旋转可以由三次剪切的叠加表示：一次 轴，一次 轴，再一次 轴。

这是一个非常令人意想不到的结果！经过这样的拆分，最终的算法就显而易见了。

实现与分析

既然我们可以对图片进行近似剪切操作，也可以将一个旋转分解为若干个剪切，那么只要把 精细的剪切替换成像素网格上的近似 ，我们就能旋转一张图片了！

从图里也许你已经能看出来了，这个算法有一个显而易见的劣势：需要一个足够大的边框，用来存放剪切后挪出来的像素点； 这也意味着旋转的角度不能太大。上面的动画展示的旋转只有-90° ~ 90°，因为超过这180°的旋转范围， 只需要中心对称地翻转一下就能转化为范围内的旋转。文章开头的旋转动画就是这样完成的。

这个奇怪的算法其实也有一些优势。首先一个，图中的每一个像素点恰好对应新图片上的一个像素点，不多不少！ 基于插值的其他旋转算法在旋转时可能会丢掉一些亮度较高的像素点，但这个算法不会。

另一个有趣的地方是，这个算法是 完全可逆的！ 旋转两次只要和为0°，就能回到原来的位置。

一般来说，图像旋转的任务都会交给GPU来完成，但对于一些古老的、没有内置旋转算法的硬件， 这个算法的效率相当地高，因为很多硬件都能高效地实现剪切操作。

这个算法还能拓展到三维以及更高维的空间，因为高维旋转矩阵也能分解为若干个剪切矩阵的乘积 （具体的分解方法就留给读者自己推导了）。