从原点开始在离散 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

这是 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 2

这是基于答案的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 3

通过分析螺旋角的坐标如何变化可以最好地理解这个问题。考虑前 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 螺旋角，只需将最后一个点的 x 或 y 加 1 或 -1 即可获得 k 和 k+1 之间的所有数据点。
就是这样。

祝你好运。

Answer 4

我会用一些数学来解决它。这是 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 5

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

// 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]));
        })
      );
};

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

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

< /a>

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

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

Answer 6

这是基于@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

Answer 7

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

Answer 8

我已经完成了与训练练习几乎相同的任务，但输出和螺旋方向有一些差异，并且有一个额外的要求，即函数的空间复杂度必须为 O(1)。

经过思考一段时间后，我想到，通过知道螺旋从哪里开始以及我计算值的位置，我可以通过减去螺旋的所有完整“圆”来简化问题，然后只计算一个更简单的值。

这是我在 ruby​​ 中对该算法的实现：

def print_spiral(n)
  (0...n).each do |y|
    (0...n).each do |x|
      printf("%02d ", get_value(x, y, n))
    end
    print "\n"
  end
end


def distance_to_border(x, y, n)
  [x, y, n - 1 - x, n - 1 - y].min
end

def get_value(x, y, n)
  dist = distance_to_border(x, y, n)
  initial = n * n - 1

  (0...dist).each do |i|
    initial -= 2 * (n - 2 * i) + 2 * (n - 2 * i - 2)
  end        

  x -= dist
  y -= dist
  n -= dist * 2

  if y == 0 then
    initial - x # If we are in the upper row
  elsif y == n - 1 then
    initial - n - (n - 2) - ((n - 1) - x) # If we are in the lower row
  elsif x == n - 1 then
    initial - n - y + 1# If we are in the right column
  else
    initial - 2 * n - (n - 2) - ((n - 1) - y - 1) # If we are in the left column
  end
end

print_spiral 5

这并不完全是您所要求的，但我相信它会帮助您思考您的问题

Answer 9

我遇到了类似的问题，但我不想每次都循环整个螺旋以找到下一个新坐标。要求是您知道您的最后一个坐标。

这是我通过大量阅读其他解决方案得出的结论：

function getNextCoord(coord) {

    // required info
    var x     = coord.x,
        y     = coord.y,
        level = Math.max(Math.abs(x), Math.abs(y));
        delta = {x:0, y:0};

    // calculate current direction (start up)
    if (-x === level)
        delta.y = 1;    // going up
    else if (y === level)
        delta.x = 1;    // going right
    else if (x === level)        
        delta.y = -1;    // going down
    else if (-y === level)
        delta.x = -1;    // going left

    // check if we need to turn down or left
    if (x > 0 && (x === y || x === -y)) {
        // change direction (clockwise)
        delta = {x: delta.y, 
                 y: -delta.x};
    }

    // move to next coordinate
    x += delta.x;
    y += delta.y;

    return {x: x,
            y: y};
}

coord = {x: 0, y: 0}
for (i = 0; i < 40; i++) {
    console.log('['+ coord.x +', ' + coord.y + ']');
    coord = getNextCoord(coord);  

}

仍然不确定它是否是最优雅的解决方案。也许一些优雅的数学可以删除一些 if 语句。一些限制是需要进行一些修改来改变螺旋方向，不考虑非方形螺旋并且不能围绕固定坐标螺旋。

Answer 10

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

Answer 11

这是算法。它顺时针旋转，但可以轻松地逆时针旋转，只需进行一些更改。我只用了不到一个小时就做到了。

// spiral_get_value(x,y);
sx = argument0;
sy = argument1;
a = max(sqrt(sqr(sx)),sqrt(sqr(sy)));
c = -b;
d = (b*2)+1;
us = (sy==c and sx !=c);
rs = (sx==b and sy !=c);
bs = (sy==b and sx !=b);
ls = (sx==c and sy !=b);
ra = rs*((b)*2);
ba = bs*((b)*4);
la = ls*((b)*6);
ax = (us*sx)+(bs*-sx);
ay = (rs*sy)+(ls*-sy);
add = ra+ba+la+ax+ay;
value = add+sqr(d-2)+b;
return(value);`

它将处理任何 x / y 值（无限）。

它是用 GML（游戏制作语言）编写的，但实际逻辑在任何编程语言中都是合理的。

单线算法只有 2 个变量（sx 和 sy）用于 x 和 y 输入。我基本上扩大了括号，很多。它使您可以更轻松地将其粘贴到记事本中，并将“sx”更改为您的 x 参数/变量名称，将“sy”更改为您的 y 参数/变量名称。

`// spiral_get_value(x,y);

sx = argument0;  
sy = argument1;

value = ((((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*2))+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*4))+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*6))+((((sy==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sx !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sx)+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sx))+(((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sy)+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sy))+sqr(((max(sqrt(sqr(sx)),sqrt(sqr(sy)))*2)+1)-2)+max(sqrt(sqr(sx)),sqrt(sqr(sy)));

return(value);`

我知道回复太晚了 :D 但我希望它对未来的访客有所帮助。

Answer 12

这是 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>

Answer 13

直接的“临时”解决方案没有任何问题。它也可以足够干净。
请注意，螺旋是由分段构建的。您可以将当前线段旋转 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.要将旋转切换为顺时针，请查看如何修改这些值。