algorithm - 从中心扫描阵列

Question

我正在制作一个照片马赛克应用程序，一个简单的解决方案是扫描位图以将位图划分为小方块并用小图像替换每个。但为了提高生成图像的质量，我想从中心而不是从左上角扫描位图。有没有现有的算法可以解决这个问题？

例如：

在传统方法中，我们从左上角扫描二维数组：

1  2  3  4

5  6  7  8

9  10 11 12

13 14 15 16

但我想从中心扫描到边界，螺旋式：

16 15 14 13

5  4  3  12

6  1  2  11

7  8  9  10

Answer 1

解决这个问题的一种可能性是考虑向后绘制螺旋。

您从点 (0,0) 开始，然后转到 (0, y) -> (x,y) -> (x, 0) -> (1, 0)。剩下的是一个较小的矩形。只要剩余部分的高度/宽度大于 2，您就可以这样做。

现在你有一个大小为 (x,2) 或 (2,y) 的矩形，它是开始绘制的中心矩形。为简单起见，我假设您有一个大小为 (x,2) 的矩形。你从它的左下角开始。向右画 x 步，然后向上画 1。然后你增加你的宽度或高度的步数。

现在的问题是，如何获得第一个大小为 (x,2) 的矩形？假设你有一张大小为 (w,h) 的图片，w > h那么你的第一个矩形是 (w-h+2,2) 并且开始的坐标是 (w/2-(w-h+2)/2, h /2)。

示例：给定一个矩形 w=8，h=4。中心矩形是 w=6，h=2。你从位置 (1,2) 开始。

绘图将是：向右 6，向上 1，向左 6，向下 2，向右 7，向上 3，向左 7，完成。

Answer 2

bool between(int x, int low, int high) {
  return low <= x && x <= high;
}

// we use this constant array to help tweaking the (row,col) coordinate
const int D[4][2] = {
  {0, 1},   // 0 - right
  {1, 0},   // 1 - down
  {0, -1},  // 2 - left
  {-1, 0}   // 3 - up
};

int a[n][n]; // suppose the array is n times n in size
int row = 0, col = 0, dir = 0; // initial direction is "0 - right"

for (int m = n*n; m >= 1; m--) {
  a[row][col] = m;

  int old_row = row, old_col = col;  // remember current coordinate

  row += D[dir][0];
  col += D[dir][1];

  if (!(between(row,0,n-1) && between(col,0,n-1))) { // have to move back
    // move back
    row = old_row;
    col = old_col;

    // change direction
    dir++;
    dir %= 4;

    // move again
    row += D[dir][0];
    col += D[dir][1];
  }
}