用于从原点迭代离散2D网格上的向外螺旋的算法

Question

例如,这是预期螺旋的形状(以及迭代的每个步骤)

          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],返回第一个网格中的位置为空(或者没有被数据点占用)的网格.

网格大小没有上限.

Answer 1

直接的"ad-hoc"解决方案没有任何问题.它也足够干净.
请注意,螺旋是由段构建的.你可以从当前的一个旋转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.要将旋转切换为顺时针,请查看这些值的修改方式.

Answer 2

这是C++中的一个有状态迭代器.

class SpiralOut{
protected:
    unsigned layer;
    unsigned leg;
public:
    int x, y; //read these as output from next, do not modify.
    SpiralOut():layer(1),leg(0),x(0),y(0){}
    void goNext(){
        switch(leg){
        case 0: ++x; if(x  == layer)  ++leg;                break;
        case 1: ++y; if(y  == layer)  ++leg;                break;
        case 2: --x; if(-x == layer)  ++leg;                break;
        case 3: --y; if(-y == layer){ leg = 0; ++layer; }   break;
        }
    }
};

应该尽可能高效.

Answer 3

这是基于循环循环的答案的javascript解决方案

var x = 0,
    y = 0,
    delta = [0, -1],
    // spiral width
    width = 6,
    // spiral height
    height = 6;


for (i = Math.pow(Math.max(width, height), 2); i>0; i--) {
    if ((-width/2 < x && x <= width/2) 
            && (-height/2 < y && y <= height/2)) {
        console.debug('POINT', x, y);
    }

    if (x === y 
            || (x < 0 && x === -y) 
            || (x > 0 && x === 1-y)){
        // change direction
        delta = [-delta[1], delta[0]]            
    }

    x += delta[0];
    y += delta[1];        
}

小提琴:http://jsfiddle.net/N9gEC/18/

Answer 4

通过分析如何改变螺旋角的坐标可以最好地理解这个问题.考虑这个前8个螺旋角的表(不包括原点):

 x,y   |  dx,dy  | k-th corner | N | Sign |
___________________________________________
1,0    |  1,0    | 1           | 1 |  +
1,1    |  0,1    | 2           | 1 |  +
-1,1   |  -2,0   | 3           | 2 |  -
-1,-1  |  0,-2   | 4           | 2 |  -
2,-1   |  3,0    | 5           | 3 |  +
2,2    |  0,3    | 6           | 3 |  +
-2,2   |  -4,0   | 7           | 4 |  -
-2,-2  |  0,-4   | 8           | 4 |  -

通过查看此表,我们可以计算给定(k-1)角的X,Y的第k个角的X,Y:

N = INT((1+k)/2)
Sign = | +1 when N is Odd
       | -1 when N is Even
[dx,dy] = | [N*Sign,0]  when k is Odd
          | [0,N*Sign]  when k is Even
[X(k),Y(k)] = [X(k-1)+dx,Y(k-1)+dy]

现在,当您知道k和k + 1螺旋角的坐标时,您可以通过简单地将1或-1添加到最后一个点的x或y来获得k和k + 1之间的所有数据点.而已.

祝好运.

Answer 5

我会用一些数学解决它.这是Ruby代码(带输入和输出):

(0..($*.pop.to_i)).each do |i|
    j = Math.sqrt(i).round
    k = (j ** 2 - i).abs - j
    p = [k, -k].map {|l| (l + j ** 2 - i - (j % 2)) * 0.5 * (-1) ** j}.map(&:to_i)
    puts "p => #{p[0]}, #{p[1]}"
end

例如

$ ruby spiral.rb 10
p => 0, 0
p => 1, 0
p => 1, 1
p => 0, 1
p => -1, 1
p => -1, 0
p => -1, -1
p => 0, -1
p => 1, -1
p => 2, -1
p => 2, 0

高尔夫版:

p (0..$*.pop.to_i).map{|i|j=Math.sqrt(i).round;k=(j**2-i).abs-j;[k,-k].map{|l|(l+j**2-i-j%2)*0.5*(-1)**j}.map(&:to_i)}

编辑

首先尝试在功能上解决问题.在每一步中,您需要了解什么才能进入下一步？

专注于飞机的第一个对角线x = y.k告诉你在触摸它之前你必须采取多少步骤:负值意味着你必须abs(k)垂直移动步骤,而正值意味着你必须k水平移动步骤.

现在关注你当前所处片段的长度(螺旋的顶点 - 当片段的倾斜度发生变化时 - 被视为"下一个"片段的一部分).这是0第一次,然后1是接下来的两个片段(= 2个点),然后2是接下来的两个片段(= 4个点)等.它每两个片段改变一次,每次片段的部分数量增加.这j是用于.

意外地,这可以用于获取另一些信息:(-1)**j只是" 1如果你减少一些坐标到达这一步; -1如果你正在增加" 的简写(注意每一步只改变一个坐标) .同样适用于j%2,只需更换1与0和-1用1在这种情况下.这意味着它们在两个值之间交换:一个用于向上或向右"向前"的段,一个用于向下或向左移动的段.

这是一个熟悉的推理,如果你习惯于函数式编程:其余的只是一点点简单的数学.

Answer 6

它可以使用递归以相当简单的方式完成。我们只需要一些基本的二维向量数学和工具来生成和映射（可能是无限的）序列：

