算法遍历向外螺旋式的离散2D网格从原点 [英] 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（点），它会遍历上面给出的螺旋和返回是空的和可用的第一个位置。

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.

因此​​，首先，它会检查点+ [0,0] （只是为了完整性的缘故）。然后，它会检查点+ [1,0] 。然后，它会检查点+ [1,1] 。然后点+ [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).

有没有上限，以网格大小。

There is no upper bound to grid size.

推荐答案

这没有什么错，可直接点对点的解决方案。它可以是够干净了。
只需注意螺旋从分段建造。你也可以从当前旋转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.

修改插图，编号为这些细分

edit Illustration, those segments numbered

   ... 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;
            }
        }
    }

要改变原来的方向，看看的原始值二和 DJ 。要切换旋转顺时针旋转，看到这些值被修改。

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

这篇关于算法遍历向外螺旋式的离散2D网格从原点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！