c++ - 就地旋转二维矩形阵列

Question

我有一个像这样的非方形数组：

const int dim1 = 3, dim2 = 4;
int array[12] = { 1, 2, 3, 
                  4, 5, 6,
                  7, 8, 9,
                 10,11,12};

我需要将其转换为：

{3,6,9,12,
 2,5,8,11,
 1,4,7,10}

也就是说，逆时针旋转/洗牌（或顺时针，算法应该类似）。

该算法应使用最少的空间。我必须在内存极度受限的环境中旋转图像，所以空间越少越好。速度不是什么大问题。

Answer 1

您可以就地转置矩阵（请参阅http://en.wikipedia.org/wiki/In-place_matrix_transposition），然后反转微不足道的行。

Answer 2

二维旋转公式为：

x' = x cos f - y sin f
y' = y cos f + x sin f

如果仅以 90° 步长旋转，则生成的公式变为：

x' = -y
y' =  x

由于数组不是正方形的，因此您必须查找分配周期，即元素 (0, 0) 被分配元素 (2, 0)，而元素 (2, 0) 又被分配 (2, 2) 等。您需要分配每个周期都在“同一”时间。

因此，要旋转整个数组，您将执行类似（伪代码）的操作：

// this function rotates 90 degrees
point successor(const point &p)
{
  return (-p.y, p.x);
}

// this function rotates 90 degrees in opposite direction
point predecessor(const point &p)
{
  return (p.y, -p.x);
}

void replace_cycle(const point &start)
{
  int data = get_data(start);
  point x = predecessor(start);
  while(x != start)
  {
    set_data(successor(x), get_data(x));
    x = predecessor(x);
  }
  set_data(successor(start), data);
}

void rotate_in_place()
{
  list<point> l;
  find_cycles(l);
  foreach(c in l)
  {
    replace_cycle(c);
  }
}

Answer 3

根本不旋转可能是一种选择。您只需设置一个标志，该标志将给出矩阵的读取方式。

缺点是，如果必须将该图像提供给某些显示设备或诸如此类的具有固定方向的设备，那可能是不可能的。

Answer 4

您可以使用 xor 不使用额外的内存。

// Switch a and b
int a;
int b;
a ^= b;
b ^= a;
a ^= b;

然后你可以使用一个简单的for循环来制作你的整个矩阵。