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

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]，依此类推。并且返回第一个在网格中的位置为空（或未被数据点占用）的位置。

网格大小没有上限。

- Justin L.

---

我已经完成了这个任务，但是无法理解您给出的输出示例。 - alcuadrado

听起来像是一个代码高尔夫问题... - Jeff Meatball Yang

@alcuadrado 首先，它返回原点。然后它返回点[1,0]。然后它逆时针“螺旋”并返回点[1,1]。我会尽力让它更清晰明了。 - Justin L.

这个问题与ProjectEuler的问题有关吗？ - Khaled Alshaya

@Arak 这不是这样的；我会在帖子中澄清我的目的。 - Justin L.

请查看https://dev59.com/a3RC5IYBdhLWcg3wJNgN。 - rahil627

Answer 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 的原始值。要将旋转方向切换为顺时针，请查看这些值如何被修改。

- Nikita Rybak

---

仅仅因为个人原因，我不喜欢使用i、j、k作为变量名 :) ... 我会用i=x，j=y，k=n来表示坐标系中的数量n。 - Jeff Meatball Yang

我很喜欢这种方法 =）它易于实现，而且目前是我正在使用的方法。不过，出于好奇，我会等待看看是否出现其他方法，然后再选择最佳答案。 - Justin L.

10年后你依然值得一个“+”。 - xTwisteDx

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

应该是效率最高的了。

- mako

---

这是Godot GDScript中此算法的一个版本：https://gist.github.com/dmlo/0662bbafb125e4174fc28c60273f56d7 - Daniel Mlodecki

Answer 3

这是基于Looping in a spiral答案的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];        
}

fiddle: http://jsfiddle.net/N9gEC/18/

- Nicolas

Answer 4

通过分析螺旋角落坐标的变化，可以更好地理解这个问题。考虑以下前8个螺旋角落（不包括原点）的表格：

 x,y   |  dx,dy  | 第k个角落 | N | 符号 |
___________________________________________
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个角落的X,Y坐标，给定(k-1)角落的X,Y坐标：

N = INT((1+k)/2)
符号 = | 当N为奇数时为+1
       | 当N为偶数时为-1
[dx,dy] = | 当k为奇数时，[N*符号,0]
          | 当k为偶数时，[0,N*符号]
[X(k),Y(k)] = [X(k-1)+dx,Y(k-1)+dy]

现在，当您知道第k个和第k+1个螺旋角落的坐标时，您可以通过简单地将上一个点的x或y加1或-1来获取k和k+1之间的所有数据点。

就是这样。

祝你好运。

- Agnius Vasiliauskas

Answer 5

我会使用一些数学方法来解决它。这里是用Ruby编写的代码（包括输入和输出）：

我会使用一些数学方法来解决它。这里是用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也是如此，只需在这种情况下用0替换1，用1替换-1。这意味着它们在两个值之间交换：一个用于向上或向右的线段，另一个用于向下或向左的线段。

如果您习惯于函数式编程，则这是一种熟悉的推理方法：其余部分只涉及一些简单的数学。

- Alberto Santini

---

非常好的答案，唯一一个没有使用循环的。干得好！但是为什么要用“高尔夫版本”？这应该是“被禁止”的（除非在IOCCC上：）。像这样的代码是需要比实际代码多两倍的注释和文档的好例子。 - NightElfik

干得好，伙计！我刚刚完成了螺旋图案设计，但你的代码比我的小得多...感激不尽！1+ - Gagan Gami

Answer 6

使用递归可以相对简单地完成这个任务。我们只需要一些基本的二维向量数学知识以及用于生成和映射(可能是无限的)序列的工具：

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

现在我们可以通过递归生成一个平面线段，再加上旋转的（平面线段加上旋转的（平面线段加上旋转的……）），来表达一个螺旋。

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

  return fromGen(function*() {
    yield* leg;
    yield* map(transform)(spiralOut(i + 1));
  });
};

这将产生一个无限列表，其中包含您感兴趣的坐标。以下是部分内容示例：

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

您也可以通过取反旋转角度来调整运动方向，或者尝试改变变换和腿的长度来创建更加复杂的形状。

比如，相同的技术也适用于向内螺旋。只需要稍微调整一下变换和腿的长度即可：

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

  return w * h === 0
    ? empty
    : append(leg)(
        fromGen(function*() {
          yield* map(transform)(spiralIn([h - 1, w]));
        })
      );
};

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

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

如果您想尝试操作整个代码，请使用下面的代码：

// 2D vectors
const add = ([x0, y0]) => ([x1, y1]) => [x0 + x1, y0 + y1];
const rotate = θ => ([x, y]) => [
  Math.round(x * Math.cos(θ) - y * Math.sin(θ)),
  Math.round(x * Math.sin(θ) + y * Math.cos(θ))
];

// Iterables
const fromGen = g => ({ [Symbol.iterator]: g });
const range = n => [...Array(n).keys()];
const map = f => it =>
  fromGen(function*() {
    for (const v of it) {
      yield f(v);
    }
  });
const take = n => it =>
  fromGen(function*() {
    for (let v of it) {
      if (--n < 0) break;
      yield v;
    }
  });
