从原点迭代离散二维网格上的向外螺旋的算法

小编典典

从原点迭代离散二维网格上的向外螺旋的算法

algorithm

例如，这是预期螺旋的形状（以及迭代的每个步骤）

          y
          |
          |
   16 15 14 13 12
   17  4  3  2 11
-- 18  5  0  1 10 --- x
   19  6  7  8  9
   20 21 22 23 24
          |
          |

线是x和y轴。

这是算法每次迭代（点的坐标）将“返回”的实际值：

[0,0],
[1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1], [0,-1], [1,-1],
[2,-1], [2,0], [2,1], [2,2], [1,2], [0,2], [-1,2], [-2,2], [-2,1], [-2,0]..

等等

我已经尝试过搜索，但是我不确定要搜索的内容到底是什么，而我尝试过的搜索却出现了死胡同。

我什至不知道从哪里开始，除了凌乱，微妙和临时的东西，例如为每层创建/编码新的螺旋线。

谁能帮我入门？

另外，是否有一种方法可以轻松地在顺时针和逆时针（方向）之间切换，以及从哪个方向“开始”螺旋运动？（旋转）

此外，是否有一种方法可以递归执行此操作？

我的应用程序

我有一个填充有数据点的稀疏网格，我想向网格中添加一个新的数据点，并使其与给定的其他点“尽可能接近”。

为此，我将调用grid.find_closest_available_point_to(point)，它将在上面给定的螺旋上进行迭代，并返回第一个为空且可用的位置。

因此，首先，它将进行检查point+[0,0]（仅出于完整性考虑）。然后它将检查point+[1,0]。然后它将检查point+[1,1]。然后point+[0,1]，等等。并返回第一个网格中的位置为空（或尚未被数据点占用）的位置。

网格大小没有上限。

阅读 248

2020-07-28

共1个答案

小编典典

直接的“临时”解决方案没有错。它也可以足够干净。
只需注意螺旋是由段构建的。您可以从当前片段旋转90度获得下一个片段。并且每旋转两圈，线段的长度就会增加1。

编辑插图，这些段编号

   ... 11 10
7 7 7 7 6 10
8 3 3 2 6 10
8 4 . 1 6 10
8 4 5 5 5 10
8 9 9 9 9  9

。

    // (di, dj) is a vector - direction in which we move right now
    int di = 1;
    int dj = 0;
    // length of current segment
    int segment_length = 1;

    // current position (i, j) and how much of current segment we passed
    int i = 0;
    int j = 0;
    int segment_passed = 0;
    for (int k = 0; k < NUMBER_OF_POINTS; ++k) {
        // make a step, add 'direction' vector (di, dj) to current position (i, j)
        i += di;
        j += dj;
        ++segment_passed;
        System.out.println(i + " " + j);

        if (segment_passed == segment_length) {
            // done with current segment
            segment_passed = 0;

            // 'rotate' directions
            int buffer = di;
            di = -dj;
            dj = buffer;

            // increase segment length if necessary
            if (dj == 0) {
                ++segment_length;
            }
        }
    }

要改变原来的方向，看的原始值di和dj。要将旋转切换为顺时针方向，请参见如何修改这些值。

2020-07-28