Site Overlay

原地 $\pi/2$ 旋转图像算法

我对旋转 $\pi/2$ 的第一反应就是乘以虚数单位 $i$。高中的时候学过,乘以 $i$ 相当于矢量顺时针旋转 $90^\circ$

$$
(x, y) \to (-y, x)
$$

这个公式表明了旋转的坐标变化。不过,由于是在程序实现,会出现覆盖目标点的情况。所以,可以先临时保存当前点,然后用前一个点覆盖当前点,如此往复,直到用当前点覆盖后一个点。这样的话,针对一个象限里的点进行旋转就行了:

$$
(+x, +y) \to (-y, +x)\\
(-y, +x) \to (-x, -y)\\
(-x, -y) \to (+y, -x)\\
(+y, -x) \to (+x, +y)\\
$$

但是还有一个问题,计算机的图像是存放在矩阵的,找到矩阵的中心建系并不容易。可以考虑直接把整个矩阵作为第一象限,由于是方阵,平移旋转后的矩阵就行了。平移参数就是矩阵的边长。

$$
(+x, +y) \to (S-y, +x)\\
(S-y, +x) \to (S-x, S-y)\\
(S-x, S-y) \to (y, S-x)\\
(y, S-x) \to (x, y)\\
$$

伪代码:

$tmp = img[x,y];
$img[x, y] = $img[y, S-x];
$img[y, S-x] = $img[S-x, S-y];
$img[S-x, S-y] = $img[S-y, x];
$img[S-y, x] = $tmp;

那么循环要怎么设计呢?由于一次交换四个点,所以理论上只要遍历 $\dfrac{1}{4}$ 图像就可以了。而且是任意 $\dfrac{1}{4}$

最终代码如下:

class Solution
{
public:
    void rotate(vector<vector<int>> &img)
    {
        int S = img.size();
        int tmp;
        for (int x = 0; (S % 2) ? x <= S / 2 : x < S / 2; x++)
        {
            for (int y = 0; y < S / 2; y++)
            {
                tmp = img[x][y];
                img[x][y] = img[S - 1 - y][x];
                img[S - 1 - y][x] = img[S - 1 - x][S - 1 - y];
                img[S - 1 - x][S - 1 - y] = img[y][S - 1 - x];
                img[y][S - 1 - x] = tmp;
            }
        }
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注