const empty = [];
const append = it1 => it2 =>
  fromGen(function*() {
    yield* it1;
    yield* it2;
  });

// Outward spiral
const spiralOut = i => {
  const n = Math.floor(i / 2) + 1;
  const leg = range(n).map(x => [x, 0]);
  const transform = p => add([n, 0])(rotate(Math.PI / 2)(p));

  return fromGen(function*() {
    yield* leg;
    yield* map(transform)(spiralOut(i + 1));
  });
};

// Test
{
  const points = [...take(5)(spiralOut(0))];
  console.log(JSON.stringify(points));
}

// Inward spiral
const spiralIn = ([w, h]) => {
  const leg = range(w).map(x => [x, 0]);
  const transform = p => add([w - 1, 1])(rotate(Math.PI / 2)(p));

  return w * h === 0
    ? empty
    : append(leg)(
        fromGen(function*() {
          yield* map(transform)(spiralIn([h - 1, w]));
        })
      );
};

// Test
{
  const points = [...spiralIn([3, 3])];
  console.log(JSON.stringify(points));
}

- Asad Saeeduddin

---

漂亮的实现！使用生成器。 - Tim

Answer 7

这是一个基于@mako答案的Python实现。

def spiral_iterator(iteration_limit=999):
    x = 0
    y = 0
    layer = 1
    leg = 0
    iteration = 0

    yield 0, 0

    while iteration < iteration_limit:
        iteration += 1

        if leg == 0:
            x += 1
            if (x == layer):
                leg += 1
        elif leg == 1:
            y += 1
            if (y == layer):
                leg += 1
        elif leg == 2:
            x -= 1
            if -x == layer:
                leg += 1
        elif leg == 3:
            y -= 1
            if -y == layer:
                leg = 0
                layer += 1

        yield x, y

运行以下代码：

for x, y in spiral_iterator(10):
       print(x, y)

产生：

0 0
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
2 -1
2 0

- chris

Answer 8

我有一个Java算法，输出与你的类似，只是它优先考虑右边的数字，然后是左边的数字。

  public static String[] rationals(int amount){
   String[] numberList=new String[amount];
   int currentNumberLeft=0;
   int newNumberLeft=0;
   int currentNumberRight=0;
   int newNumberRight=0;
   int state=1;
   numberList[0]="("+newNumberLeft+","+newNumberRight+")";
   boolean direction=false;
 for(int count=1;count<amount;count++){
   if(direction==true&&newNumberLeft==state){direction=false;state=(state<=0?(-state)+1:-state);}
   else if(direction==false&&newNumberRight==state){direction=true;}
   if(direction){newNumberLeft=currentNumberLeft+sign(state);}else{newNumberRight=currentNumberRight+sign(state);}
   currentNumberLeft=newNumberLeft;
   currentNumberRight=newNumberRight;
   numberList[count]="("+newNumberLeft+","+newNumberRight+")";
 }
 return numberList;
}

- Ely Golden

Answer 9

尝试搜索参数方程或极坐标方程。两者都适合绘制螺旋形物体。这里有一个页面，其中包含大量示例，带有图片（和方程式）。它应该会给你一些更多的想法去寻找。

- Seth

Answer 10

这是一个非常简单的Javascript答案：

let v     = [0, 0]
let r     = 1
let axis  = 0
let delta = 1
let count = 4 * (radius + 1) * radius + 1

for (let i = 0; i < count; i++) {
  console.log(v[0], v[1])

  v[axis] += delta
  if (Math.abs(v[axis]) == r) {
    axis = axis ? 0 : 1
    if (axis) delta = delta < 0 ? 1 : -1;
    else if (0 < delta) r++
  }
}

请注意上面由count计算得出的所谓半径的总方块数。

完整代码示例

async function main() {
  // Drawing code
  const width  = 200 // Canvas size
  const size   = 16  // Square size
  const radius = 4   // Output "radius"

  function draw(ctx, x, y, n) {
    x = width / 2 + (size + 2) * x + 1
    y = width / 2 + (size + 2) * y + 1
    ctx.fillStyle = 'black'
    ctx.fillRect(x, y, size, size)
    ctx.fillStyle = 'white'
    ctx.textAlign = 'center'
    ctx.font = '12px serif'
    ctx.fillText(n, x + size / 2, y + size / 2 + 6)
  }

  const canvas = document.getElementById('canvas')
  const ctx    = canvas.getContext('2d')

  // ********* Important part *********
  let v     = [0, 0]
  let r     = 1
  let axis  = 0
  let delta = 1
  let count = 4 * (radius + 1) * radius + 1

  for (let i = 0; i < count; i++) {
    draw(ctx, v[0], v[1], i)

    v[axis] += delta
    if (Math.abs(v[axis]) == r) {
      axis = axis ? 0 : 1
      if (axis) delta = delta < 0 ? 1 : -1;
      else if (0 < delta) r++
    }

    // Delay for visualization only
    await new Promise(r => setTimeout(r, 100))
  }
}


main()

<canvas id="canvas" width="200" height="200"></canvas>

- jcoffland