螺旋迭代

Question

我需要一个算法来从中心向外扫描像素。问题是不同的长度和尺寸，它有时无法到达位置（见下图蓝色部分）。

为了进一步说明问题，我将展示示例输出：

如果您比较图片，您会发现它呈螺旋状，输出与常规 for 循环相匹配，很明显问题是它无法正确打印蓝色部分

代码如下：

#include<iostream>
#include<string>
#include<math.h>

int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
int arrSize = sizeof(arr) / sizeof(arr[0]);
int width = 5;
int height = 3;

void normal2DArray() {
    int index = 0;
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            std::cout << std::to_string(x) << "," << std::to_string(y) << " = " << std::to_string(arr[index]) << "\n";
            index++;
        }
    }
}

int convertToInex(int x, int y) {
    int left = x * y; // elements to the left
    int right = (width - x) * y; // elements to the right
    return left + right + x;
}

void spiralArray() {
    // calculate middle point, which is also the start point
    int x = round((float)width / 2) - 1;
    int y = round((float)height / 2) - 1;

    int direction = 0; // 0=right, 1=up, 2=left, 3=down
    int turnCounter = 1;
    int numSteps = 1;
    int step = 1;
    int index;

    while (true) {

        index = convertToInex(x, y); // defines the index position in arr
        std::cout << std::to_string(x) << "," << std::to_string(y) << " = " << std::to_string(arr[index]) << "\n";

        switch (direction) {
        case 0: x++; break;
        case 1: y--; break;
        case 2: x--; break;
        case 3: y++; break;
        }
        index = convertToInex(x, y);

        if (step % numSteps == 0) {
            direction = (direction + 1) % 4;
            turnCounter++;
            if (turnCounter % 2 == 0) numSteps++;
        }
        step++;
        if (step > arrSize) break;
    }
}

void main() {
    std::cout << "Output of Normal 2D Array:\n";
    normal2DArray();

    std::cout << "\n"; // better spacing

    std::cout << "Output of Spiral Array:\n";
    spiralArray();
}

我试图让代码尽可能简单和小巧。它应该可以导入和使用。是的，我已经在网上搜索了我的答案，但我没有在这里找到任何掩盖问题的东西，也没有像我这样的类似设置（1D arr 和组合的 2D 数组 WIDTH/HEIGHT），而且肯定不是在 c++ 中。

❗我还需要一个适用于所有宽度和高度以及排列尺寸的解决方案，并且也适用于任何一侧❗

我希望你能为我提供有用的答案，并希望你能提供又好又快的算法implementations/optimizations

编辑： 感谢此线程中的回复。我决定暂时使用 @ldog 的解决方案，尽管我对它并不完全满意。

以下是编辑后的代码部分：

    int failcounter = 0;
    while (true) {
    index = convertToInex(x, y); // defines the index position in arr
    if (index < 0 || index > arrSize) failcounter++;
    else std::cout << std::to_string(x) << "," << std::to_string(y) << " = " << std::to_string(arr[index]) << "\n";

// unchanged code inbetween

if (step > arrSize + failcounter) break;

Answer 1

您可以在四个位置进入死胡同（即退出网格）。在每种情况下，如果仍有活细胞，则跳转到您将达到的下一个活像素。

通过跟踪您访问过的离起始像素最远的四个角，您可以很容易地做到这一点。使用罗盘坐标和 N 向上，这些是访问的 NE、NW、SW 和 SE 极值。

如果你遇到了从NE像素往N的死胡同，跳到NW像素左边第一个像素，并将移动方向设置为向下。如果那也是死胡同，跳到 SW 像素下方的一个并将移动方向设置为右。等等...当所有四个角和死角都结束时，您就完成了。

Answer 2

根据您的评论：

@Beta they don't need to connect. It just has to detect that it's outside the array size (in that case -1) and don't scan them and find the next continue point. So it would continue like this: 5, 1, 6, 11

看来您并不关心螺旋线走向“out-of-bounds”。在这种情况下，简单的答案是，将没有螺旋的形状嵌入到始终保证有螺旋的形状中。

因此如果你输入的矩形是N x M，那么将它嵌入到一个大小为max(M,N) x max(M,N)的矩形中，解决后者的问题，打印时忽略non-existent中的数字即可原来的问题。然后，您打印的序列将始终是唯一的，具体取决于嵌入的方式。最合理的嵌入是尽量使较小的矩形在较大的矩形中居中，但这取决于您。

在这种情况下，您不需要算法，因为如果您愿意执行 book-keeping 并找出所涉及的公式，您可以分析计算所有内容。

螺旋迭代

Spiral Iteration

c++

iteration

algorithm

matrix