\n\n

// 2D vectors\nconst add = ([x0, y0]) => ([x1, y1]) => [x0 + x1, y0 + y1];\nconst rotate = \xce\xb8 => ([x, y]) => [\n  Math.round(x * Math.cos(\xce\xb8) - y * Math.sin(\xce\xb8)),\n  Math.round(x * Math.sin(\xce\xb8) + y * Math.cos(\xce\xb8))\n];\n// Iterables\nconst fromGen = g => ({ [Symbol.iterator]: g });\nconst range = n => [...Array(n).keys()];\nconst map = f => it =>\n  fromGen(function*() {\n    for (const v of it) {\n      yield f(v);\n    }\n  });\n

\n\n

现在我们可以通过生成一条扁线，加上一条旋转的（扁线，加上一条旋转的（扁线，加上一条旋转...））来递归地表达螺旋：

\n\n

const spiralOut = i => {\n  const n = Math.floor(i / 2) + 1;\n  const leg = range(n).map(x => [x, 0]);\n  const transform = p => add([n, 0])(rotate(Math.PI / 2)(p));\n\n  return fromGen(function*() {\n    yield* leg;\n    yield* map(transform)(spiralOut(i + 1));\n  });\n};\n

\n\n

这会产生您感兴趣的坐标的无限列表。这是内容的示例：

\n\n

const take = n => it =>\n  fromGen(function*() {\n    for (let v of it) {\n      if (--n < 0) break;\n      yield v;\n    }\n  });\nconst points = [...take(5)(spiralOut(0))];\nconsole.log(points);\n// => [[0,0],[1,0],[1,1],[0,1],[-1,1]]\n

\n\n

\n\n

您还可以取消旋转角度以朝另一个方向移动，或者尝试变换和腿长度以获得更复杂的形状。

\n\n

例如，相同的技术也适用于向内螺旋。这只是一个稍微不同的变换，以及改变腿长度的稍微不同的方案：

\n\n

const empty = [];\nconst append = it1 => it2 =>\n  fromGen(function*() {\n    yield* it1;\n    yield* it2;\n  });\nconst spiralIn = ([w, h]) => {\n  const leg = range(w).map(x => [x, 0]);\n  const transform = p => add([w - 1, 1])(rotate(Math.PI / 2)(p));\n\n  return w * h === 0\n    ? empty\n    : append(leg)(\n        fromGen(function*() {\n          yield* map(transform)(spiralIn([h - 1, w]));\n        })\n      );\n};\n

\n\n

产生（这个螺旋是有限的，所以我们不需要take某个任意数字）：

\n\n

const points = [...spiralIn([3, 3])];\nconsole.log(points);\n// => [[0,0],[1,0],[2,0],[2,1],[2,2],[1,2],[0,2],[0,1],[1,1]]\n

\n\n

\n\n

如果您想尝试一下，这里是整个事情的实时片段：

\n\n

\r\n

\r\n

// 2D vectors\r\nconst add = ([x0, y0]) => ([x1, y1]) => [x0 + x1, y0 + y1];\r\nconst rotate = \xce\xb8 => ([x, y]) => [\r\n  Math.round(x * Math.cos(\xce\xb8) - y * Math.sin(\xce\xb8)),\r\n  Math.round(x * Math.sin(\xce\xb8) + y * Math.cos(\xce\xb8))\r\n];\r\n\r\n// Iterables\r\nconst fromGen = g => ({ [Symbol.iterator]: g });\r\nconst range = n => [...Array(n).keys()];\r\nconst map = f => it =>\r\n  fromGen(function*() {\r\n    for (const v of it) {\r\n      yield f(v);\r\n    }\r\n  });\r\nconst take = n => it =>\r\n  fromGen(function*() {\r\n    for (let v of it) {\r\n      if (--n < 0) break;\r\n      yield v;\r\n    }\r\n  });\r\nconst empty = [];\r\nconst append = it1 => it2 =>\r\n  fromGen(function*() {\r\n    yield* it1;\r\n    yield* it2;\r\n  });\r\n\r\n// Outward spiral\r\nconst spiralOut = i => {\r\n  const n = Math.floor(i / 2) + 1;\r\n  const leg = range(n).map(x => [x, 0]);\r\n  const transform = p => add([n, 0])(rotate(Math.PI / 2)(p));\r\n\r\n  return fromGen(function*() {\r\n    yield* leg;\r\n    yield* map(transform)(spiralOut(i + 1));\r\n  });\r\n};\r\n\r\n// Test\r\n{\r\n  const points = [...take(5)(spiralOut(0))];\r\n  console.log(JSON.stringify(points));\r\n}\r\n\r\n// Inward spiral\r\nconst spiralIn = ([w, h]) => {\r\n  const leg = range(w).map(x => [x, 0]);\r\n  const transform = p => add([w - 1, 1])(rotate(Math.PI / 2)(p));\r\n\r\n  return w * h === 0\r\n    ? empty\r\n    : append(leg)(\r\n        fromGen(function*() {\r\n          yield* map(transform)(spiralIn([h - 1, w]));\r\n        })\r\n      );\r\n};\r\n\r\n// Test\r\n{\r\n  const points = [...spiralIn([3, 3])];\r\n  console.log(JSON.stringify(points));\r\n}

\r\n

\r\n

\r\n

\n