从原点开始在离散二维网格上迭代向外螺旋的算法 [英] Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin

问题描述

例如，这里是预期螺旋的形状(以及迭代的每一步)

For example, here is the shape of intended spiral (and each step of the iteration)

          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 轴.

Where the lines are the x and y axes.

以下是算法在每次迭代中返回"的实际值(点的坐标):

Here would be the actual values the algorithm would "return" with each iteration (the coordinates of the points):

[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]..

等等

我尝试过搜索，但我不确定到底要搜索什么，而且我尝试过的搜索出现了死胡同.

I've tried searching, but I'm not exactly sure what to search for exactly, and what searches I've tried have come up with dead ends.

我什至不知道从哪里开始，除了一些杂乱、不雅和临时的东西，比如为每一层创建/编码一个新的螺旋.

I'm not even sure where to start, other than something messy and inelegant and ad-hoc, like creating/coding a new spiral for each layer.

谁能帮我开始?

另外，有没有一种方法可以轻松地在顺时针和逆时针(方向)之间切换，以及从哪个方向开始"螺旋?(旋转)

Also, is there a way that can easily switch between clockwise and counter-clockwise (the orientation), and which direction to "start" the spiral from? (the rotation)

另外，有没有办法递归地做到这一点?

Also, is there a way to do this recursively?

我的应用程序

我有一个填充了数据点的稀疏网格，我想在网格中添加一个新数据点，并让它尽可能接近"给定的其他点.

I have a sparse grid filled with data points, and I want to add a new data point to the grid, and have it be "as close as possible" to a given other point.

为此，我将调用 grid.find_closest_available_point_to(point)，它将遍历上面给出的螺旋并返回第一个空且可用的位置.

To do that, I'll call grid.find_closest_available_point_to(point), which will iterate over the spiral given above and return the first position that is empty and available.

首先，它会检查 point+[0,0](只是为了完整起见).然后它会检查 point+[1,0].然后它会检查 point+[1,1].然后 point+[0,1] 等.并返回第一个在网格中的位置为空(或尚未被数据点占用)的位置.

So first, it'll check point+[0,0] (just for completeness's sake). Then it'll check point+[1,0]. Then it'll check point+[1,1]. Then point+[0,1], etc. And return the first one for which the position in the grid is empty (or not occupied already by a data point).

网格大小没有上限.

推荐答案

直接，ad-hoc"没有错解决方案.也可以够干净.
请注意，螺旋是由段构成的.您可以从当前的片段中将其旋转 90 度来获得下一个片段.并且每旋转两次，线段长度增加1.

There's nothing wrong with direct, "ad-hoc" solution. It can be clean enough too.
Just notice that spiral is built from segments. And you can get next segment from current one rotating it by 90 degrees. And each two rotations, length of segment grows by 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 的原始值.要将旋转切换为顺时针，请查看这些值是如何修改的.

To change original direction, look at original values of di and dj. To switch rotation to clockwise, see how those values are modified.

这篇关于从原点开始在离散二维网格上迭代向外螺旋的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！